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.     

Generalized Steiner systems GS4 (2, 4, v,g) for g = 2, 3, 6

Generalized Steiner systems GS_d(t, k, v, g) were first introduced by Etzion and used to construct optimal constant‐weight codes over an alphabet of size g + 1 with minimum Hamming distance d, in which each codeword has length v and weight k. Much work has been done for the existence of generalized Steiner triple systems GS(2, 3, v, g). However, for block size four there is not much known on GS_d(2, 4, v, g). In this paper, the necessary conditions for the existence of a GS_d(t, k, v, g) are given, which answers an open problem of Etzion. Some singular indirect product constructions for GS_d(2, k, v, g) are also presented. By using both recursive and direct constructions, it is proved that the necessary conditions for the existence of a GS₄(2, 4, v, g) are also sufficient for g = 2, 3, 6. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 401–423, 2001     

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     

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.     

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.     

4‐*GDDs(3n) and generalized Steiner systems GS(2, 4, v, 3)

Generalized Steiner systems GS(2, k, v, g) were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g + 1 with minimum Hamming distance 2k ? 3, in which each codeword has length v and weight k. As to the existence of a GS(2, k, v, g), a lot of work has been done for k = 3, while not so much is known for k = 4. The notion k‐*GDD was first introduced and used to construct GS(2, 3, v, 6). In this paper, singular indirect product (SIP) construction for GDDs is modified to construct GS(2, 4, v, g) via 4‐*GDDs. Furthermore, it is proved that the necessary conditions for the existence of a 4‐*GDD(3ⁿ), namely, n ≡ 0, 1 (mod 4) and n ≥ 8 are also sufficient. The known results on the existence of a GS(2, 4, v, 3) are then extended. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 381–393, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10047     

On semi-planar Steiner quasigroups

A Steiner triple system (briefly ST) is in 1-1 correspondence with a Steiner quasigroup or squag (briefly SQ) [B. Ganter, H. Werner, Co-ordinatizing Steiner systems, Ann. Discrete Math. 7 (1980) 3-24; C.C. Lindner, A. Rosa, Steiner quadruple systems: A survey, Discrete Math. 21 (1979) 147-181]. It is well known that for each n≡1 or 3 (mod 6) there is a planar squag of cardinality n [J. Doyen, Sur la structure de certains systems triples de Steiner, Math. Z. 111 (1969) 289-300]. Quackenbush expected that there should also be semi-planar squags [R.W. Quackenbush, Varieties of Steiner loops and Steiner quasigroups, Canad. J. Math. 28 (1976) 1187-1198]. A simple squag is semi-planar if every triangle either generates the whole squag or the 9-element squag. The first author has constructed a semi-planar squag of cardinality 3n for all n>3 and n≡1 or 3 (mod 6) [M.H. Armanious, Semi-planar Steiner quasigroups of cardinality 3n, Australas. J. Combin. 27 (2003) 13-27]. In fact, this construction supplies us with semi-planar squags having only nontrivial subsquags of cardinality 9. Our aim in this article is to give a recursive construction as n→3n for semi-planar squags. This construction permits us to construct semi-planar squags having nontrivial subsquags of cardinality >9. Consequently, we may say that there are semi-planar (or semi-planar ) for each positive integer m and each n≡1 or 3 (mod 6) with n>3 having only medial subsquags at most of cardinality 3^ν (sub-) for each ν∈{1,2,…,m+1}.     

Existence of Generalized Steiner Systems <Emphasis Type="Italic">GS</Emphasis>(2,4,ν,2)

Generalized Steiner systems GS(2,4,v,2) were first discussed by Etzion and used to construct optimal constant weight codes over an alphabet of size three with minimum Hamming distance five, in which each codeword has length v and weight four. Etzion conjectured its existence for any integer v 7 and v 1(mod 3). The conjecture has been verified for prime powers v > 7 and v 7(mod 12) by the latter two of the present authors. It has also been pointed out that there does not exist a GS(2,4,7,2). In this paper, constructions using frame generalized Steiner systems, two holey perfect bases and orthogonal Latin squares are discussed. With these constructions the conjecture is confirmed with the exception for v=7 and three possible exceptions for v 13, 52, 58.AMS classification: 05B05, 94B25     

Constructions for generalized Steiner systems <Emphasis Type="Italic">GS</Emphasis>(3, 4, <Emphasis Type="Italic">v</Emphasis>, 2)

Generalized Steiner systems GS (3, 4, v, 2) were first discussed by Etzion and used to construct optimal constant weight codes over an alphabet of size three with minimum Hamming distance three, in which each codeword has length v and weight four. Not much is known for GS (3, 4, v, 2)s except for a recursive construction and two small designs for v = 8,10 given by Etzion. In this paper, more small designs are found by computer search and also given are direct constructions based on finite fields and rotational Steiner quadruple systems and recursive constructions using three-wise balanced designs. Some infinite families are also obtained.      

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     

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     

A Construction of Almost Steiner Systems

Let n, k, and t be integers satisfying . A Steiner system with parameters t, k, and n is a k‐uniform hypergraph on n vertices in which every set of t distinct vertices is contained in exactly one edge. An outstanding problem in Design Theory is to determine whether a nontrivial Steiner system exists for . In this note we prove that for every and sufficiently large n, there exists an almost Steiner system with parameters t, k, and n; that is, there exists a k‐uniform hypergraph on n vertices such that every set of t distinct vertices is covered by either one or two edges.     

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.     

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.     

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.     

On the Intersection Problem for Steiner Triple Systems of Different Orders

A Steiner triple system of order v, or STS(v), is a pair (V, ) with V a set of v points and a set of 3-subsets of V called blocks or triples, such that every pair of distinct elements of V occurs in exactly one triple. The intersection problem for STS is to determine the possible numbers of blocks common to two Steiner triple systems STS(u), (U, ), and STS(v), (V, ), with U⊆V. The case where U=V was solved by Lindner and Rosa in 1975. Here, we let U⊂V and completely solve this question for v−u=2,4 and for v≥2u−3. supported by NSERC research grant #OGP0170220. supported by NSERC postdoctoral fellowship. supported by NSERC research grant #OGP007621.     

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.     

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