Large monochromatic components in 3‐edge‐colored Steiner triple systems

It is known that in any r‐coloring of the edges of a complete r‐uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on n vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3‐coloring of the edges? Gyárfás proved that $\left(2n+3\right)/3$ is an absolute lower bound and that this lower bound is best possible for infinitely many $n$. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually $\left(1?o\left(1\right)\right)n$. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest 3‐partite hole (ie, disjoint sets $X_1,X_2,X_3$ with $|X_1|=|X_2|=|X_3|$ such that no edge intersects all of $X_1,X_2,X_3$) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the structure of the Steiner triple system and the coloring of its edges are restricted in a certain way. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.     

Ramsey theory on Steiner triples

We call a partial Steiner triple system C (configuration) t‐Ramsey if for large enough n (in terms of $C,t$), in every t‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic copy of C. We prove that configuration C is t‐Ramsey for every t in three cases:

• C is acyclic
• every block of C has a point of degree one
• C has a triangle with blocks 123, 345, 561 with some further blocks attached at points 1 and 4

This implies that we can decide for all but one configurations with at most four blocks whether they are t‐Ramsey. The one in doubt is the sail with blocks 123, 345, 561, 147.     

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     

Holey Steiner pentagon systems

In this article, it is shown that the necessary conditions for the existence of a holey Steiner pentagon system (HSPS) of type hⁿ are also sufficient, except possibly for the following cases: (1) when n = 15, and h ≡ 1 or 5 (mod 6) where h ≢ 0 (mod 5), or h = 9; and (2) (h, n) ∈ {(6, 6), (6, 36), (15, 19), (15, 23), (15, 27), (30, 18), (30, 22), (30, 24)}. Moreover, the results of this article guarantee the analogous existence results for group divisible designs (GDDs) of type hⁿ with block-size k = 5 and index λ = 2. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 41–56, 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.     

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.     

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.     

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     

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     

Solving large Steiner Triple Covering Problems

Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to highly symmetric and computationally challenging set covering problems. The largest instance solved so far corresponds to a Steiner Tripe System of order 81. We present optimal solutions for systems of orders 135 and 243. These are computed by a tailored implementation of constraint orbital branching, a method designed to exploit symmetry in integer programs.     

Homogeneous and ultrahomogeneous Steiner systems

A Steiner system (or t — (v, k, 1) design) S is said to be homogeneous if, whenever the substructures induced on two finite subsets S₁ and S₂ of S are isomorphic, there is at least one automorphism of S mapping S₁ onto S₂, and is said to be ultrahomogeneous if each isomorphism between the substructures induced on two finite subsets of S can be extended to an automorphism of S. We give a complete classification of all homogeneous and ultrahomogeneous Steiner systems. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 153–161, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10034     

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.     

On the number of partial Steiner systems

We give a simple proof of the result of Grable on the asymptotics of the number of partial Steiner systems S(t,k,m). © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 347–352, 2000     

Nilpotent Steiner skeins with nilpotent derived Steiner loops

Armanious and Guelzow obtained the structure theorem of finite nilpotent Steiner skeins. Guelzow gave a construction of a Steiner skein of nilpotence class n with all its derived Steiner loops of nilpotence class 1. Armanious gave a construction for Steiner skeins of nilpotence class n with all its derived Steiner loops of nilpotence class n. In this article we survey the main results on nilpotent Steiner skeins and give a new and simple construction, in the form of polynomials, for Steiner skeins of nilpotence class n with all its derived Steiner loops of nilpotence class n. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 232–238, 2000     

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     

Steiner centers and Steiner medians of graphs

Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by d_G(S) or d(S). The Steiner n-eccentricity e_n(v) and Steiner n-distance d_n(v) of a vertex v in G are defined as e_n(v)=max{d(S)| SV(G), |S|=n and vS} and d_n(v)=∑{d(S)| SV(G), |S|=n and vS}, respectively. The Steiner n-center C_n(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median M_n(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597] showed that C_n(T) is contained in C_n+1(T) for all n2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249–258] showed that M_n(T) is contained in M_n+1(T) for all n2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258–263] asked whether these containment relationships hold for general graphs. In this note we show that for every n2 there is an infinite family of block graphs G for which C_n(G)C_n+1(G). We also show that for each n2 there is a distance–hereditary graph G such that M_n(G)M_n+1(G). Despite these negative examples, we prove that if G is a block graph then M_n(G) is contained in M_n+1(G) for all n2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described.     

Uniform two‐class regular partial Steiner triple systems

A 2‐class regular partial Steiner triple system is a partial Steiner triple system whose points can be partitioned into 2‐classes such that no triple is contained in either class and any two points belonging to the same class are contained in the same number of triples. It is uniform if the two classes have the same size. We provide necessary and sufficient conditions for the existence of uniform 2‐class regular partial Steiner triple systems.     

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.