New bounds for Ryser’s conjecture and related problems
HTML articles powered by AMS MathViewer
- by Peter Keevash, Alexey Pokrovskiy, Benny Sudakov and Liana Yepremyan HTML | PDF
- Trans. Amer. Math. Soc. Ser. B 9 (2022), 288-321
Abstract:
A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser-Brualdi-Stein from 60s which says that every Latin square of order $n\times n$ contains a transversal of order $n-1$. In this paper we prove the existence of a transversal of order $n-O(\log {n}/\log {\log {n}})$, improving the celebrated bound of $n-O(\log ^2n)$ by Hatami and Shor. Our approach (different from that of Hatami-Shor) is quite general and gives several other applications as well. We obtain a new lower bound on a 40-year-old conjecture of Brouwer on the maximum matching in Steiner triple systems, showing that every such system of order $n$ is guaranteed to have a matching of size $n/3-O(\log {n}/\log {\log {n}})$. This substantially improves the current best result of Alon, Kim and Spencer which has the error term of order $n^{1/2+o(1)}$. Finally, we also show that $O(n\log {n}/\log {\log {n}})$ many symbols in Latin arrays suffice to guarantee a full transversal, improving on a previously known bound of $n^{2-\varepsilon }$. The proofs combine in a novel way the semi-random method together with the robust expansion properties of edge-coloured pseudorandom graphs to show the existence of a rainbow matching covering all but $O(\log n/\log {\log {n}})$ vertices. All previous results, based on the semi-random method, left uncovered at least $\Omega (n^{\alpha })$ (for some constant $\alpha >0$) vertices.References
- Ron Aharoni, Eli Berger, Dani Kotlar, and Ran Ziv, On a conjecture of Stein, Abh. Math. Semin. Univ. Hambg. 87 (2017), no. 2, 203–211. MR 3696146, DOI 10.1007/s12188-016-0160-3
- Saieed Akbari and Alireza Alipour, Transversals and multicolored matchings, J. Combin. Des. 12 (2004), no. 5, 325–332. MR 2079255, DOI 10.1002/jcd.20014
- Noga Alon, Jeong-Han Kim, and Joel Spencer, Nearly perfect matchings in regular simple hypergraphs, Israel J. Math. 100 (1997), 171–187. MR 1469109, DOI 10.1007/BF02773639
- Noga Alon, Michael Krivelevich, and Benny Sudakov, List coloring of random and pseudo-random graphs, Combinatorica 19 (1999), no. 4, 453–472. MR 1773652, DOI 10.1007/s004939970001
- Kazuoki Azuma, Weighted sums of certain dependent random variables, Tohoku Math. J. (2) 19 (1967), 357–367. MR 221571, DOI 10.2748/tmj/1178243286
- János Barát and Zoltán Lóránt Nagy, Transversals in generalized Latin squares, Ars Math. Contemp. 16 (2019), no. 1, 39–47. MR 3904714, DOI 10.26493/1855-3974.1316.2d2
- Darcy Best, Kevin Hendrey, Ian M. Wanless, Tim E. Wilson, and David R. Wood, Transversals in Latin arrays with many distinct symbols, J. Combin. Des. 26 (2018), no. 2, 84–96. MR 3745158, DOI 10.1002/jcd.21566
- A. E. Brouwer, On the size of a maximum transversal in a Steiner triple system, Canadian J. Math. 33 (1981), no. 5, 1202–1204. MR 638375, DOI 10.4153/CJM-1981-090-7
- A. E. Brouwer, A. J. de Vries, and R. M. A. Wieringa, A lower bound for the length of partial transversals in a Latin square, Nieuw Arch. Wisk. (3) 26 (1978), no. 2, 330–332. MR 480083
- Richard A. Brualdi and Herbert J. Ryser, Combinatorial matrix theory, Encyclopedia of Mathematics and its Applications, vol. 39, Cambridge University Press, Cambridge, 1991. MR 1130611, DOI 10.1017/CBO9781107325708
- David A. Drake, Maximal sets of Latin squares and partial transversals, J. Statist. Plann. Inference 1 (1977), no. 2, 143–149. MR 485434, DOI 10.1016/0378-3758(77)90019-2
- S. Eberhard, F. Manners, and R. Mrazović, An asymptotic for the Hall–Paige conjecture, Preprint arXiv:2003.01798, 2020.
- L. Euler, Recherches sur un nouvelle espéce de quarrés magiques, Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, pages 85–239, 1782.
- P. Frankl and V. Rödl, Near perfect coverings in graphs and hypergraphs, European J. Combin. 6 (1985), no. 4, 317–326. MR 829351, DOI 10.1016/S0195-6698(85)80045-7
- Marshall Hall and L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 5 (1955), 541–549. MR 79589, DOI 10.2140/pjm.1955.5.541
- Pooya Hatami and Peter W. Shor, A lower bound for the length of a partial transversal in a Latin square, J. Combin. Theory Ser. A 115 (2008), no. 7, 1103–1113. MR 2450332, DOI 10.1016/j.jcta.2008.01.002
- Peter Keevash and Liana Yepremyan, On the number of symbols that forces a transversal, Combin. Probab. Comput. 29 (2020), no. 2, 234–240. MR 4079635, DOI 10.1017/s0963548319000282
- Jeong Han Kim, Benny Sudakov, and Van H. Vu, On the asymmetry of random regular graphs and random graphs, Random Structures Algorithms 21 (2002), no. 3-4, 216–224. Random structures and algorithms (Poznan, 2001). MR 1945368, DOI 10.1002/rsa.10054
- Klaas K. Koksma, A lower bound for the order of a partial transversal in a Latin square, J. Combinatorial Theory 7 (1969), 94–95. MR 239988, DOI 10.1016/S0021-9800(69)80009-8
- C. C. Lindner and K. T. Phelps, A note on partial parallel classes in Steiner systems, Discrete Math. 24 (1978), no. 1, 109–112. MR 522740, DOI 10.1016/0012-365X(78)90179-6
- Michael Molloy and Bruce Reed, Graph colouring and the probabilistic method, Algorithms and Combinatorics, vol. 23, Springer-Verlag, Berlin, 2002. MR 1869439, DOI 10.1007/978-3-642-04016-0
- Richard Montgomery, Alexey Pokrovskiy, and Benjamin Sudakov, Decompositions into spanning rainbow structures, Proc. Lond. Math. Soc. (3) 119 (2019), no. 4, 899–959. MR 3964824, DOI 10.1112/plms.12245
- Alexey Pokrovskiy and Benny Sudakov, A counterexample to Stein’s equi-$n$-square conjecture, Proc. Amer. Math. Soc. 147 (2019), no. 6, 2281–2287. MR 3951411, DOI 10.1090/proc/14220
- Vojtěch Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78. MR 793489, DOI 10.1016/S0195-6698(85)80023-8
- H. J. Ryser, Neuere probleme der kombinatorik, Vorträge über Kombinatorik, Oberwolfach, 69 (1967), 91.
- P. W. Shor, A lower bound for the length of a partial transversal in a Latin square, J. Combin. Theory Ser. A 33 (1982), no. 1, 1–8. MR 665651, DOI 10.1016/0097-3165(82)90074-7
- S. K. Stein, Transversals of Latin squares and their generalizations, Pacific J. Math. 59 (1975), no. 2, 567–575. MR 387083, DOI 10.2140/pjm.1975.59.567
- Shinmin Patrick Wang, ON SELF-ORTHOGONAL LATIN SQUARES AND PARTIAL TRANSVERSALS OF LATIN SQUARES, ProQuest LLC, Ann Arbor, MI, 1978. Thesis (Ph.D.)–The Ohio State University. MR 2627641
- Stewart Wilcox, Reduction of the Hall-Paige conjecture to sporadic simple groups, J. Algebra 321 (2009), no. 5, 1407–1428. MR 2494397, DOI 10.1016/j.jalgebra.2008.11.033
- David E. Woolbright, An $n\times n$ Latin square has a transversal with at least $n-\surd n$ distinct symbols, J. Combinatorial Theory Ser. A 24 (1978), no. 2, 235–237. MR 472562, DOI 10.1016/0097-3165(78)90009-2
Additional Information
- Peter Keevash
- Affiliation: Mathematical Institute, University of Oxford, Oxford, United Kingdom
- MR Author ID: 670477
- Email: keevash@maths.ox.ac.uk
- Alexey Pokrovskiy
- Affiliation: Department of Mathematics, University College London, United Kingdom
- MR Author ID: 884033
- Email: dr.alexey.pokrovskiy@gmail.com
- Benny Sudakov
- Affiliation: Department of Mathematics, ETH, 8092 Zürich, Switzerland
- MR Author ID: 602546
- Email: benny.sudakov@gmail.com
- Liana Yepremyan
- Affiliation: Department of Mathematics, Emory University, Atlanta
- MR Author ID: 1120553
- Email: liana.yepremyan@emory.edu
- Received by editor(s): February 25, 2021
- Received by editor(s) in revised form: July 22, 2021
- Published electronically: April 15, 2022
- Additional Notes: The research of the first author was supported in part by ERC Consolidator Grant 647678. The research of the third author was supported in part by SNSF grant 200021_196965. The research of the fourth author was supported by Marie Sklodowska Curie Global Fellowship, H2020-MSCA-IF-2018:846304
- © Copyright 2022 by the authors under Creative Commons Attribution 3.0 License (CC BY 3.0)
- Journal: Trans. Amer. Math. Soc. Ser. B 9 (2022), 288-321
- MSC (2020): Primary 05D40, 05C65, 05B15, 05D15
- DOI: https://doi.org/10.1090/btran/92
- MathSciNet review: 4408405