Steiner triple systems with two disjoint subsystems

It is shown that there exists a triangle decomposition of the graph obtained from the complete graph of order v by removing the edges of two vertex disjoint complete subgraphs of orders u and w if and only if u,w, and v are odd, (mod 3), and . Such decompositions are equivalent to group divisible designs with block size 3, one group of size u, one group of size w, and v – u – w groups of size 1. This result settles the existence problem for Steiner triple systems having two disjoint specified subsystems, thereby generalizing the well‐known theorem of Doyen and Wilson on the existence of Steiner triple systems with a single specified subsystem. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Steiner triple systems with disjoint or intersecting subsystems

The existence of incomplete Steiner triple systems of order υ having holes of orders w and u meeting in z elements is examined, with emphasis on the disjoint (z = 0) and intersecting (z = 1) cases. When and , the elementary necessary conditions are shown to be sufficient for all values of z. Then for and υ “near” the minimum of , the conditions are again shown to be sufficient. Consequences for larger orders are also discussed, in particular the proof that when one hole is at least three times as large as the other, the conditions are again sufficient. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 58–77, 2000     

Kirkman triple systems of order 21 with nontrivial automorphism group

There are 50,024 Kirkman triple systems of order 21 admitting an automorphism of order 2. There are 13,280 Kirkman triple systems of order 21 admitting an automorphism of order 3. Together with the 192 known systems and some simple exchange operations, this leads to a collection of 63,745 nonisomorphic Kirkman triple systems of order 21. This includes all KTS(21)s having a nontrivial automorphism group. None of these is doubly resolvable. Four are quadrilateral-free, providing the first examples of such a KTS(21).

     

The Steiner triple systems of order 19

Using an orderly algorithm, the Steiner triple systems of order are classified; there are pairwise nonisomorphic such designs. For each design, the order of its automorphism group and the number of Pasch configurations it contains are recorded; of the designs are anti-Pasch. There are three main parts of the classification: constructing an initial set of blocks, the seeds; completing the seeds to triple systems with an algorithm for exact cover; and carrying out isomorph rejection of the final triple systems. Isomorph rejection is based on the graph canonical labeling software nauty supplemented with a vertex invariant based on Pasch configurations. The possibility of using the (strongly regular) block graphs of these designs in the isomorphism tests is utilized. The aforementioned value is in fact a lower bound on the number of pairwise nonisomorphic strongly regular graphs with parameters .

     

Perfect dexagon triple systems with given subsystems

The graph consisting of the six triples (or triangles) {a,b,c}, {c,d,e}, {e,f,a}, {x,a,y}, {x,c,z}, {x,e,w}, where a,b,c,d,e,f,x,y,z and w are distinct, is called a dexagon triple. In this case the six edges {a,c}, {c,e}, {e,a}, {x,a}, {x,c}, and {x,e} form a copy of K₄ and are called the inside edges of the dexagon triple. A dexagon triple system of order v is a pair (X,D), where D is a collection of edge disjoint dexagon triples which partitions the edge set of 3K_v. A dexagon triple system is said to be perfect if the inside copies of K₄ form a block design. In this note, we investigate the existence of a dexagon triple system with a subsystem. We show that the necessary conditions for the existence of a dexagon triple system of order v with a sub-dexagon triple system of order u are also sufficient.     

Some new perfect Steiner triple systems

In a Steiner triple system STS(v) = (V, B), for each pair {a, b} ⊂ V, the cycle graph G_a,b can be defined as follows. The vertices of G_a,b are V \ {a, b, c} where {a, b, c} ∈ B. {x, y} is an edge if either {a, x, y} or {b, x, y} ∈ B. The Steiner triple system is said to be perfect if the cycle graph of every pair is a single (v − 3)-cycle. Perfect STS(v) are known only for v = 7, 9, 25, and 33. We construct perfect STS (v) for v = 79, 139, 367, 811, 1531, 25771, 50923, 61339, and 69991. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 327–330, 1999     

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.     

On 6-sparse Steiner triple systems

We give the first known examples of 6-sparse Steiner triple systems by constructing 29 such systems in the residue class 7 modulo 12, with orders ranging from 139 to 4447. We then present a recursive construction which establishes the existence of 6-sparse systems for an infinite set of orders. Observations are also made concerning existing construction methods for perfect Steiner triple systems, and we give a further example of such a system. This has order 135,859 and is only the fourteenth known. Finally, we present a uniform Steiner triple system of order 180,907.     

