Small Embeddings of Partial Steiner Triple Systems

It was proved in 2009 that any partial Steiner triple system of order u has an embedding of order v for each admissible . This result is best possible in the sense that, for each , there exists a partial Steiner triple system of order u that does not have an embedding of order v for any . Many partial Steiner triple systems do have embeddings of orders smaller than , but much less is known about when these embeddings exist. In this paper, we detail a method for constructing such embeddings. We use this method to show that each member of a wide class of partial Steiner triple systems has an embedding of order v for at least half (or nearly half) of the orders for which an embedding could exist. For some members of this class we are able to completely determine the set of all orders for which the member has an embedding.     

A Construction of Almost Steiner Systems

Let n, k, and t be integers satisfying . A Steiner system with parameters t, k, and n is a k‐uniform hypergraph on n vertices in which every set of t distinct vertices is contained in exactly one edge. An outstanding problem in Design Theory is to determine whether a nontrivial Steiner system exists for . In this note we prove that for every and sufficiently large n, there exists an almost Steiner system with parameters t, k, and n; that is, there exists a k‐uniform hypergraph on n vertices such that every set of t distinct vertices is covered by either one or two edges.     

On the number of SQSs,latin hypercubes and MDS codes

We establish that the logarithm of the number of latin d‐cubes of order n is and the logarithm of the number of sets of t ( is fixed) orthogonal latin squares of order n is . Similar estimations are obtained for systems of mutually strongly orthogonal latin d‐cubes. As a consequence, we construct a set of Steiner quadruple systems of order n such that the logarithm of its cardinality is as and .     

Trinal Decompositions of Steiner Triple Systems into Triangles

It is well known that when or , there exists a Steiner triple system (STS) of order n decomposable into triangles (three pairwise intersecting triples whose intersection is empty). A triangle in an STS determines naturally two more triples: the triple of “vertices” , and the triple of “midpoints” . The number of these triples in both cases, that of “vertex” triples (inner) or that of “midpoint triples” (outer), equals one‐third of the number of triples in the STS. In this paper, we consider a new problem of trinal decompositions of an STS into triangles. In this problem, one asks for three distinct decompositions of an STS of order n into triangles such that the union of the three collections of inner triples (outer triples, respectively) from the three decompositions form the set of triples of an STS of the same order. These decompositions are called trinal inner and trinal outer decompositions, respectively. We settle the existence question for trinal inner decompositions completely, and for trinal outer decompositions with two possible exceptions.     

Rigid Steiner Triple Systems Obtained from Projective Triple Systems

It was shown by Babai in 1980 that almost all Steiner triple systems are rigid; that is, their only automorphism is the identity permutation. Those Steiner triple systems with the largest automorphism groups are the projective systems of orders . In this paper, we show that each such projective system may be transformed to a rigid Steiner triple system by at most n Pasch trades whenever .     

Simple Signed Steiner Triple Systems

Let X be a v‐set, be a set of 3‐subsets (triples) of X, and be a partition of with . The pair is called a simple signed Steiner triple system, denoted by ST, if the number of occurrences of every 2‐subset of X in triples is one more than the number of occurrences in triples . In this paper, we prove that exists if and only if , , and , where and for , . © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 332–343, 2012     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

Large Cross‐Free Sets in Steiner Triple Systems

A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n.     

Well‐Balanced Designs for Data Placement

The problem we consider in this article is motivated by data placement, in particular data replication in distributed storage and retrieval systems. We are given a set V of v servers along with b files (data, documents). Each file is replicated on exactly k servers. A placement consists in finding a family of b subsets of V (representing the files) called blocks, each of size k. Each server has some probability to fail and we want to find a placement that minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well‐balanced design—that is, a family of blocks—each of size k, such that each j‐element subset of V, , belongs to the same or almost the same number of blocks (difference at most one). The existence of well‐balanced designs is a difficult problem as it contains, as a subproblem, the existence of Steiner systems. We completely solve the case and give bounds and constructions for and some values of v and b.     

Sequencing partial Steiner triple systems

A partial Steiner triple system of order $n$ is sequenceable if there is a sequence of length $n$ of its distinct points such that no proper segment of the sequence is a union of point‐disjoint blocks. We prove that if a partial Steiner triple system has at most three point‐disjoint blocks, then it is sequenceable.     

Overlap Cycles for Steiner Quadruple Systems

Steiner quadruple systems are set systems in which every triple is contained in a unique quadruple. It is well known that Steiner quadruple systems of order v, or SQS(v), exist if and only if . Universal cycles, introduced by Chung, Diaconis, and Graham in 1992, are a type of cyclic Gray code. Overlap cycles are generalizations of universal cycles that were introduced in 2010 by Godbole, et al. Using Hanani's SQS constructions, we show that for every with there exists an SQS(v) that admits a 1‐overlap cycle.     

