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     

A conjecture on small embeddings of partial Steiner triple systems

A well‐known, and unresolved, conjecture states that every partial Steiner triple system of order u can be embedded in a Steiner triple system of order υ for all υ ≡ 1 or 3, (mod 6), υ ≥ 2u + 1. However, some partial Steiner triple systems of order u can be embedded in Steiner triple systems of order υ <2u + 1. A more general conjecture that considers these small embeddings is presented and verified for some cases. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 313–321, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10017     

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     

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     

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.     

The Fine Intersection Problem for Steiner Triple Systems

The intersection of two Steiner triple systems and is the set . The fine intersection problem for Steiner triple systems is to determine for each v, the set I(v), consisting of all possible pairs (m, n) such that there exist two Steiner triple systems of order v whose intersection satisfies and . We show that for v ≡ 1 or 3 (mod 6), |I(v)| = Θ(v ³), where previous results only imply that |I(v)| = Ω(v ²). Received: January 23, 2006. Final Version received: September 2, 2006     

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     

Generalized steiner triple systems with group size five

Generalized Steiner triple systems, GS(2, 3, n, g) are used to construct maximum constant weight codes over an alphabet of size g+1 with distance 3 and weight 3 in which each codeword has length n. The existence of GS(2, 3, n, g) has been solved for g=2, 3, 4, 9. In this paper, by introducing a special kind of holey generalized Steiner triple systems (denoted by HGS(2, 3, (n, u), g)), singular indirect product (SIP) construction for GDDs is used to construct generalized Steiner systems. The numerical necessary conditions for the existence of a GS(2, 3, n, g) are shown to be sufficient for g=5.     

Some rigid Steiner 5‐designs

Hitherto, all known non‐trivial Steiner systems S(5, k, v) have, as a group of automorphisms, either PSL(2, v−1) or PGL(2, (v−2)/2) × C₂. In this article, systems S(5, 6, 72), S(5, 6, 84) and S(5, 6, 108) are constructed that have only the trivial automorphism group. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:392–400, 2010     

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.     

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.     

Generalized Steiner systems with block size three and group size g ≡ 3(mod 6)

Generalized Steiner Systems, GS(2, 3, n, g), are equivalent to maximum constant weight codes over an alphabet of size g + 1 with distance 3 and weight 3 in which each codeword has length n. We construct Generalized Steiner Triple Systems, GS(2, 3, n, g), when g ≡ 3(mod 6). © 1997 John Wiley & Sons, Inc. J Combin Designs 5:417–432, 1997     

A lower bound on the number of Semi‐Boolean quadruple systems

A Steiner quadruple system of order 2ⁿ is Semi‐Boolean (SBQS(2ⁿ) in short) if all its derived triple systems are isomorphic to the point‐line design associated with the projective geometry PG(n?1, 2). We prove by means of explicit constructions that for any n, up to isomorphism, there exist at least 2^{? 3(n?4)/2?} regular and resolvable SBQS(2ⁿ). © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 229–239, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10050     

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.     

The combinatorial game Nofil played on Steiner triple systems

We introduce an impartial combinatorial game on Steiner triple systems called Next One to Fill Is the Loser (Nofil ). Players move alternately, choosing points of the triple system. If a player is forced to fill a block on their turn, they lose. By computing nim-values, we determine optimal strategies for Nofil on all Steiner triple systems up to order 15 and a sampling for orders 19, 21 and 25. The game Nofil can be thought of in terms of play on a corresponding hypergraph which will become a graph during play. At that point Nofil is equivalent to playing the game Node Kayles on the graph. We prove necessary conditions and sufficient conditions for a graph to reached playing Nofil. We conclude that the complexity of determining the outcome of the game Nofil on Steiner triple systems is PSPACE-complete for randomized reductions.     

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.

相似文献   

A construction of mutually disjoint Steiner systems from isomorphic Golay codes

It is well known that the extended binary Golay [24,12,8] code yields 5-designs. In particular, the supports of all the weight 8 codewords in the code form a Steiner system S(5,8,24). In this paper, we give a construction of mutually disjoint Steiner systems S(5,8,24) by constructing isomorphic Golay codes. As a consequence, we show that there exists at least 22 mutually disjoint Steiner systems S(5,8,24). Finally, we prove that there exists at least 46 mutually disjoint 5-(48,12,8) designs from the extended binary quadratic residue [48,24,12] code.     

Pasch trades with a negative block

A Steiner triple system of order v, STS(v), may be called equivalent to another STS(v) if one can be converted to the other by a sequence of three simple operations involving Pasch trades with a single negative block. It is conjectured that any two STS(v)s on the same base set are equivalent in this sense. We prove that the equivalence class containing a given system S on a base set V contains all the systems that can be obtained from S by any sequence of well over one hundred distinct trades, and that this equivalence class contains all isomorphic copies of S on V. We also show that there are trades which cannot be effected by means of Pasch trades with a single negative block.     

On the Binary Codes of Steiner Triple Systems

The binary code spanned by the rows of the point byblock incidence matrix of a Steiner triple system STS(v)is studied. A sufficient condition for such a code to containa unique equivalence class of STS(v)'s of maximalrank within the code is proved. The code of the classical Steinertriple system defined by the lines in PG(n-1,2)(n3), or AG(n,3) (n3) is shown to contain exactly v codewordsof weight r=(v-1)/2, hence the system is characterizedby its code. In addition, the code of the projective STS(2ⁿ-1)is characterized as the unique (up to equivalence) binary linearcode with the given parameters and weight distribution. In general,the number of STS(v)'s contained in the code dependson the geometry of the codewords of weight r. Itis demonstrated that the ovals and hyperovals of the definingSTS(v) play a crucial role in this geometry. Thisrelation is utilized for the construction of some infinite classesof Steiner triple systems without ovals.     

There exist Steiner triple systems of order 15 that do not occur in a perfect binary one‐error‐correcting code

The codewords at distance three from a particular codeword of a perfect binary one‐error‐correcting code (of length 2^m?1) form a Steiner triple system. It is a longstanding open problem whether every Steiner triple system of order 2^m?1 occurs in a perfect code. It turns out that this is not the case; relying on a classification of the Steiner quadruple systems of order 16 it is shown that the unique anti‐Pasch Steiner triple system of order 15 provides a counterexample. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 465–468, 2007