Caps and Colouring Steiner Triple Systems

Hill [6] showed that the largest cap in PG(5,3) has cardinality 56. Using this cap it is easy to construct a cap of cardinality 45 in AG(5,3). Here we show that the size of a cap in AG(5,3) is bounded above by 48. We also give an example of three disjoint 45-caps in AG(5,3). Using these two results we are able to prove that the Steiner triple system AG(5,3) is 6-chromatic, and so we exhibit the first specific example of a 6-chromatic Steiner triple system.     

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     

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.     

Equitable Specialized Block-Colourings for Steiner Triple Systems

We continue the study of specialized block-colourings of Steiner triple systems initiated in [2] in which the triples through any element are coloured according to a given partition π of the replication number. Such colourings are equitable if π is an equitable partition (i.e., the difference between any two parts of π is at most one). Our main results deal with colourings according to equitable partitions into two, and three parts, respectively.     

Partitioning 3‐arcs into Steiner Triple Systems

In this article, it is shown that there is a partitioning of the set of 3‐arcs in a projective plane of order three into nine pairwise disjoint Steiner triple systems of order 13.     

Dimension of the space generated by Steiner systems

To every Steiner system with parameters on and blocks , we can assign its characteristic vector , which is a ‐vector whose entries are indexed by the ‐subsets of such that for each ‐subset of if and only if . In this paper, we show that the dimension of the vector space generated by all of the characteristic vectors of Steiner systems with parameters is , provided that and there is at least one such system.     

Large Cross‐Free Sets in Steiner Triple Systems

A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n.     

Piotrowski's Infinite Series of Steiner Quadruple SystemsRevisited

The construction of Bays and deWeck [1] of a SteinerQuadruple System SQS(14) was generalized by Piotrowskiin his dissertation ([7], p. 34) to an SQS(2p), p 7 mod 12 with a group transitive on thepoints. However he gave no proof of his construction and hispresesntation was open to misinterpretation. So Hanfried Lenzsuggested to analyse Piotrowski's construction and to supplyit with a proof. In the following we will present Piotrowski'sideas somewhat differently and will furnish a proof of the construction.     

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     

Simple Signed Steiner Triple Systems

Let X be a v‐set, be a set of 3‐subsets (triples) of X, and be a partition of with . The pair is called a simple signed Steiner triple system, denoted by ST, if the number of occurrences of every 2‐subset of X in triples is one more than the number of occurrences in triples . In this paper, we prove that exists if and only if , , and , where and for , . © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 332–343, 2012     

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.     

Tactical Decompositions of Steiner Systems and Orbits of Projective Groups

Block's lemma states that the numbers m of point-classes and n of block-classes in a tactical decomposition of a 2-(v, k, ) design with b blocks satisfy m n m + b – v. We present a strengthening of the upper bound for the case of Steiner systems (2-designs with = 1), together with results concerning the structure of the block-classes in both extreme cases. Applying the results to the Steiner systems of points and lines of projective space PG(N, q), we obtain a complete classification of the groups inducing decompositions satisfying the upper bound; answering the analog of a question raised by Cameron and Liebler (P.J. Cameron and R.A. Liebler, Lin. Alg. Appl. 46 (1982), 91–102) (and still open).     

The Automorphism Groups of Steiner Triple Systems Obtained by the Bose Construction

The automorphism group of the Steiner triple system of order v 3 (mod 6), obtained from the Bose construction using any Abelian Group G of order 2s + 1, is determined. The main result is that if G is not isomorphic to Z ₃ ⁿ × Z ₉ ^m , n 0, m 0, the full automorphism group is isomorphic to Hol(G) × Z ₃, where Hol(G) is the Holomorph of G. If G is isomorphic to Z ₃ ⁿ × Z ₉ ^m , further automorphisms occur, and these are described in full.     

Two-Weight Codes, Partial Geometries and Steiner Systems

Two-weight codes and projectivesets having two intersection sizes with hyperplanes are equivalentobjects and they define strongly regular graphs. We construct projective sets in PG(2m – 1,q) that have the sameintersection numbers with hyperplanes as the hyperbolic quadricQ⁺(2m – 1,q). We investigate these sets; we provethat if q = 2 the corresponding strongly regular graphsare switching equivalent and that they contain subconstituentsthat are point graphs of partial geometries. If m = 4the partial geometries have parameters s = 7, t = 8, = 4 and some of them are embeddable in Steinersystems S(2,8,120).     

Trinal Decompositions of Steiner Triple Systems into Triangles

It is well known that when or , there exists a Steiner triple system (STS) of order n decomposable into triangles (three pairwise intersecting triples whose intersection is empty). A triangle in an STS determines naturally two more triples: the triple of “vertices” , and the triple of “midpoints” . The number of these triples in both cases, that of “vertex” triples (inner) or that of “midpoint triples” (outer), equals one‐third of the number of triples in the STS. In this paper, we consider a new problem of trinal decompositions of an STS into triangles. In this problem, one asks for three distinct decompositions of an STS of order n into triangles such that the union of the three collections of inner triples (outer triples, respectively) from the three decompositions form the set of triples of an STS of the same order. These decompositions are called trinal inner and trinal outer decompositions, respectively. We settle the existence question for trinal inner decompositions completely, and for trinal outer decompositions with two possible exceptions.     

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.     

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     

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}.     

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.     

Classification of Cyclic Steiner Quadruple Systems

The problem of classifying cyclic Steiner quadruple systems (CSQSs) is considered. A computational approach shows that the number of isomorphism classes of such designs with orders 26 and 28 is 52,170 and 1,028,387, respectively. It is further shown that CSQSs of order 2p, where p is a prime, are isomorphic iff they are multiplier equivalent. Moreover, no CSQSs of order less than or equal to 38 are isomorphic but not multiplier equivalent.