Quasi‐embeddings of Steiner triple systems,or Steiner triple systems of different orders with maximum intersection

In this paper, we present a conjecture that is a common generalization of the Doyen–Wilson Theorem and Lindner and Rosa's intersection theorem for Steiner triple systems. Given u, v ≡ 1,3 (mod 6), u < v < 2u + 1, we ask for the minimum r such that there exists a Steiner triple system such that some partial system can be completed to an STS , where |?| = r. In other words, in order to “quasi‐embed” an STS(u) into an STS(v), we must remove r blocks from the small system, and this r is the least such with this property. One can also view the quantity (u(u ? 1)/6) ? r as the maximum intersection of an STS(u) and an STS(v) with u < v. We conjecture that the necessary minimum r = (v ? u) (2u + 1 ? v)/6 can be achieved, except when u = 6t + 1 and v = 6t + 3, in which case it is r = 3t for t ≠ 2, or r = 7 when t = 2. Using small examples and recursion, we solve the cases v ? u = 2 and 4, asymptotically solve the cases v ? u = 6, 8, and 10, and further show for given v ? u > 2 that an asymptotic solution exists if solutions exist for a run of consecutive values of u (whose required length is no more than v ? u). Some results are obtained for v close to 2u + 1 as well. The cases where ≈ 3u/2 seem to be the hardest. © 2004 Wiley Periodicals, Inc.     

A proof of Lindner's conjecture on embeddings of partial Steiner triple systems

Lindner's conjecture that any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v if and is proved. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 63–89, 2009     

The Steiner quadruple systems of order 16

The Steiner quadruple systems of order 16 are classified up to isomorphism by means of an exhaustive computer search. The number of isomorphism classes of such designs is 1,054,163. Properties of the designs—including the orders of the automorphism groups and the structures of the derived Steiner triple systems of order 15—are tabulated. A consistency check based on double counting is carried out to gain confidence in the correctness of the classification.     

Minimum embedding of Steiner triple systems into -designs I

A (K₄-e)-design on v+w points embeds a Steiner triple system (STS) if there is a subset of v points on which the graphs of the design induce the blocks of a STS. It is established that wv/3, and that when equality is met that such a minimum embedding of an STS(v) exists, except when v=15.     

On sparse countably infinite Steiner triple systems

We give a general construction for Steiner triple systems on a countably infinite point set and show that it yields 2 ${}^{\text{?}{}_{\text{0}}}$ nonisomorphic systems all of which are uniform and r‐sparse for all finite r?4. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 115–122, 2010     

Embedding Steiner triple systems in hexagon triple systems

A hexagon triple is the graph consisting of the three triangles (triples) {a,b,c},{c,d,e}, and {e,f,a}, where a,b,c,d,e, and f are distinct. The triple {a,c,e} is called an inside triple. A hexagon triple system of order n is a pair (X,H) where H is a collection of edge disjoint hexagon triples which partitions the edge set of K_n with vertex set X. The inside triples form a partial Steiner triple system. We show that any Steiner triple system of order n can be embedded in the inside triples of a hexagon triple system of order approximately 3n.     

On list coloring Steiner triple systems

We study the list chromatic number of Steiner triple systems. We show that for every integer s there exists n₀=n₀(s) such that every Steiner triple system on n points STS(n) with n≥n₀ has list chromatic number greater than s. We also show that the list chromatic number of a STS(n) is always within a log n factor of its chromatic number. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 314–322, 2009     

Doyen–Wilson theorem for nested Steiner triple systems

The obvious necessary conditions for the existence of a nested Steiner triple system of order v containing a nested subsystem of order w are v ≥ 3w + 4 and v ≡ w ≡ 1 (mod 6). We show that these conditions are also sufficient. © 2004 Wiley Periodicals, Inc.     

Embedding partial Steiner triple systems so that their automorphisms extend

It is shown that there is a function g on the natural numbers such that a partial Steiner triple system U on u points can be embedded in a Steiner triple system V on ν points, in such a way that all automorphisms of U can be extended to V, for every admissible ν satisfying ν > g(u). We find exponential upper and lower bounds for g. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

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.     

Constructions for anti‐mitre Steiner triple systems

In this paper, we present a recursive construction for anti‐mitre Steiner triple systems. Furthermore, we present another construction of anti‐mitre STSs by utilizing 5‐sparse ones. © 2004 Wiley Periodicals, Inc.