Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-29T13:03:30.219Z Has data issue: false hasContentIssue false
  • English
  • Français

Almost all Steiner triple systems are almost resolvable

Part of: Classical differential geometry Spectral theory and eigenvalue problems Calculus on manifolds; nonlinear operators

Published online by Cambridge University Press:  03 November 2020

Asaf Ferber  and
Matthew Kwan
Asaf Ferber
Affiliation:
Department of Mathematics, University of California, Irvine, California, USA; E-mail: [email protected]
Matthew Kwan
Affiliation:
Department of Mathematics, Stanford University, Stanford, California94305,USA; E-mail: [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show that for any n divisible by 3, almost all order-n Steiner triple systems admit a decomposition of almost all their triples into disjoint perfect matchings (that is, almost all Steiner triple systems are almost resolvable).

Keywords

survey designmeasurement errormachine learning

MSC classification

Primary: 35P15: Estimation of eigenvalues, upper and lower bounds
Secondary: 58C40: Spectral theory; eigenvalue problems 53A07: Higher-dimensional and -codimensional surfaces in Euclidean $n$-space
Type
Discrete Mathematics
Information
Forum of Mathematics, Sigma , Volume 8 , 2020 , e39
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2020. Published by Cambridge University Press

References

Alon, N., Kim, J.-H., and Spencer, J., ‘Nearly perfect matchings in regular simple hypergraphs’, Israel J. Math. 100 (1997), 171–187.CrossRefGoogle Scholar
Babai, L., ‘Almost all Steiner triple systems are asymmetric’, Ann. Discrete Math. 7 (1980), 37–39, Topics on Steiner systems.CrossRefGoogle Scholar
Boucheron, S., Lugosi, G., and Massart, P., Concentration inequalities: A nonasymptotic theory of independence (Oxford University Press, 2013).CrossRefGoogle Scholar
Bryant, D. and Horsley, D., ‘Steiner triple systems without parallel classes’, SIAM J. Discrete Math. 29(1) (2015), 693–696.CrossRefGoogle Scholar
Cameron, P. J., ‘A generalisation of $t$ -designs’, Discrete Math. 309(14) (2009), 4835–4842.CrossRefGoogle Scholar
Cayley, A., ‘On the triadic arrangements of seven and fifteen things’, Phil. Mag. 37 (1850), 50–53.Google Scholar
Colbourn, C. J. and Rosa, A., ‘Triple systems’, Oxford University Press, 1999.Google Scholar
Conlon, D., Gowers, W. T., Samotij, W., and Schacht, M., ‘On the KŁR conjecture in random graphs’, Israel J. Math. 203(1) (2014), 535–580.CrossRefGoogle Scholar
Conlon, D., Hàn, H., Person, Y., and Schacht, M., ‘Weak quasi-randomness for uniform hypergraphs’, Random Structures Algorithms. 40(1) (2012), 1–38.CrossRefGoogle Scholar
Erdős, P. and Rényi, A., ‘On random graphs. I’, Publ. Math, Debrecen 6 (1959), 290–297.Google Scholar
Ferber, A., Kronenberg, G., and Long, E., ‘Packing, counting and covering Hamilton cycles in random directed graphs’, Israel J. Math. 220(1) (2017), 57–87.CrossRefGoogle Scholar
Freedman, D. A., ‘On tail probabilities for martingales’, Ann. Probability 3 (1975), 100–118.CrossRefGoogle Scholar
Frieze, A. and Krivelevich, M., ‘Packing Hamilton cycles in random and pseudo-random hypergraphs’, Random Structures & Algorithms 41(1) (2012), 1–22.CrossRefGoogle Scholar
Hàn, H., Person, Y., and Schacht, M., ‘On perfect matchings in uniform hypergraphs with large minimum vertex degree’, SIAM J. Discrete Math. 23(2) (2009), 732–748.CrossRefGoogle Scholar
Janson, S., Łuczak, T., and Ruciński, A., Random graphs (Cambridge University Press, 2000).CrossRefGoogle Scholar
Janson, S. and Ruciński, A., ‘The infamous upper tail’, Random Structures Algorithms 20(3) (2002), 317–342, Probabilistic methods in combinatorial optimization.CrossRefGoogle Scholar
Johansson, A., Kahn, J., and Vu, V., ‘Factors in random graphs’, Random Structures Algorithms 33(1) (2008), 1–28.CrossRefGoogle Scholar
Karp, R.M., ‘Reducibility among combinatorial problems’, Complexity of Computer Computations (1972), 85–103.CrossRefGoogle Scholar
Keevash, P., ‘The existence of designs’, arXiv preprint arXiv:1401.3665 (2014).Google Scholar
Keevash, P., ‘Counting designs’, J. Eur. Math. Soc. (JEMS) 20(4) (2018), 903–927.CrossRefGoogle Scholar
Keevash, P., ‘The existence of designs II’, arXiv preprint arXiv:1802.05900 (2018).Google Scholar
Keevash, P. and Mycroft, R., ‘A geometric theory for hypergraph matching’, Mem. Amer. Math. Soc. 233(1098) (2015).Google Scholar
Kirkman, T.P., ‘On a problem in combinations’, The Cambridge and Dublin Mathematical Journal (Macmillan, Barclay, and Macmillan), II: (1847) 191–204.Google Scholar
Kirkman, T.P., ‘Query, VI., lady’s and gentleman’s diary’ (1850), 48.Google Scholar
Knox, F., Kühn, D., and Osthus, D., ‘Edge-disjoint Hamilton cycles in random graphs’, Random Structures Algorithms 46(3) (2015), 397–445.CrossRefGoogle Scholar
Kohayakawa, Y., Łuczak, T., and Rödl, V., ‘On ${K}^4$ -free subgraphs of random graphs’, Combinatorica 17(2) (1997), 173–213.CrossRefGoogle Scholar
Kohayakawa, Y. and Rödl, V., Szemerédi’s regularity lemma and quasi-randomness in Recent Advances in Algorithms and Combinatorics , CMS Books Math./Ouvrages Math. SMC, vol. 11 (Springer, New York, 2003), 289–351.Google Scholar
Kohayakawa, Y., Nagle, B., Rödl, V., and Schacht, M., ‘Weak hypergraph regularity and linear hypergraphs’, J. Combin. Theory Ser. B 100(2) (2010), 151–160.CrossRefGoogle Scholar
Krivelevich, M., Sudakov, B., Vu, V. H., and Wormald, N. C., ‘Random regular graphs of high degree’, Random Structures Algorithms 18(4) (2001), 346–363.CrossRefGoogle Scholar
Kühn, D. and Osthus, D., ‘Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments’, Adv. Math. 237 (2013), 62–146.CrossRefGoogle Scholar
Kwan, M., ‘Almost all Steiner triple systems have perfect matchings’, arXiv preprint arXiv:1611.02246 (2016).Google Scholar
Kwan, M. and Sudakov, B., ‘Intercalates and discrepancy in random Latin squares’, Random Structures Algorithms 52(2) (2018), 181–196.CrossRefGoogle Scholar
Linial, N. and Luria, Z., ‘Discrepancy of high-dimensional permutations’, Discrete Anal. (2016), paper 11, 8.Google Scholar
McKay, B. D. and Wanless, I. M., ‘Most Latin squares have many subsquares’, J. Combin. Theory Ser. A 86(2) (1999), 322–347.CrossRefGoogle Scholar
Montgomery, R., ‘Embedding bounded degree spanning trees in random graphs’, arXiv preprint arXiv:1405.6559 (2014).Google Scholar
Morris, P., ‘Random Steiner triple systems’, Master’s thesis, Freie Universität Berlin (2017).Google Scholar
Pippenger, N. and Spencer, J., ‘Asymptotic behavior of the chromatic index for hypergraphs’, J. Combin. Theory Ser. A 51(1) (1989), 24–42.CrossRefGoogle Scholar
Quackenbush, R. W., ‘Algebraic speculations about Steiner systems’, Ann. Discrete Math. 7 (1980), 25–35, Topics on Steiner systems.CrossRefGoogle Scholar
Ray-Chaudhuri, D. K. and Wilson, R. M., ‘Solution of Kirkman’s schoolgirl problem’, in Combinatorics (Proc. Sympos. Pure Math.), vol. XIX (Univ. California, Los Angeles, Calif., 1968; Amer. Math. Soc., Providence, RI, 1971), 187–203.Google Scholar
Rödl, V., ‘On a packing and covering problem’, European J. Combin. 6(1) (1985), 69–78.CrossRefGoogle Scholar
Rödl, V., Ruciński, A., and Szemerédi, E., ‘An approximate Dirac-type theorem for k-uniform hypergraphs’, Combinatorica 28(2) (2008), 229–260.CrossRefGoogle Scholar
Simkin, M., ‘Methods for analyzing random designs’, lecture notes: IIAS special day on combinatorial design theory, http://math.huji.ac.il/~michaels/files/papers/pasch_in_sts.pdf (2018).Google Scholar
van Rees, G. H. J., ‘Subsquares and transversals in Latin squares’, Ars Combin. 29(B) (1990), 193–204, 12th British Combinatorial Conference (Norwich, 1989).Google Scholar
Wanless, I. M. and Webb, B. S., ‘The existence of Latin squares without orthogonal mates’, Des. Codes Cryptogr. 40(1) (2006), 131–135.CrossRefGoogle Scholar
Warnke, L., ‘On the method of typical bounded differences’, Combin. Probab. Comput. 25(2) (2016), 269–299.CrossRefGoogle Scholar