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.     

Extremal problems for triple systems

In this article Turán-type problems for several triple systems arising from (k, k ? 2)-configurations [i.e. (k ? 2) triples on k vertices] are considered. It will be shown that every Steiner triple system contains a (k, k ? 2)-configuration for some k < c log n/ log log n. Moreover, the Turán numbers of (k, k ? 2)-trees are determined asymptotically to be ((k ? 3)/3).(ⁿ₂) (1?o(1)). Finally, anti-Pasch hypergraphs avoiding (5, 3) -and (6, 4)-Configurations are considered. © 1993 John Wiley & Sons, Inc.     

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.     

Ubiquitous configurations in Steiner triple systems

A Steiner triple system S is a C-ubiquitous (where C is a configuration) if every line of S is contained in a copy of C, and is n-ubiquitous if it is C-ubiquitous for every n-line configuration C. We determine the spectrum of 4-ubiquitous Steiner triple systems as well as the spectra of C-ubiquitous Steiner triple systems for all configurations C with five lines. © 1997 John Wiley & Sons, Inc.     

On cliques in spanning graphs of projective Steiner triple systems

We are interested in the sizes of cliques that are to be found in any arbitrary spanning graph of a Steiner triple system 𝒮. In this paper we investigate spanning graphs of projective Steiner triple systems, proving, not surprisingly, that for any positive integer k and any sufficiently large projective Steiner triple system 𝒮, every spanning graph of 𝒮 contains a clique of size k. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 157–165, 2000     

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     

Large sets with holes

We study large sets of disjoint Steiner triple systems “with holes”. The purpose of these structures is to extend the use of large sets of disjoint Steiner triple systems in the construction of various other large set type structures to values of v for which no Steiner triple system of order v exists, i.e., v ≡ 0, 2, 4, or 5 (mod 6). We give constructions for all of these congruence classes. We describe several applications, including applications to large sets of disjoint group divisible designs and to large sets of disjoint separable ordered designs. © 1993 John Wiley & Sons, Inc.     

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.     

Steiner polygons in the Steiner problem

A polygon, whose vertices are points in a given setA ofn points, is defined to be a Steiner polygon ofA if all Steiner minimal trees forA lie in it. Cockayne first found that a Steiner polygon can be obtained by repeatedly deleting triangles from the boundary of the convex hull ofA. We generalize this concept and give a method to construct Steiner polygons by repeatedly deletingk-gons,k n. We also prove the uniqueness of Steiner polygons obtained by our method.     

A construction for large sets of disjoint Kirkman triple systems

A Steiner system S(t, k, v) is called i-resolvable, 0 < i < t, if its block set can be partitioned into S(i, k, v). In this paper, a 2-resolvable S(3, 4, v) is used to construct a large set of disjoint Kirkman triple systems of order 3v − 3 (briefly LKTS) and some new orders for LKTS are then obtained. Research supported by Tianyuan Mathematics Foundation of NSFC Grant 10526032 and Natural Science Foundation of Universities of Jiangsu Province Grant 05KJB110111.     

Self‐embeddings of cyclic and projective Steiner quasigroups

It is shown that for every admissible order v for which a cyclic Steiner triple system exists, there exists a biembedding of a cyclic Steiner quasigroup of order v with a copy of itself. Furthermore, it is shown that for each n≥2 the projective Steiner quasigroup of order 2ⁿ?1 has a biembedding with a copy of itself. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:16‐27, 2010     

Triple Systems are Eulerian

An Euler tour of a hypergraph (also called a rank‐2 universal cycle or 1‐overlap cycle in the context of designs) is a closed walk that traverses every edge exactly once. In this paper, using a graph‐theoretic approach, we prove that every triple system with at least two triples is eulerian, that is, it admits an Euler tour. Horan and Hurlbert have previously shown that for every admissible order >3, there exists a Steiner triple system with an Euler tour, while Dewar and Stevens have proved that every cyclic Steiner triple system of order >3 and every cyclic twofold triple system admits an Euler tour.     

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.     

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 skolem sequences and related disjoint structures

A Skolem sequence of order n is a sequence S = (s₁, s₂…, s²ⁿ) of 2n integers satisfying the following conditions: (1) for every k ∈ {1, 2,… n} there exist exactly two elements s_i,S_j such that S_i = S_j = k; (2) If s_i = s_j = k,i < j then j ? i = k. In this article we show the existence of disjoint Skolem, disjoint hooked Skolem, and disjoint near-Skolem sequences. Then we apply these concepts to the existence problems of disjoint cyclic Steiner and Mendelsohn triple systems and the existence of disjoint 1-covering designs. © 1993 John Wiley & Sons, Inc.     

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.     

Doubling and Tripling Constructions for Defining Sets in Steiner Triple Systems

 A minimal defining set of a Steiner triple system on v points (STS(v)) is a partial Steiner triple system contained in only this STS(v), and such that any of its proper subsets is contained in at least two distinct STS(v)s. We consider the standard doubling and tripling constructions for STS(2v+1) and STS(3v) from STS(v) and show how minimal defining sets of an STS(v) gives rise to minimal defining sets in the larger systems. We use this to construct some new families of defining sets. For example, for Steiner triple systems on 3 ⁿ points, we construct minimal defining sets of volumes varying by as much as 7 ⁿ⁻² . Received: September 16, 2000 Final version received: September 13, 2001 RID="*" ID="*" Research supported by the Australian Research Council A49937047, A49802044     

Steiner triple systems satisfying the 4-vertex condition

Higman asked which block graphs of Steiner triple systems of order v satisfy the 4-vertex condition and left the cases v = 9, 13, 25 unsettled.We give a complete answer to this question by showing that the affine plane of order 3 and the binary projective spaces are the only such systems. The major part of the proof is to show that no block graph of a Steiner triple system of order 25 satisfies the 4-vertex condition.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.