A counterexample to Stein’s Equi-𝑛-square Conjecture

Pokrovskiy, Alexey; Sudakov, Benny

doi:10.1090/proc/14220

A counterexample to Stein’s Equi-$n$-square Conjecture
HTML articles powered by AMS MathViewer

by Alexey Pokrovskiy and Benny Sudakov PDF

Proc. Amer. Math. Soc. 147 (2019), 2281-2287 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