×

Anti-mitre Steiner triple systems. (English) Zbl 0815.05017

A \((k,\ell)\)-configuration in a Steiner triple system \((V,B)\), is a subset of \(\ell\) triples from \(B\) whose union is a \(k\)-element subset of \(V\). The Pasch configuration is the \((6,4)\)-configuration on a set \(\{a,b, c,d, e,f\}\) with triples \(abe\), \(acf\), \(bdf\), \(cde\). The mitre is the \((7,5)\)-configuration on a set \(\{a,b, c,d, e,f, g\}\) with triples \(abe\), \(acf\), \(adg\), \(bcd\), \(efg\). A Steiner triple system (STS) is anti- Pasch (anti-mitre) if it does not contain any Pasch (mitre) configuration. Moreover, an STS is called \(r\)-sparse if every set of \(r+2\) elements carries fewer than \(r\) triples. Every STS is 3-sparse, is 4-sparse if and only if it is anti-Pasch, and 5-sparse if and only if it is both anti-Pasch and anti-mitre.
This paper makes substantial progress toward characterizing those \(v\) for which there exists an anti-mitre STS of order \(v\), and shows that for at least \({9 \over {16}}\) of the admissible values of \(v\) there exists an anti-mitre STS. The paper includes a table summarising small cyclic STS up to order 57, with the number of cyclic STS which are anti-Pasch or anti-mitre, or both (5-sparse). Also cyclic 5-sparse \(\text{STS} (v)\) are given for orders \(v=19\) and (\(v\equiv 1\) or \(3\pmod 6\)), \(33\leq v\leq 97\). This leads to the conjecture made in the paper that a 5-sparse \(\text{STS} (v)\) exists for all \(v\equiv 1, 3\pmod 6\), \(v\geq 33\). Existence of 5-sparse STS for orders 21, 25, 27 and 31 remains open, while not a single example of a 6-sparse \(\text{STS} (v)\) is currently known.

MSC:

05B07 Triple systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brouwer, A.E.: Steiner triple systems without forbidden subconfigurations, Mathematisch Centrum Amsterdam, ZW 104-77, 1977 · Zbl 0367.05011
[2] Colbourn, M. J.; Mathon, R., On cyclic Steiner 2-designs, Ann. Discrete Math., 7, 215-253 (1980) · Zbl 0438.05012 · doi:10.1016/S0167-5060(08)70182-1
[3] Frenz, T. C.; Kreher, D. L., An algorithm for enumerating distinct cyclic Steiner systems, J. Comb. Math. Comb. Comput., 11, 23-32 (1992) · Zbl 0755.05009
[4] Griggs, T. S.; Murphy, J.; Phelan, J. S., Anti-Pasch Steiner triple systems, J. Comb. Inf. Syst. Sci., 15, 79-84 (1990) · Zbl 0741.05009
[5] Lefmann, H.; Phelps, K. T.; Rödl, V., Extremal problems for triple systems, J. Combinat. Designs, 1, 379-394 (1993) · Zbl 0817.05015 · doi:10.1002/jcd.3180010506
[6] Mathon, R.; Phelps, K. T.; Rosa, A., Small Steiner triple systems and their properties, Ars Comb., 15, 3-110 (1983) · Zbl 0516.05010
[7] Robinson, R. M., The structure of certain triple systems, Math. Comput., 20, 223-241 (1975) · Zbl 0293.05015
[8] Rosa, A., Algebraic properties of designs and recursive constructions, Congressus Numer., 13, 183-200 (1975) · Zbl 0328.05012
[9] Stinson, D. R.; Wei, R., Some results on quadrilaterals in Steiner triple systems, Discrete Math., 105, 207-219 (1992) · Zbl 0783.05022 · doi:10.1016/0012-365X(92)90143-4
[10] Street, A. P.; Street, DJ., The Combinatorics of Experimental Design (1987), Oxford: Clarendon Press, Oxford · Zbl 0622.05001
[11] Teirlinck, L.; Dinitz, J. H.; Stinson, D. R., Large sets of disjoint designs and related structures, Contemporary Design Theory, 561-592 (1992), New York: Wiley, New York · Zbl 0805.05012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.