New bounds for Ryser’s conjecture and related problems. (English) Zbl 1490.05269
A transversal is a collection of cells of the Latin square which do not share the same row, column, or symbol. A full transversal is a transversal of order \(n\). The study of Latin squares goes back to the work of Euler in the 18th century. Latin squares have connections to 2-dimensional permutations, design theory, finite projective planes, and error-correcting codes.
One of the most famous open problems on transversals in general Latin squares is a conjecture of Ryser-Brualdi-Stein from the 60s which says that every \(n \times n\) Latin square has a transversal of order \(n-1\), and it has a full transversal for odd \(n\).
In this paper, the authors prove the existence of a transversal of order \(n-O\)(log \(n\)/log log \(n)\), improving the celebrated bound of \(n- O(\)log\(^2 n)\) by P. Hatami and P. W. Shor [J. Comb. Theory, Ser. A 115, No. 7, 1103–1113 (2008; Zbl 1159.05303)]. Their approach (different from that of Hatami-Shor) is quite general and gives several other applications as well. They obtain a new lower bound on a 40-year-old conjecture of A. E. Brouwer [Can. J. Math. 33, 1202–1204 (1981; Zbl 0481.05016)] 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 N. Alon et al. [Isr. J. Math. 100, 171–187 (1997; Zbl 0882.05107)] which has the error term of order \(n^{1/2+o(1)}\). Finally, they 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-\epsilon}\). The proofs combine in a novel way the semi-random method together with the robust expansion properties of edge-colored 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.
One of the most famous open problems on transversals in general Latin squares is a conjecture of Ryser-Brualdi-Stein from the 60s which says that every \(n \times n\) Latin square has a transversal of order \(n-1\), and it has a full transversal for odd \(n\).
In this paper, the authors prove the existence of a transversal of order \(n-O\)(log \(n\)/log log \(n)\), improving the celebrated bound of \(n- O(\)log\(^2 n)\) by P. Hatami and P. W. Shor [J. Comb. Theory, Ser. A 115, No. 7, 1103–1113 (2008; Zbl 1159.05303)]. Their approach (different from that of Hatami-Shor) is quite general and gives several other applications as well. They obtain a new lower bound on a 40-year-old conjecture of A. E. Brouwer [Can. J. Math. 33, 1202–1204 (1981; Zbl 0481.05016)] 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 N. Alon et al. [Isr. J. Math. 100, 171–187 (1997; Zbl 0882.05107)] which has the error term of order \(n^{1/2+o(1)}\). Finally, they 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-\epsilon}\). The proofs combine in a novel way the semi-random method together with the robust expansion properties of edge-colored 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.
Reviewer: Zihong Tian (Shijiazhuang)
MSC:
| 05D40 | Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) |
| 05C65 | Hypergraphs |
| 05B15 | Orthogonal arrays, Latin squares, Room squares |
| 05D15 | Transversal (matching) theory |
| 05B07 | Triple systems |
Keywords:
Latin square; transversal; Latin array; Steiner triple system; rainbow matching; semi-random methodReferences:
| [1] | Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran, On a conjecture of Stein, Abh. Math. Semin. Univ. Hambg., 87, 2, 203-211 (2017) · Zbl 1379.05115 · doi:10.1007/s12188-016-0160-3 |
| [2] | Akbari, Saieed; Alipour, Alireza, Transversals and multicolored matchings, J. Combin. Des., 12, 5, 325-332 (2004) · Zbl 1053.05017 · doi:10.1002/jcd.20014 |
| [3] | Alon, Noga; Kim, Jeong-Han; Spencer, Joel, Nearly perfect matchings in regular simple hypergraphs, Israel J. Math., 100, 171-187 (1997) · Zbl 0882.05107 · doi:10.1007/BF02773639 |
| [4] | Alon, Noga; Krivelevich, Michael; Sudakov, Benny, List coloring of random and pseudo-random graphs, Combinatorica, 19, 4, 453-472 (1999) · Zbl 0985.05046 · doi:10.1007/s004939970001 |
| [5] | Azuma, Kazuoki, Weighted sums of certain dependent random variables, Tohoku Math. J. (2), 19, 357-367 (1967) · Zbl 0178.21103 · doi:10.2748/tmj/1178243286 |
| [6] | Bar\'{a}t, J\'{a}nos; Nagy, Zolt\'{a}n L\'{o}r\'{a}nt, Transversals in generalized Latin squares, Ars Math. Contemp., 16, 1, 39-47 (2019) · Zbl 1416.05054 · doi:10.26493/1855-3974.1316.2d2 |
| [7] | Best, Darcy; Hendrey, Kevin; Wanless, Ian M.; Wilson, Tim E.; Wood, David R., Transversals in Latin arrays with many distinct symbols, J. Combin. Des., 26, 2, 84-96 (2018) · Zbl 1391.05061 · doi:10.1002/jcd.21566 |
| [8] | Brouwer, A. E., On the size of a maximum transversal in a Steiner triple system, Canadian J. Math., 33, 5, 1202-1204 (1981) · Zbl 0481.05016 · doi:10.4153/CJM-1981-090-7 |
| [9] | Brouwer, A. E.; de Vries, A. J.; Wieringa, R. M. A., A lower bound for the length of partial transversals in a Latin square, Nieuw Arch. Wisk. (3), 26, 2, 330-332 (1978) · Zbl 0395.05012 |
| [10] | Brualdi, Richard A.; Ryser, Herbert J., Combinatorial matrix theory, Encyclopedia of Mathematics and Its Applications 39, x+367 pp. (1991), Cambridge University Press, Cambridge · Zbl 1286.05001 · doi:10.1017/CBO9781107325708 |
| [11] | Drake, David A., Maximal sets of Latin squares and partial transversals, J. Statist. Plann. Inference, 1, 2, 143-149 (1977) · Zbl 0392.05014 · doi:10.1016/0378-3758(77)90019-2 |
| [12] | eberhard2020asymptotic S. Eberhard, F. Manners, and R. Mrazovi\'c, An asymptotic for the Hall-Paige conjecture, Preprint 2003.01798, 2020. |
| [13] | euler1782recherches L. Euler, Recherches sur un nouvelle esp\'ece de quarr\'es magiques, Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, pages 85-239, 1782. |
| [14] | Frankl, P.; R\"{o}dl, V., Near perfect coverings in graphs and hypergraphs, European J. Combin., 6, 4, 317-326 (1985) · Zbl 0624.05055 · doi:10.1016/S0195-6698(85)80045-7 |
| [15] | Hall, Marshall; Paige, L. J., Complete mappings of finite groups, Pacific J. Math., 5, 541-549 (1955) · Zbl 0066.27703 |
| [16] | Hatami, Pooya; Shor, Peter W., A lower bound for the length of a partial transversal in a Latin square, J. Combin. Theory Ser. A, 115, 7, 1103-1113 (2008) · Zbl 1159.05303 · doi:10.1016/j.jcta.2008.01.002 |
| [17] | Keevash, Peter; Yepremyan, Liana, On the number of symbols that forces a transversal, Combin. Probab. Comput., 29, 2, 234-240 (2020) · Zbl 1466.05217 · doi:10.1017/s0963548319000282 |
| [18] | Kim, Jeong Han; Sudakov, Benny; Vu, Van H., On the asymmetry of random regular graphs and random graphs, Random Structures Algorithms, 21, 3-4, 216-224 (2002) · Zbl 1012.05143 · doi:10.1002/rsa.10054 |
| [19] | Koksma, Klaas K., A lower bound for the order of a partial transversal in a Latin square, J. Combinatorial Theory, 7, 94-95 (1969) · Zbl 0172.01504 |
| [20] | Lindner, C. C.; Phelps, K. T., A note on partial parallel classes in Steiner systems, Discrete Math., 24, 1, 109-112 (1978) · Zbl 0401.05020 · doi:10.1016/0012-365X(78)90179-6 |
| [21] | Molloy, Michael; Reed, Bruce, Graph colouring and the probabilistic method, Algorithms and Combinatorics 23, xiv+326 pp. (2002), Springer-Verlag, Berlin · Zbl 0987.05002 · doi:10.1007/978-3-642-04016-0 |
| [22] | Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benjamin, Decompositions into spanning rainbow structures, Proc. Lond. Math. Soc. (3), 119, 4, 899-959 (2019) · Zbl 1429.05024 · doi:10.1112/plms.12245 |
| [23] | Pokrovskiy, Alexey; Sudakov, Benny, A counterexample to Stein’s equi-\(n\)-square conjecture, Proc. Amer. Math. Soc., 147, 6, 2281-2287 (2019) · Zbl 1411.05041 · doi:10.1090/proc/14220 |
| [24] | R\"{o}dl, Vojt\v{e}ch, On a packing and covering problem, European J. Combin., 6, 1, 69-78 (1985) · Zbl 0565.05016 · doi:10.1016/S0195-6698(85)80023-8 |
| [25] | ryser1967neuere H. J. Ryser, Neuere probleme der kombinatorik, Vortr\"age \"uber Kombinatorik, Oberwolfach, 69 (1967), 91. |
| [26] | Shor, P. W., A lower bound for the length of a partial transversal in a Latin square, J. Combin. Theory Ser. A, 33, 1, 1-8 (1982) · Zbl 0489.05012 · doi:10.1016/0097-3165(82)90074-7 |
| [27] | Stein, S. K., Transversals of Latin squares and their generalizations, Pacific J. Math., 59, 2, 567-575 (1975) · Zbl 0302.05015 |
| [28] | Wang, Shinmin Patrick, On self-orthogonal Latin squares and partial transversals of Latin squares, 145 pp. (1978), ProQuest LLC, Ann Arbor, MI |
| [29] | Wilcox, Stewart, Reduction of the Hall-Paige conjecture to sporadic simple groups, J. Algebra, 321, 5, 1407-1428 (2009) · Zbl 1172.20024 · doi:10.1016/j.jalgebra.2008.11.033 |
| [30] | Woolbright, David E., An \(n\times n\) Latin square has a transversal with at least \(n-\surd n\) distinct symbols, J. Combinatorial Theory Ser. A, 24, 2, 235-237 (1978) · Zbl 0368.05012 · doi:10.1016/0097-3165(78)90009-2 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
