Stein conjectured in 1975 that every equi-nn-square — an n×nn\times n array filled with nn symbols, each appearing exactly nn times — has a transversal of size n−1n-1, where a transversal is a set of cells sharing no row, column, or symbol. Pokrovskiy and Sudakov disproved this in 2019, constructing equi-nn-squares with no transversal larger than n−142log⁡nn-\tfrac{1}{42}\log n, while asking whether an asymptotic version holds. Chakraborti, Christoph, Hunter, Montgomery and Petrov confirmed the asymptotic version in 2024: every equi-nn-square has a transversal of size at least n−n1−εn-n^{1-\varepsilon} for some absolute ε>0\varepsilon>0 (indeed an almost-decomposition into such transversals), and there exist equi-nn-squares with no transversal of size n−(122+o(1))nn-(\tfrac{1}{2\sqrt2}+o(1))\sqrt{n}. This record states the sharp question they pose in response (their Conjecture 1.3): whether some absolute constant CC guarantees every equi-nn-square a transversal of size at least n−Cnn-C\sqrt{n}, and if so whether the optimal constant is 122\tfrac{1}{2\sqrt2}.

Background

A Latin square of order nn is an n×nn\times n array filled with nn symbols so that each symbol appears exactly once in every row and every column. A transversal (also called a partial transversal) is a set of cells of the array, no two of which share a row, a column, or a symbol; its size is its number of cells. The Ryser–Brualdi–Stein conjecture, originating in the 1960s, predicts that every Latin square of order nn has a transversal with n−1n-1 cells (and one with nn cells when nn is odd); Montgomery proved the n−1n-1 claim for all sufficiently large even nn in 2023. In 1975, Stein proposed a far-reaching generalization: an equi-nn-square is an n×nn\times n array filled with nn symbols in which each symbol appears exactly nn times, with no restriction on how often a symbol may repeat within a row or column (every Latin square is an equi-nn-square). Stein conjectured that every equi-nn-square has a transversal of size n−1n-1, and showed by the probabilistic method that every one has a transversal of size at least (1−e−1)n≈0.632n(1-e^{-1})n\approx 0.632n. Aharoni, Berger, Kotlar and Ziv improved this to 2n/32n/3 by topological methods in 2017. In 2019, Pokrovskiy and Sudakov disproved Stein's conjecture by constructing equi-nn-squares with no transversal of size larger than n−142log⁡nn-\tfrac{1}{42}\log n, but asked whether the conjecture is approximately true, i.e. whether every equi-nn-square has a transversal of size (1−o(1))n(1-o(1))n. Chakraborti, Christoph, Hunter, Montgomery and Petrov (arXiv:2412.07733, 2024) answered this positively: there is an absolute ε>0\varepsilon>0 such that every equi-nn-square contains at least n−n1−εn-n^{1-\varepsilon} pairwise disjoint transversals, each of size at least n−n1−εn-n^{1-\varepsilon}. Their proof works through a chromatic-index result (Theorem 4.3) for 3-uniform hypergraphs of maximum degree DD whose graph of large-codegree pairs is bipartite, where the chromatic index is the least number of colours needed to colour the edges so that any two intersecting edges receive distinct colours, and the codegree of two vertices is the number of edges containing both. Modifying the Pokrovskiy–Sudakov obstruction through a box-pairing construction (the n×nn\times n square is partitioned into boxes, pairs of boxes share a color, and a counting argument forces every transversal to miss many colors), they also showed the o(n)o(n) loss is necessary: for every nn there is an equi-nn-square with no transversal of size n−(122+o(1))nn-(\tfrac{1}{2\sqrt2}+o(1))\sqrt{n}. These two results leave the fundamental gap between the guaranteed size n−n1−εn-n^{1-\varepsilon} and the extremal obstruction n−Ω(n)n-\Omega(\sqrt{n}). The authors state their Conjecture 1.3 as the proposed replacement for Stein's disproved conjecture, and suggest the constant 122\tfrac{1}{2\sqrt2} in their construction is unimprovable, i.e. that the worst-case deficit is exactly (122+o(1))n(\tfrac{1}{2\sqrt2}+o(1))\sqrt{n}. In the standard hypergraph formulation, an equi-nn-square is an nn-regular 3-partite 3-uniform hypergraph with nn vertices in each of the three classes (rows, columns, symbols), and a transversal is a matching; the question asks how close to perfect a matching must be in such a hypergraph when it is linear between the row and column classes, that is, when each row-column pair of vertices lies together in at most one edge.

