JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 26, No 4 (2007)

Yuichiro Fujiwara

Nagoya University Graduate School of Information Science Furo-cho, Chikusa-ku 464-8601 Japan

In 1973 Paul Erdös conjectured that there is an integer v ₀( r) such that, for every v> v ₀( r) and v\equiv 1,3 (mod 6), there exists a Steiner triple system of order v, containing no i blocks on i+2 points for every 1< i\leq  r. Such an STS is said to be r-sparse. In this paper we consider relations of automorphisms of an STS to its sparseness. We show that for every r\geq 13 there exists no point-transitive r-sparse STS over an abelian group. This bound and the classification of transitive groups give further nonexistence results on block-transitive, flag-transitive, 2-transitive, and 2-homogeneous STSs with high sparseness. We also give stronger bounds on the sparseness of STSs having some particular automorphisms with small groups. As a corollary of these results, it is shown that various well-known automorphisms, such as cyclic, 1-rotational over arbitrary groups, and involutions, prevent an STS from being high-sparse.

1. Beth, T., Jungnickel, D., & Lenz, H. (1999). Design theory. Cambridge: Cambridge University Press.
2. Brouwer, A. E. (1977). Steiner triple systems without forbidden subconfigurations. Mathematisch Centrum Amsterdam, ZW 104/77.
3. Brown, W. G., Erd\Acute\Acute os, P., & Sós, V. T. (1973). Some extremal problems on r -graphs. In F. Harary (Ed.), New directions in the theory of graphs, Proc. Third Ann Arbor Conf. Univ. Michigan, Ann Arbor, MI, October 1971 (pp. 53-63). New York: Academic Press.
4. Buratti, M. (2001). 1-rotational Steiner triple systems over arbitrary groups. J. Comb. Des., 9, 215- 226.
5. Calahan-Zijlstra, R., & Gardner, R. B. (1994). Bicyclic Steiner triple systems. Discret. Math., 128, 35-44.
6. Chee, Y. M., Colbourn, C. J., & Ling, A. C. H. (2000). Asymptotically optimal erasure-resilient codes for large disk arrays. Discret. Appl. Math., 102, 3-36.
7. Clapham, P. C. (1976). Steiner triple systems with block-transitive automorphism groups. Discret. Math., 14, 121-131.
8. Colbourn, C. J., & Rosa, A. (1999). Triple systems. New York: Oxford University Press.
9. Colbourn, C. J., Mendelsohn, E., Rosa, A., & Širá\check n, J. (1994). Anti-mitre Steiner triple systems. Graphs Comb., 10, 215-224.
10. Delandtsheer, A., Doyen, J., Siemons, J., & Tamburini, C. (1986). Doubly homogeneous 2-(v, k, 1) designs. J. Comb. Theory Ser. A, 43, 140-145.
11. Doyen, J. (1972). A note on Steiner triple systems. Discret. Math., 1, 315-319.
12. Erd\Acute\Acute os, P. (1976). Problems and results in combinatorial analysis. In Atti dei Convegni Lincei (Vol. 17, pp. 3-17). Colloquio Internazionale sulle Teorie Combinatorie, Tomo II, Rome,
1973. Rome: Accad. Naz. Lincei.
13. Forbes, A. D., Grannell, M. J., & Griggs, T. S. (2007). On 6-sparse Steiner triple systems. J. Comb. Theory Ser. A, 114, 235-252.
14. Fujiwara, Y. (2005). Constructions for anti-mitre Steiner triple systems. J. Comb. Des., 13, 286-291.
15. Fujiwara, Y. (2006). Infinite classes of anti-mitre and 5-sparse Steiner triple systems. J. Comb. Des., 14, 237-250.
16. Fujiwara, Y. Cyclic 4- and 5-sparse Steiner triple systems (submitted).
17. Gardner, R. B. (1994). Steiner triple systems with transrotational automorphisms. Discret. Math., 131, 99-104.
18. Grannell, M. J., Griggs, T. S., & Murphy, J. P. (1999). Some new perfect Steiner triple systems. J. Comb. Des., 7, 327-330.
19. Grannell, M. J., Griggs, T. S., & Whitehead, C. A. (2000). The resolution of the anti-Pasch conjecture. J. Comb. Des., 8, 300-309.
20. Hall, M. Jr. (1985). Steiner triple systems with a doubly-transitive automorphism group. J. Comb. Theory Ser. A, 38, 192-202.
21. Hartman, A., & Hoffman, D. G. (1987). Steiner triple systems with an involution. Eur. J. Comb., 8, 371-378.
22. Johnson, S. J., & Weller, S. R. (2003). Resolvable 2-designs for regular low-density parity-check codes. IEEE Trans. Commun., 51, 1413-1419.
23. Kantor, W. M. (1985). Homogeneous designs and geometric lattices. J. Comb. Theory Ser. A, 38, 66-74.
24. Key, J. D., & Shult, E. E. (1984). Steiner triple systems with doubly-transitive automorphism groups: a corollary to the classification theorem for finite simple groups. J. Comb. Theory Ser. A, 36, 105-110.
25. Kirkman, T. P. (1847). On a problem in combinations. Camb. Dublin Math. J., 2, 191-204.
26. Lefmann, H., Phelps, K. T., & Rödl, V. (1993). Extremal problems for triple systems. J. Comb. Des., 1, 379-394.
27. Ling, A. C. H. (1997). A direct product construction for 5-sparse triple systems. J. Comb. Des., 5, 443-447.
28. Ling, A. C. H., Colbourn, C. J., Grannell, M. J., & Griggs, T. S. (2000). Construction techniques for anti-Pasch Steiner triple systems. J. Lond. Math. Soc. (2), 61, 641-657.
29. Peltesohn, R. (1939). Eine Lösung der beiden Heffterschen Differenzenprobleme. Compos. Math., 6, 251-257.
30. Robinson, R. M. (1975). The structure of certain triple systems. Math. Comput., 29, 223-241.
31. Rosa, A. (1972). On reverse Steiner triple systems. Discret. Math., 2, 61-71.
32. Teirlinck, L. (1973). The existence of Steiner triple systems. Discret. Math., 6, 301-302. J Algebr Comb (2007) 26: 495-506
33. Vasic, B., & Milenkovic, O. (2004). Combinatorial constructions of low-density parity-check codes for iterative decoding. IEEE Trans. Inf. Theory, 50, 1156-1176.
34. Vasic, B., Kurtas, E. M., & Kuznetsov, A. V. (2002). Kirkman systems and their application in perpendicular magnetic recording. IEEE Trans. Mag., 38, 1705-1710.
35. Wolfe, A. (2005). 5-sparse Steiner triple systems of order n exist for almost all admissible n. Electron. J. Comb., 12, Research Paper 68, 42 pp. (electronic).
36. Wolfe, A. (2006). The resolution of the anti-mitre Steiner triple system conjecture. J. Comb. Des., 14, 229-236.