Dimension of the space generated by Steiner systems

To every Steiner system with parameters on and blocks , we can assign its characteristic vector , which is a ‐vector whose entries are indexed by the ‐subsets of such that for each ‐subset of if and only if . In this paper, we show that the dimension of the vector space generated by all of the characteristic vectors of Steiner systems with parameters is , provided that and there is at least one such system.     

On the maximum double independence number of Steiner triple systems

The maximum independence number of Steiner triple systems of order $v$ is well‐known. Motivated by questions of access balancing in storage systems, we determine the maximum total cardinality of a pair of disjoint independent sets of Steiner triple systems of order $v$ for all admissible orders.     

An Infinite Family of Steiner Systems from Cyclic Codes

Steiner systems are a fascinating topic of combinatorics. The most studied Steiner systems are (Steiner triple systems), (Steiner quadruple systems), and . There are a few infinite families of Steiner systems in the literature. The objective of this paper is to present an infinite family of Steiner systems for all from cyclic codes. As a by‐product, many infinite families of 2‐designs are also reported in this paper.     

4‐*GDD(6n)s and Related Optimal Quaternary Constant‐Weight Codes

Constant‐weight codes (CWCs) have played an important role in coding theory. To construct CWCs, a K‐GDD (where GDD is group divisible design) with the “star” property, denoted by K‐*GDD, was introduced, in which any two intersecting blocks intersect in at most two common groups. In this paper, we consider the existence of 4‐*GDDs. Previously, the necessary conditions for existence were shown to be sufficient for , and also sufficient for with prime powers and . We continue to investigate the existence of 4‐*GDD(6ⁿ)s and show that the necessary condition for the existence of a 4‐*GDD(6ⁿ), namely, , is also sufficient. The known results on the existence of optimal quaternary (n, 5, 4) CWCs are also extended.     

Coloring Cubic Graphs by Point‐Intransitive Steiner Triple Systems

An ‐coloring of a cubic graph G is an edge coloring of G by points of a Steiner triple system such that the colors of any three edges meeting at a vertex form a block of . A Steiner triple system that colors every simple cubic graph is said to be universal. It is known that every nontrivial point‐transitive Steiner triple system that is neither projective nor affine is universal. In this article, we present the following results.

相似文献   

On the Existence of Friendship Hypergraphs

A 3‐uniform friendship hypergraph is a 3‐uniform hypergraph in which, for all triples of vertices x, y, z there exists a unique vertex w, such that , and are edges in the hypergraph. Sós showed that such 3‐uniform friendship hypergraphs on n vertices exist with a so‐called universal friend if and only if a Steiner triple system, exists. Hartke and Vandenbussche used integer programming to search for 3‐uniform friendship hypergraphs without a universal friend and found one on 8, three nonisomorphic on 16 and one on 32 vertices. So far, these five hypergraphs are the only known 3‐uniform friendship hypergraphs. In this paper we construct an infinite family of 3‐uniform friendship hypergraphs on 2^k vertices and edges. We also construct 3‐uniform friendship hypergraphs on 20 and 28 vertices using a computer. Furthermore, we define r‐uniform friendship hypergraphs and state that the existence of those with a universal friend is dependent on the existence of a Steiner system, . As a result hereof, we know infinitely many 4‐uniform friendship hypergraphs with a universal friend. Finally we show how to construct a 4‐uniform friendship hypergraph on 9 vertices and with no universal friend.     

Tight Heffter Arrays Exist for all Possible Values

A tight Heffter array is an matrix with nonzero entries from such that (i) the sum of the elements in each row and each column is 0, and (ii) no element from appears twice. We prove that exist if and only if both m and n are at least 3. If H has the property that all entries are integers of magnitude at most , every row and column sum is 0 over the integers, and H also satisfies ), we call H an integer Heffter array. We show integer Heffter arrays exist if and only if . Finally, an integer Heffter array is shiftable if each row and column contains the same number of positive and negative integers. We show that shiftable integer arrays exists exactly when both are even.     

A Direct Construction of Nontransitive Dice Sets

In this paper, we give a direct construction for a set of dice realizing any given tournament T. The construction for a tournament with n vertices requires dice with n sides if n is odd, sides if n is divisible by 4, and sides if mod 4. This appears to be the most efficient general construction to date. Our construction relies only on a standard construction from graph theory.     

Some New Infinite Classes of Candelabra Quadruple Systems

Candelabra quadruple systems (CQS) were first introduced by Hanani who used them to determine the existence of Steiner quadruple systems. In this paper, a new method has been developed by constructing partial candelabra quadruple systems with odd group size, which is a generalization of the even cases, to complete a design. New results of candelabra quadruple systems have been obtained, i.e. we show that for any , there exists a CQS for all , and .