Problem Statement

Determine the correct worst-case scale, and the optimal constant, of the unavoidable deficit from nn in transversals of equi-nn-squares (an n×nn\times n array filled with nn symbols, each appearing exactly nn times; a transversal is a set of cells sharing no row, column, or symbol). Concretely, Conjecture 1.3 of Chakraborti–Christoph–Hunter–Montgomery–Petrov: does there exist an absolute constant C>0C>0 such that every equi-nn-square has a transversal of size at least n−Cnn-C\sqrt{n}? If yes, determine the smallest such constant — in particular, whether the sharp statement holds that every equi-nn-square has a transversal of size at least n−(122+o(1))nn-(\tfrac{1}{2\sqrt2}+o(1))\sqrt{n}, which would make the authors' box-pairing constructions extremal. If no, exhibit equi-nn-squares of arbitrarily large orders nn whose largest transversal has size below n−Cnn-C\sqrt{n} for arbitrarily large constants CC, and determine as precisely as possible the worst-case scale of the deficit, which by the known results lies somewhere between Ω(n)\Omega(\sqrt{n}) and O(n1−ε)O(n^{1-\varepsilon}) for some absolute ε>0\varepsilon>0.

References

  1. Debsoumya Chakraborti, Micha Christoph, Zach Hunter, Richard Montgomery, Teo Petrov, 'Almost-full transversals in equi-nn-squares', arXiv:2412.07733 (2024). DOI: 10.48550/arXiv.2412.07733. URL: https://arxiv.org/abs/2412.07733
  2. Sherman Stein, 'Transversals of Latin squares and their generalizations', Pacific Journal of Mathematics 59:567–575 (1975). DOI: 10.2140/pjm.1975.59.567. URL: https://doi.org/10.2140/pjm.1975.59.567
  3. Ron Aharoni, Eli Berger, Dani Kotlar, Ran Ziv, 'On a conjecture of Stein', Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 87:203–211 (2017). DOI: 10.1007/s12188-016-0160-3. URL: https://doi.org/10.1007/s12188-016-0160-3
  4. Alexey Pokrovskiy, Benny Sudakov, 'A counterexample to Stein's equi-nn-square conjecture', Proceedings of the American Mathematical Society 147(6):2281–2287 (2019). DOI: 10.1090/proc/14220. URL: https://doi.org/10.1090/proc/14220
  5. Richard Montgomery, 'A proof of the Ryser–Brualdi–Stein conjecture for large even nn', arXiv:2310.19779 (2023). DOI: 10.48550/arXiv.2310.19779. URL: https://arxiv.org/abs/2310.19779
  6. Michael Anastos, Patrick Morris, 'A note on finding large transversals efficiently', Journal of Combinatorial Designs 33(9):338–342 (2025); arXiv:2412.05891. DOI: 10.1002/jcd.21990. URL: https://arxiv.org/abs/2412.05891
  7. Amarja Kathapurkar, Patrick Morris, Guillem Perarnau, 'A rainbow Dirac theorem for loose Hamilton cycles in hypergraphs', arXiv:2501.07644 (2025). DOI: 10.48550/arXiv.2501.07644. URL: https://arxiv.org/abs/2501.07644
  8. Benny Sudakov, 'Restricted subgraphs of edge-colored graphs and applications', arXiv:2412.13945 (2024). DOI: 10.48550/arXiv.2412.13945. URL: https://arxiv.org/abs/2412.13945
  9. Ronen Wdowinski, 'Hall's theorem for reconfigurations and higher dimensional topological connectedness', arXiv:2511.04863 (2025). DOI: 10.48550/arXiv.2511.04863. URL: https://arxiv.org/abs/2511.04863
  10. Andrew Pendleton, 'Enumeration and Distribution of Permutation Rows and Columns in Equi-nn-Squares', arXiv:2510.11980 (2025). DOI: 10.48550/arXiv.2510.11980. URL: https://arxiv.org/abs/2510.11980
  11. Emma Hogan, Alex Scott, Dmitry Tsarev, 'Colour-balanced subgraphs', arXiv:2604.09449 (2026). DOI: 10.48550/arXiv.2604.09449. URL: https://arxiv.org/abs/2604.09449