An n×nn\times n array in which no symbol occurs more than βn\beta n times is called a β\beta-bounded nn-square; the special case of nn symbols each occurring exactly nn times is an equi-nn-square. Anastos and Morris (2024) gave a deterministic polynomial-time algorithm finding a transversal (entries with distinct rows, columns, and symbols) of size (1−β/4−ε)n(1-\beta/4-\varepsilon)n in any such array, while Chakraborti, Christoph, Hunter, Montgomery and Petrov independently proved existentially that every equi-nn-square has a transversal of size n−o(n)n-o(n). The open problem is whether the strongest existential guarantee can be achieved by a deterministic polynomial-time algorithm — that is, whether every equi-nn-square can be given a deterministic polynomial-time construction of an n−o(n)n-o(n) transversal.

Background

A transversal of an n×nn\times n array filled with symbols is a set of entries no two of which lie in the same row, the same column, or contain the same symbol; a transversal of size nn is called full. A Latin square of order nn is an n×nn\times n array in which each of nn symbols appears exactly once in every row and every column. The Ryser–Brualdi–Stein conjecture, originating with Ryser in 1967 and developed by Brualdi and Stein, predicts that every Latin square of order nn has a transversal of size n−1n-1, and one of size nn when nn is odd. After the bound n−O(log⁡n/log⁡log⁡n)n-O(\log n/\log\log n) of Keevash, Pokrovskiy, Sudakov and Yepremyan, Montgomery proved the n−1n-1 part for all sufficiently large nn; the odd-order (full transversal) part, Ryser's conjecture, remains open.

In 1975 Stein proposed dropping the row and column conditions: an equi-nn-square is an n×nn\times n array filled with nn symbols each appearing exactly nn times, and he conjectured that every equi-nn-square still has a transversal of size n−1n-1. Pokrovskiy and Sudakov disproved this in 2019, constructing equi-nn-squares with no transversal larger than n−log⁡n42n-\frac{\log n}{42}, but their work asked whether the conjecture is approximately true. Successive lower bounds on the largest transversal guaranteed in every equi-nn-square are (1−1/e−o(1))n(1-1/e-o(1))n (Stein), 2n/32n/3 (Aharoni, Berger, Kotlar and Ziv, via topological methods), (3/4−ε)n(3/4-\varepsilon)n (Anastos and Morris), and finally n−o(n)n-o(n) — indeed n−n1−Ω(1)n-n^{1-\Omega(1)}, together with n−n1−Ω(1)n-n^{1-\Omega(1)} pairwise disjoint such transversals — by Chakraborti, Christoph, Hunter, Montgomery and Petrov, who also improved the counterexample to equi-nn-squares with no transversal larger than n−(1/(22)+o(1))nn-(1/(2\sqrt 2)+o(1))\sqrt n and conjectured that a guarantee of n−Cnn-C\sqrt n is optimal. Their existence proof uses the semi-random method (building the transversal in many small random increments, known as nibble steps) together with a novel randomized matching step and absorption (setting aside a flexible reservoir of entries that is used to repair whatever defects remain at the end), and is purely existential.

A common generalization of Latin squares and equi-nn-squares is the β\beta-bounded nn-square: an n×nn\times n array in which no symbol appears more than βn\beta n times. Erdős and Spencer, introducing the lopsided Lovász local lemma (LLL) in 1991 — a probabilistic principle guaranteeing that a finite family of undesirable events can be simultaneously avoided when their dependencies are sufficiently sparse and one-sided — proved that every β\beta-bounded nn-square with β<1/16\beta<1/16 has a full transversal; Bissacot, Fernández, Procacci and Scoppola improved the sufficient constant to β≤27/256\beta\le 27/256 using a cluster-expansion improvement of the LLL (a refinement based on ideas from statistical mechanics that takes into account how overlapping clusters of mutually dependent events compensate one another). Since Moser and Tardos made the LLL constructive (exhibiting a randomized algorithm that efficiently finds an object whose existence the LLL guarantees), the transversal problem has served as a benchmark application for algorithmic versions of the LLL: Harris and Srinivasan, and later Harris alone, analyzed randomized polynomial-time algorithms for finding large (but not full) transversals in β\beta-bounded nn-squares. Anastos and Morris gave the first deterministic polynomial-time algorithm for the problem: for every ε>0\varepsilon>0 and 0<β≤10<\beta\le 1 it finds, in polynomial time, a transversal of size (1−β/4−ε)n(1-\beta/4-\varepsilon)n in any β\beta-bounded nn-square — hence (3/4−ε)n(3/4-\varepsilon)n in equi-nn-squares — improving on the LLL-based algorithmic bounds whenever β≥0.14\beta\ge 0.14, but remaining strictly below the best existential guarantee of n−o(n)n-o(n). The problem below asks to close this existential-versus-constructive gap for equi-nn-squares.

