Cycle structures of automorphisms of 2-(v,k,1) designs

An automorphism of a 2?(v,k, 1) design acts as a permutation of the points and as another of the blocks. We show that the permutation of the blocks has at least as many cycles, of lengths n > k, as the permutation of the points. Looking at Steiner triple systems we show that this holds for all n unless n|Cp(n)| ? 3, where Cp(n) is the set of cycles of length n of the automorphism in its action on the points. Examples of Steiner triple systems for each of these exceptions are given. Considering designs with infinitely many points, but with k finite, we show that these results generalize. © 1995 John Wiley & Sons, Inc.     

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.     

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     

Graph factorization,general triple systems,and cyclic triple systems

In this self-contained exposition, results are developed concerning one-factorizations of complete graphs, and incidence matrices are used to turn these factorization results into embedding theorems on Steiner triple systems. The result is a constructive graphical proof that a Steiner triple system exists for any order congruent to 1 or 3 modulo 6. A pairing construction is then introduced to show that one can also obtain triple systems which are cyclically generated.     

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 .     

A Steiner triple system which colors all cubic graphs

We prove that there is a Steiner triple system ?? such that every simple cubic graph can have its edges colored by points of ?? in such a way that for each vertex the colors of the three incident edges form a triple in ??. This result complements the result of Holroyd and ?koviera that every bridgeless cubic graph admits a similar coloring by any Steiner triple system of order greater than 3. The Steiner triple system employed in our proof has order 381 and is probably not the smallest possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 15–24, 2004     

Steiner Triple Systems,Pinched Surfaces,and Complete Multigraphs

We consider complete multigraphs \({K_n^m}\) on n vertices with every pair joined by m edges. We embed these graphs to triangulate \({S_n^k}\) , a pinched surface with n pinch points each having k sheets. These embeddings have a vertex at each pinch point and any two sheets at a pinch point have the same number of edges. Moreover, we want to 2m-color the faces such that each color class is a Steiner triple system. These embeddings generalize in two ways biembeddings of Steiner triple systems, the case m =  1, k =  1 of simple graphs in surfaces without pinch points.     

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.     

Disjoint finite partial steiner triple systems can be embedded in disjoint finite steiner triple systems

This paper shows that a pair of disjoint finite partial Steiner triple systems can be embedded in a pair of disjoint finite Steiner triple systems.     

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.     

Anti-mitre steiner triple systems

A mitre in a Steiner triple system is a set of five triples on seven points, in which two are disjoint. Recursive constructions for Steiner triple systems containing no mitre are developed, leading to such anti-mitre systems for at least 9/16 of the admissible orders. Computational results for small cyclic Steiner triple systems are also included.     

On sets of pairwise disjoint blocks in Steiner triple systems

In a Steiner triple system with 19 points, each disjoint pair blocks is contained in at least 43 quadruplets of pairwise disjoint blocks. In a Steiner triple system with 25 points, each disjoint pair of blocks is contained in a pairwise disjoint quintuple of blocks. Theorems used are those of Connor on determinants based on intersecting and nonintersecting blocks of a BIBD, and of Turán on extremal graphs without triangles.     

Linearly Derived Steiner Triple Systems

We attach a graph to every Steiner triple system. The chromatic number of this graph is related to the possibility of extending the triple system to a quadruple system. For example, the triple systems with chromatic number one are precisely the classical systems of points and lines of a projective geometry over the two-element field, the Hall triple systems have chromatic number three (and, as is well-known, are extendable) and all Steiner triple systems whose graph has chromatic number two are extendable. We also give a configurational characterization of the Hall triple systems in terms of mitres.     

On the maximal number of pairwise orthogonal Steiner triple systems

For some time it has been known that for prime powers p^k = 1 + 3 · 2^st there exists a pair of orthogonal Steiner triple systems of order p^k. In fact, such a pair can be constructed using the method of Mullin and Nemeth for constructing strong starters. We use a generalization of the construction of Mullin and Nemeth to construct sets of mutually orthogonal Steiner triple systems for many of these prime powers. By using other techniques we show that a set of mutually orthogonal Steiner triple systems of any given size can be constructed for all but a finite number of such prime powers.     

On the Steiner quadruple systems of small rank which are embeddable into extended perfect binary codes

The codewords of weight 4 of every extended perfect binary code that contains the all-zero vector are known to form a Steiner quadruple system. We propose a modification of the Lindner construction for the Steiner quadruple system of order N = 2 ^r which can be described by special switchings from the Hamming Steiner quadruple system. We prove that each of these Steiner quadruple systems is embedded into some extended perfect binary code constructed by the method of switching of ijkl-components from the binary extended Hamming code. We give the lower bound for the number of different Steiner quadruple systems of order N with rank at most N ? logN + 1 which are embedded into extended perfect codes of length N.     

Johnson type bounds on constant dimension codes

Very recently, an operator channel was defined by Koetter and Kschischang when they studied random network coding. They also introduced constant dimension codes and demonstrated that these codes can be employed to correct errors and/or erasures over the operator channel. Constant dimension codes are equivalent to the so-called linear authentication codes introduced by Wang, Xing and Safavi-Naini when constructing distributed authentication systems in 2003. In this paper, we study constant dimension codes. It is shown that Steiner structures are optimal constant dimension codes achieving the Wang-Xing-Safavi-Naini bound. Furthermore, we show that constant dimension codes achieve the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures. Then, we derive two Johnson type upper bounds, say I and II, on constant dimension codes. The Johnson type bound II slightly improves on the Wang-Xing-Safavi-Naini bound. Finally, we point out that a family of known Steiner structures is actually a family of optimal constant dimension codes achieving both the Johnson type bounds I and II.      

Characterization of affine Steiner triple systems and Hall triple systems

It is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration C₁₄. We find three configurations such that a Steiner triple system is affine if and only if it does not contain any of these configurations. Similarly, we characterize Hall triple systems, a superclass of affine Steiner triple systems, using two forbidden configurations.     

Steiner triple systems with block-transitive automorphism groups

This paper describes the Steiner triple systems which have automorphism groups acting transitively on the blocks but not doubly transitively on the points. In the case of those systems not previously described, there is a group acting regularly on the blocks and the number of points is a prime power congruent to 7 modulo 12. A formula yielding the number (up to isomorphism) of these systems with a given number of points is derived.