Glasnik Matematicki, Vol. 58, No. 2 (2023), 201-224. \( \)

BUSSEY SYSTEMS AND STEINER'S TACTICAL PROBLEM

Charles J. Colbourn, Donald L. Kreher and Patric R. J. Östergård

Arizona State University, Tempe, Arizona, USA
e-mail:Charles.Colbourn@asu.edu

Michigan Technological University, Houghton, Michigan, USA
e-mail:Kreher@mtu.edu

Department of Information and Communications Engineering, Aalto University School of Electrical Engineering, 00076 Aalto, Finland
e-mail:patric.ostergard@aalto.fi

Abstract.   In 1853, Steiner posed a number of combinatorial (tactical) problems, which eventually led to a large body of research on Steiner systems. However, solutions to Steiner's questions coincide with Steiner systems only for strengths two and three. For larger strengths, essentially only one class of solutions to Steiner's tactical problems is known, found by Bussey more than a century ago. In this paper, the relationships among Steiner systems, perfect binary one-error-correcting codes, and solutions to Steiner's tactical problem (Bussey systems) are discussed. For the latter, computational results are provided for at most 15 points.

2020 Mathematics Subject Classification.   05B05, 51E10, 94B99, 05B30, 05B40

Key words and phrases.   Steiner system, original Steiner system, Bussey system, perfect code

Full text (PDF) (access from subscribing institutions only)

https://doi.org/10.3336/gm.58.2.04

