A counterexample to Stein’s Equi-$n$-square Conjecture
HTML articles powered by AMS MathViewer
- by Alexey Pokrovskiy and Benny Sudakov
- Proc. Amer. Math. Soc. 147 (2019), 2281-2287
- DOI: https://doi.org/10.1090/proc/14220
- Published electronically: March 1, 2019
- PDF | Request permission
Abstract:
In 1975 Stein conjectured that in every $n\times n$ array filled with the numbers $1, \dots , n$ with every number occuring exactly $n$ times, there is a partial transversal of size $n-1$. In this note we show that this conjecture is false by constructing such arrays without partial transverals of size $n-\frac {1}{42}\ln n$.References
- Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, and Ran Ziv, Fair representation by independent sets, A journey through discrete mathematics, Springer, Cham, 2017, pp. 31–58. MR 3726593
- Ron Aharoni, János Barát, and Ian M. Wanless, Multipartite hypergraphs achieving equality in Ryser’s conjecture, Graphs Combin. 32 (2016), no. 1, 1–15. MR 3436945, DOI 10.1007/s00373-015-1575-9
- 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
- N. Alon, Personal communication, 2018.
- Noga Alon and Joel H. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. MR 1140703
- Noga Alon, Joel Spencer, and Prasad Tetali, Covering with Latin transversals, Discrete Appl. Math. 57 (1995), no. 1, 1–10. MR 1317190, DOI 10.1016/0166-218X(93)E0136-M
- 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
- Paul Erdős and Joel Spencer, Lopsided Lovász local lemma and Latin transversals, Discrete Appl. Math. 30 (1991), no. 2-3, 151–154. ARIDAM III (New Brunswick, NJ, 1988). MR 1095369, DOI 10.1016/0166-218X(91)90040-4
- L. Euler, Recherches sur une nouvelle espéce de quarrés magiques, Verh. Zeeuwsch. Gennot. Weten. Vliss., 9:85–239, 1782.
- J. Dénes, Research problems, Period. Math. Hungar. 17 (1986), no. 3, 245–246. MR 1553641, DOI 10.1007/BF01848652
- Geňa Hahn and Carsten Thomassen, Path and cycle sub-Ramsey numbers and an edge-colouring conjecture, Discrete Math. 62 (1986), no. 1, 29–33. MR 862350, DOI 10.1016/0012-365X(86)90038-5
- A. Donald Keedwell and József Dénes, Latin squares and their applications, 2nd ed., Elsevier/North-Holland, Amsterdam, 2015. With a foreword to the previous edition by Paul Erdös. MR 3495977
- R. Montgomery, A. Pokrovskiy, and B. Sudakov, Decompositions into spanning rainbow structures, preprint, 2018.
- H. Ryser, Neuere probleme der kombinatorik, Vorträge über Kombinatorik, Oberwolfach, 69–91, 1967.
- S. K. Stein, Transversals of Latin squares and their generalizations, Pacific J. Math. 59 (1975), no. 2, 567–575. MR 387083
Bibliographic Information
- Alexey Pokrovskiy
- Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland
- MR Author ID: 884033
- Email: dr.alexey.pokrovskiy@gmail.com
- Benny Sudakov
- Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland
- MR Author ID: 602546
- Email: benjamin.sudakov@math.ethz.ch
- Received by editor(s): February 28, 2018
- Received by editor(s) in revised form: May 9, 2018
- Published electronically: March 1, 2019
- Additional Notes: The research of the first author was supported in part by SNSF grant 200021-175573.
The research of the second author was supported in part by SNSF grant 200021-175573. - Communicated by: Patricia L. Hersh
- © Copyright 2019 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 147 (2019), 2281-2287
- MSC (2010): Primary 05B15
- DOI: https://doi.org/10.1090/proc/14220
- MathSciNet review: 3951411