×

zbMATH — the first resource for mathematics

On 6-sparse Steiner triple systems. (English) Zbl 1121.05015
A Steiner triple system of order \(v\) \([\text{STS}(v)]\) consists of a \(v\)-set \(V\) of elements and a family \(B\) of 3-subsets of \(V\) called triples such that each 2-subset of \(V\) is contained in exactly one triple of \(B\). A configuration in an \(\text{STS}(v)\) is a partial triple system consisting typically of a small number of triples. An \(\text{STS}(v)\) is \(k\)-sparse if it contains no configuration with \(n\) triples and \(n+2\) points for any \(4\leq n\leq k\). The 4-sparse STSs are precisely those which are anti-Pasch, and are known to exist for all orders \(v\) congruent to 1 or 3 modulo 6, except for \(v= 7\) or 13. The 5-sparse STSs are precisely those which are both anti-Pasch and anti-mitre, and have been shown by A. Wolfe [Electron. J. Comb. 12, No. 1, Research paper R68, 42 p., electronic only (2005; Zbl 1079.05013)] to exist for almost all admissible orders.
In this article, the authors use a construction of M. J. Grannell, T. S. Griggs and J. P. Murphy [J. Comb. Des. 7, No. 5, 327–330 (1999; Zbl 0935.05016)] to obtain first examples of 6-sparse STSs. Their 29 examples given range from \(v= 139\) to \(v= 4447\); it is shown that these are the only 6-sparse STSs that can be obtained by using this method. A tripling construction and a product construction are then used to show that there exist infinitely many 6-sparse STSs. Also in this paper, the authors construct a new perfect STS of order \(v= 135\),859 and a new uniform (non-perfect) STS with \(v= 180\),907.
Reviewer: Colin Reid

MSC:
05B07 Triple systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.; Kim, J.-H.; Spencer, J., Nearly perfect matchings in regular simple hypergraphs, Israel J. math., 100, 171-187, (1997) · Zbl 0882.05107
[2] A.E. Brouwer, Steiner triple systems without forbidden subconfigurations, Mathematisch Centrum Amsterdam, ZW 104/77, 1977 · Zbl 0367.05011
[3] Colbourn, C.J.; Mendelsohn, E.; Rosa, A.; Širáň, J., Anti-mitre Steiner triple systems, Graphs combin., 10, 215-224, (1994) · Zbl 0815.05017
[4] Colbourn, C.J.; Rosa, A., Triple systems, ISBN: 0-19-853576-7, (1999), Oxford Univ. Press New York · Zbl 0607.05014
[5] Erdös, P., Problems and results in combinatorial analysis, (), 3-17
[6] Fujiwara, Y., Constructions for anti-mitre Steiner triple systems, J. combin. des., 13, 286-291, (2005) · Zbl 1066.05034
[7] Fujiwara, Y., Infinite classes of anti-mitre and 5-sparse Steiner triple systems, J. combin. des., 14, 237-250, (2006) · Zbl 1089.05012
[8] Grannell, M.J.; Griggs, T.S.; Mendelsohn, E., A small basis for four-line configurations in Steiner triple systems, J. combin. des., 3, 51-59, (1994) · Zbl 0820.05010
[9] Grannell, M.J.; Griggs, T.S.; Murphy, J.P., Some new perfect Steiner triple systems, J. combin. des., 7, 327-330, (1999) · Zbl 0935.05016
[10] Grannell, M.J.; Griggs, T.S.; Whitehead, C.A., The resolution of the anti-pasch conjecture, J. combin. des., 8, 300-309, (2000) · Zbl 0959.05016
[11] Griggs, T.S.; Murphy, J.P.; Phelan, J.S., Anti-pasch Steiner triple systems, J. combin. inform. system sci., 15, 79-84, (1990) · Zbl 0741.05009
[12] Ling, A.C.H., A direct product construction for 5-sparse Steiner triple systems, J. combin. des., 5, 443-447, (1997) · Zbl 0912.05012
[13] Ling, A.C.H.; Colbourn, C.J.; Grannell, M.J.; Griggs, T.S., Construction techniques for anti-pasch Steiner triple systems, J. London math. soc. (2), 61, 641-657, (2000) · Zbl 0956.05023
[14] Schmidt, W.M., Equations over finite fields, Lecture notes in math., vol. 536, (1976), Springer-Verlag Berlin
[15] Robinson, R.M., The structure of certain triple systems, Math. comp., 29, 223-241, (1975) · Zbl 0293.05015
[16] Wolfe, A.J., The resolution of the anti-mitre Steiner triple system conjecture, J. combin. des., 14, 229-236, (2006) · Zbl 1089.05013
[17] Wolfe, A.J., 5-sparse Steiner triple systems of order n exist for almost all admissible n, Electron. J. combin., 12, #R68, (2005), 42 p. (electronic) · Zbl 1079.05013
[18] A.J. Wolfe, Block transitive meager squares over \(\mathit{GF}(q)\) for prime q, preprint, 2005, 15 p., http://www.math.ohio-state.edu/ water/
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.