References:

  1. W. O. Alltop, Extending \(t\)-designs, J. Combinatorial Theory Ser. A 18 (1975), 177–186.
    MathSciNet    CrossRef

  2. I. Anderson, C. J. Colbourn, J. H. Dinitz, and T. S. Griggs, Design theory: Antiquity to 1950, in: Handbook of combinatorial designs, Chapman and Hall/CRC, Boca Raton, 2007, 11–22.

  3. J. E. F. Assmus Jr. and J. H. F. Mattson Jr., On tactical configurations and error-correcting codes, J. Combinatorial Theory 2 (1967), 243–257.
    MathSciNet

  4. W. W. R. Ball, Mathematical recreations and essays, The Macmillan Company, London, 1914.

  5. J. A. Barrau, On the combinatory problem of Steiner, Nederl. Akad. Wetensch. Proc. Ser. B 11 (1908), 352–360.

  6. S. Bays and E. de Weck, Sur les systèmes de quadruples, Comment. Math. Helv. 7 (1934), 222–241.
    MathSciNet    CrossRef

  7. R. A. Beezer, Counting configurations in designs, J. Combin. Theory Ser. A 96 (2001), 341–357.
    MathSciNet    CrossRef

  8. R. C. Bose, On the construction of balanced incomplete block designs, Ann. Eugenics 9 (1939), 353–399.
    MathSciNet

  9. G. Brunel, Sur les deux systèmes de triades de treize éléments, J. Math. Pures Appl. (5) 7 (1901) 305–330.

  10. W. H. Bussey, On the tactical problem of Steiner, Bull. Amer. Math. Soc. 16 (1909), 19–22.
    MathSciNet    CrossRef

  11. W. H. Bussey, The tactical problem of Steiner, Amer. Math. Monthly 21 (1914), 3–12.
    MathSciNet    CrossRef

  12. R. D. Carmichael, Tactical configurations of rank two, Amer. J. Math. 53 (1931), 217–240.
    MathSciNet    CrossRef

  13. L. G. Chouinard II, E. S. Kramer and D. L. Kreher, Graphical \(t\)-wise balanced designs, Discrete Math. 46 (1983), 227–240.
    MathSciNet    CrossRef

  14. C. J. Colbourn, The configuration polytope of \(l\)-line configurations in Steiner triple systems, Math. Slovaca 59 (2009), 77–108.
    MathSciNet    CrossRef

  15. C. J. Colbourn and J. H. Dinitz (eds.), Handbook of combinatorial designs, Chapman & Hall/CRC, Boca Raton, 2007.
    MathSciNet

  16. C. J. Colbourn, A. D. Forbes, M. J. Grannell, T. S. Griggs, P. Kaski, P. R. J. Östergård, D. A. Pike and O. Pottonen, Properties of the Steiner triple systems of order 19, Electron. J. Combin. 17 (2010), research paper 98.
    MathSciNet    CrossRef

  17. C. J. Colbourn and R. A. Mathon, Steiner systems, in: Handbook of combinatorial designs, Chapman and Hall/CRC, Boca Raton, 2007, 102–110.

  18. C. J. Colbourn and A. Rosa, Triple systems, The Clarendon Press, Oxford University Press, New York, 1999.
    MathSciNet

  19. F. N. Cole, L. D. Cummings, and H. S. White, The complete enumeration of triad systems in 15 elements, Proc. Natl. Acad. Sci. USA 3 (1917), 197–199.

  20. L. D. Cummings, An undervalued Kirkman paper, Bull. Amer. Math. Soc. 24 (1918), 336–339.
    MathSciNet    CrossRef

  21. V. De Pasquale, Sui sistemi ternari di 13 elementi, Rendiconti. Reale Istituto Lombardo di Science e Lettere, Serie II, 32 (1899), 213–221.

  22. I. Diener, E. Schmitt and H. L. de Vries, All \(80\) Steiner triple systems on \(15\) elements are derived, Discrete Math. 55 (1985), 13–19.
    MathSciNet    CrossRef

  23. C. Ehrhardt, Tactics: in search of a long-term mathematical project (1844–1896), Historia Math. 42 (2015), 436–467.
    MathSciNet    CrossRef

  24. M. J. E. Golay, Notes on digital coding, Proc. I.R.E. 37 (1949), 657.
    MathSciNet

  25. M. J. Grannell, T. S. Griggs and R. A. Mathon, Steiner systems \(S(5,6,v)\) with \(v=72\) and \(84\), Math. Comp. 67 (1998), 357–359, S1–S9.
    MathSciNet    CrossRef

  26. R. W. Hamming, Error detecting and error correcting codes, Bell System Tech. J. 29 (1950), 147–160.
    MathSciNet    CrossRef

  27. H. Hanani, On quadruple systems, Canadian J. Math. 12 (1960), 145–157.
    MathSciNet    CrossRef

  28. H. Hanani, On the original Steiner systems, Discrete Math. 51 (1984), 309–310.
    MathSciNet    CrossRef

  29. H. Hanani and J. Schönheim, On Steiner systems, Israel J. Math. 2 (1964), 139–142 and 4 (1966), 144.
    MathSciNet    CrossRef

  30. O. Heden, A survey of perfect codes, Adv. Math. Commun. 2 (2008), 223–247.
    MathSciNet    CrossRef

  31. S. Jukna, Extremal combinatorics, Springer, Heidelberg, 2011.
    MathSciNet    CrossRef

  32. P. Kaski and P. R. J. Östergård, The Steiner triple systems of order 19, Math. Comp. 73 (2004), 2075–2092.
    MathSciNet    CrossRef

  33. P. Kaski, P. R. J. Östergård and O. Pottonen, The Steiner quadruple systems of order 16, J. Combin. Theory Ser. A 113 (2006), 1764–1770.
    MathSciNet    CrossRef

  34. P. Kaski and O. Pottonen, libexact user's guide, version 1.0., Technical Report 2008-1, Helsinki Institute for Information Technology, 2008.

  35. P. Keevash, The existence of designs, 2014, arXiv:1401.3665.
    Link

  36. T. P. Kirkman, On a problem in combinations, Cambridge and Dublin Mathematical Journal 2 (1847), 191–204.

  37. E. S. Kramer and D. M. Mesner, \(t\)-designs on hypergraphs, Discrete Math. 15 (1976), 263–296.
    MathSciNet    CrossRef

  38. K. A. Lauinger, D. L. Kreher, R. Rees and D. R. Stinson, Computing transverse \(t\)-designs, J. Combin. Math. Combin. Comput. 54 (2005), 33–56.
    MathSciNet

  39. B. D. McKay, nauty user's guide (version 1.5), Report TR-CS-90-02, Computer Science, Australian National University, 1990.

  40. N. S. Mendelsohn, A theorem on Steiner systems, Canadian J. Math. 22 (1970), 1010–1015.
    MathSciNet    CrossRef

  41. N. S. Mendelsohn and S. H. Y. Hung, On the Steiner systems \(S(3,\,4,\,14)\) and \(S(4,\,5,\,15)\), Utilitas Math. 1 (1972), 5–95.
    MathSciNet

  42. E. H. Moore, Tactical Memoranda I–III, Amer. J. Math. 18 (1896), 264–290.
    MathSciNet    CrossRef

  43. E. Netto, Lehrbuch der Combinatorik, Teubner, Leipzig, 1927.

  44. P. R. J. Östergård and O. Pottonen, There exist Steiner triple systems of order 15 that do not occur in a perfect binary one-error-correcting code, J. Combin. Des. 15 (2007), 465–468.
    MathSciNet    CrossRef

  45. P. R. J. Östergård and O. Pottonen, There exists no Steiner system \(S(4,5,17)\), J. Combin. Theory Ser. A 115 (2008), 1570–1573.
    MathSciNet    CrossRef

  46. P. R. J. Östergård and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I. Classification, IEEE Trans. Inform. Theory 55 (2009), 4657–4660.
    MathSciNet    CrossRef

  47. P. R. J. Östergård, O. Pottonen and K. T. Phelps, The perfect binary one-error-correcting codes of length 15: Part II. Properties, IEEE Trans. Inform. Theory 56 (2010), 2571–2582.
    MathSciNet    CrossRef

  48. K. T. Phelps, A combinatorial construction of perfect codes, SIAM J. Algebraic Discrete Methods 4 (1983), 398–403.
    MathSciNet    CrossRef

  49. K. T. Phelps, A general product construction for error correcting codes, SIAM J. Algebraic Discrete Methods 5 (1984), 224–228.
    MathSciNet    CrossRef

  50. M. Plotkin, Binary codes with specified minimum distance, IRE Trans. IT-6 (1960), 445–450.
    MathSciNet    CrossRef

  51. J. Plücker, System der analytischen Geometrie, auf neue Betrachtungsweisen gegrün­det, und insbesondere eine ausfḧrliche Theorie der Curven dritter Ordnung enthalend, Duncker und Humboldt, Berlin, 1835.

  52. J. Plücker, Theorie der algebraischen Curven, gegründet auf eine meue Behandlungensweise der analytischen Geometrie, Marcus, Bonn, 1839.

  53. G. Salmon, A treatise on the higher plane curves, Hodges, Foster, and Figgis, Dublin, 1879.

  54. N. J. A. Sloane and D. S. Whitehead, New family of single-error correcting codes, IEEE Trans. Inform. Theory IT-16 (1970), 717–719.
    MathSciNet    CrossRef

  55. F. I. Solov'eva, Binary nongroup codes, Metody Diskret. Analiz. 37 (1981), 65–76, 86.
    MathSciNet

  56. E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), 544–548.

  57. J. Steiner, Combinatorische Aufgaben, J. Reine Angew. Math. 45 (1853), 181–182.
    MathSciNet    CrossRef

  58. J. Steiner, Allgemeine Eigenschaften der algebraischen, Curven, J. Reine Angew. Math. 47 (1854), 1–6.

  59. J. Steiner, Eigenschaften der Curven vierten Grades rücksichtlich ihrer Doppeltangenten, J. Reine Angew. Math. 49 (1855), 265–272.

  60. D. R. Stinson and Y. J. Wei, Some results on quadrilaterals in Steiner triple systems, Discrete Math. 105 (1992), 207–219.
    MathSciNet    CrossRef

  61. J. J. Sylvester, Elementary researches in the analysis of combinatorial aggregation, Phil. Mag. (3) 24 (1844), 285–296.

  62. J. H. van Lint, A survey of perfect codes, Rocky Mountain J. Math. 5 (1975), 199–224.
    MathSciNet    CrossRef

  63. J. L. Vasil'ev, On nongroup close-packed codes, Problemy Kibernet. 8 (1962), 337–339, (in Russian). English translation in Probleme der Kybernetik 8 (1965), 375–378.

  64. O. Veblen and J. W. Young, Projective geometry, Ginn and Co., Boston, 1916.

  65. E. Witt, Die 5-fach transitiven gruppen von Mathieu, Abh. Math. Sem. Univ. Hamburg 12 (1937), 256–264.
    MathSciNet    CrossRef

  66. E. Witt, Über Steinersche Systeme, Abh. Math. Sem. Univ. Hamburg 12 (1937), 265–275.

  67. W. S. B. Woolhouse, Prize question 1733, Lady's and Gentleman's Diary, 1844.
Glasnik Matematicki Home Page