Problem Statement

For equi-nn-squares — n×nn\times n arrays of symbols in which nn symbols each appear exactly nn times — the problem is to determine whether the optimal guaranteed size of a transversal, a set of entries with pairwise distinct rows, columns, and symbols, can be achieved on the deterministic constructive side as it has been on the existential side. Concretely:

Does there exist, for every ε>0\varepsilon>0, an n0n_0 and a deterministic algorithm with running time polynomial in nn that, given any equi-nn-square of order n≥n0n\ge n_0, outputs a transversal of size at least (1−ε)n(1-\varepsilon)n? That is, can the strongest existential guarantee — a transversal of size n−o(n)n-o(n) in every equi-nn-square, proved by Chakraborti, Christoph, Hunter, Montgomery and Petrov — be matched by a deterministic polynomial-time construction, rather than the currently best constructive (3/4−ε)n(3/4-\varepsilon)n of Anastos and Morris?

References

  1. Michael Anastos and Patrick Morris, A Note on Finding Large Transversals Efficiently, Journal of Combinatorial Designs 33(9) (2025), 338–342, DOI 10.1002/jcd.21990; preprint arXiv:2412.05891 (v2, June 2026), https://arxiv.org/abs/2412.05891
  2. Debsoumya Chakraborti, Micha Christoph, Zach Hunter, Richard Montgomery, and Teo Petrov, Almost-full transversals in equi-nn-squares, arXiv:2412.07733 (2024), https://arxiv.org/abs/2412.07733
  3. Sherman Stein, Transversals of Latin squares and their generalizations, Pacific Journal of Mathematics 59(2) (1975), 567–575, DOI 10.2140/pjm.1975.59.567, https://doi.org/10.2140/pjm.1975.59.567
  4. Ron Aharoni, Eli Berger, Dani Kotlar, and Ran Ziv, On a conjecture of Stein, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 87(2) (2017), 203–211, DOI 10.1007/s12188-016-0160-3, https://doi.org/10.1007/s12188-016-0160-3
  5. Alexey Pokrovskiy and Benny Sudakov, A counterexample to Stein's Equi-nn-square conjecture, Proceedings of the American Mathematical Society 147(6) (2019), 2281–2287, DOI 10.1090/proc/14220, https://doi.org/10.1090/proc/14220
  6. Richard Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large even nn, arXiv:2310.19779 (2023), https://arxiv.org/abs/2310.19779
  7. Peter Keevash, Alexey Pokrovskiy, Benny Sudakov, and Liana Yepremyan, New bounds for Ryser's conjecture and related problems, Transactions of the American Mathematical Society, Series B 9(8) (2022), 288–321, DOI 10.1090/btran/92, https://doi.org/10.1090/btran/92
  8. Paul Erdős and Joel Spencer, Lopsided Lovász local lemma and Latin transversals, Discrete Applied Mathematics 30(2–3) (1991), 151–154, DOI 10.1016/0166-218X(91)90040-4, https://doi.org/10.1016/0166-218X(91)90040-4
  9. Rodrigo Bissacot, Roberto Fernández, Aldo Procacci, and Benedetto Scoppola, An Improvement of the Lovász Local Lemma via Cluster Expansion, Combinatorics, Probability and Computing 20(5) (2011), 709–719, DOI 10.1017/S0963548311000253, https://doi.org/10.1017/S0963548311000253
  10. Robin A. Moser and Gábor Tardos, A constructive proof of the general Lovász local lemma, Journal of the ACM 57(2) (2010), 1–15, DOI 10.1145/1667053.1667060, https://doi.org/10.1145/1667053.1667060
  11. David G. Harris and Aravind Srinivasan, Algorithmic and Enumerative Aspects of the Moser-Tardos Distribution, ACM Transactions on Algorithms 13(3) (2017), 1–40, DOI 10.1145/3039869, https://doi.org/10.1145/3039869
  12. David G. Harris, New bounds for the Moser-Tardos distribution, Random Structures & Algorithms 57(1) (2020), 97–131, DOI 10.1002/rsa.20914, https://doi.org/10.1002/rsa.20914
  13. Benny Sudakov, Restricted subgraphs of edge-colored graphs and applications, arXiv:2412.13945 (2024), https://arxiv.org/abs/2412.13945
  14. Richard A. Brualdi and Herbert J. Ryser, Combinatorial Matrix Theory, Cambridge University Press, 1991, ISBN 978-0-521-32265-2, DOI 10.1017/CBO9781107325708, https://doi.org/10.1017/CBO9781107325708
  15. Afsane Ghafari and Ian M. Wanless, Latin Squares whose transversals intersect in unusual ways, arXiv:2607.17547 (2026), https://arxiv.org/abs/2607.17547