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.     

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.

相似文献   

Cyclic bi‐embeddings of Steiner triple systems on 12s + 7 points

A cyclic face 2‐colourable triangulation of the complete graph K_n in an orientable surface exists for n ≡ 7 (mod 12). Such a triangulation corresponds to a cyclic bi‐embedding of a pair of Steiner triple systems of order n, the triples being defined by the faces in each of the two colour classes. We investigate in the general case the production of such bi‐embeddings from solutions to Heffter's first difference problem and appropriately labelled current graphs. For n = 19 and n = 31 we give a complete explanation for those pairs of Steiner triple systems which do not admit a cyclic bi‐embedding and we show how all non‐isomorphic solutions may be identified. For n = 43 we describe the structures of all possible current graphs and give a more detailed analysis in the case of the Heawood graph. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 92–110, 2002; DOI 10.1002/jcd.10001     

Orientable biembeddings of cyclic Steiner triple systems from current assignments on Möbius ladder graphs

We give a characterization of a current assignment on the bipartite Möbius ladder graph with 2n+1 rungs. Such an assignment yields an index one current graph with current group Z_12n+7 that generates an orientable face 2-colorable triangular embedding of the complete graph K_12n+7 or, equivalently, an orientable biembedding of two cyclic Steiner triple systems of order 12n+7. We use our characterization to construct Skolem sequences that give rise to such current assignments. These produce many nonisomorphic orientable biembeddings of cyclic Steiner triple systems of order 12n+7.     

Edge-colorings of cubic graphs with elements of point-transitive Steiner triple systems

A cubic graph G is S-edge-colorable for a Steiner triple system S if its edges can be colored with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. We show that a cubic graph is S-edge-colorable for every non-trivial affine Steiner triple system S unless it contains a well-defined obstacle called a bipartite end. In addition, we show that all cubic graphs are S-edge-colorable for every non-projective non-affine point-transitive Steiner triple system S.     

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.     

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.     

Codes and Anticodes in the Grassman Graph

Perfect codes and optimal anticodes in the Grassman graph G_q(n, k) are examined. It is shown that the vertices of the Grassman graph cannot be partitioned into optimal anticodes, with a possible exception when n=2k. We further examine properties of diameter perfect codes in the graph. These codes are known to be similar to Steiner systems. We discuss the connection between these systems and “real” Steiner systems.     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

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     

The Cycle Switching Graph of the Steiner Triple Systems of Order 19 is Connected

Switching is a local transformation that when applied to a combinatorial object gives another object with the same parameters. It is here shown that the cycle switching graph of the 11 084 874 829 isomorphism classes of Steiner triple systems of order 19 as well as the cycle switching graph of the 1 348 410 350 618 155 344 199 680 000 labeled such designs are connected. In addition to giving an understanding of the multitude of Steiner triple systems—at least for order 19 but perhaps also generally—this work also presents an algorithm for testing connectedness of large implicit graphs and brings forward a benchmark instance for such algorithms.     

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     

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     

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.     

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.     

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     

Semiboolean SQS-skeins

We will present a counter example to the conjecture that the class of boolean SQS-skeins is defined by the equation q(x, u, q(y, u, z)) = q(q(x, u, y), u, z ). The SQS-skeins satisfying this equation will be seen to be exactly those SQS-skeins that correspond to Steiner quadruple systems whose derived Steiner triple systems are all projective geometries.     

The use of hill-climbing to construct orthogonal steiner triple systems

In a related article, Colbourn, Gibbons, Mathon, Mullin, and Rosa [7] have shown that a pair of orthogonal Steiner triple systems exists for all v ≡ 1, 3 (mod 6), v ≥ 7 and v ≠ 9. This result is based on the construction of a finite set of pairs of orthogonal Steiner triple systems followed by the application of recursive constructions to settle the remaining undecided cases. In this article we report on the computational aspects of that investigation, and in particular the remarkable success of the hill-climbing method. © 1993 John Wiley & Sons, Inc.     

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.