The optimal symbol-multiplicity threshold guaranteeing a full Latin transversal in an $n\times n$ array

Erdős and Spencer (1991) introduced the lopsided Lovász Local Lemma and used it to prove that every $n\times n$ array of symbols in which no symbol occurs more than $(n-1)/16$ times has a Latin transversal: a selection of $n$ cells, one in each row and each column, whose symbols are pairwise distinct. The natural quantitative question left open is how far this multiplicity bound can be pushed. Later work raised the sufficient constant from $1/16$ to $1/(4e)$ (the standard symmetric lopsided criterion) and then to $27/256$ (Bissacot, Fernández, Procacci and Scoppola, via the cluster-expansion improvement of the Local Lemma, with a polynomial-time algorithm due to Harris and Srinivasan); this remains the best published constant. On the other side, constructions descending from Pokrovskiy and Sudakov's refutation of Stein's conjecture that every equi-$n$-square — an $n\times n$ array in which each symbol occurs exactly $n$ times — has a partial transversal of size $n-1$ show that multiplicity $n-\Omega(\log n)$ does not suffice. The optimal constant $c^\ast$ such that multiplicity at most $c^\ast n$ always guarantees a full Latin transversal is therefore known only to lie between $27/256$ and $1$. The problem is to improve the sufficient constant beyond $27/256$, to construct counterexample arrays with multiplicity at most $cn$ for an explicit absolute constant $c<1$ independent of $n$, or to determine the threshold exactly.

Background

An $n\times n$ array is a grid of $n$ rows and $n$ columns whose cells are filled with arbitrary symbols; a Latin square is the special case in which each symbol appears exactly once in every row and every column. A transversal of such an array is a choice of $n$ cells with exactly one cell in each row and each column, and it is a Latin transversal when the $n$ symbols in the chosen cells are pairwise distinct. Writing $k$ for the maximum number of occurrences of any single symbol in the array, the central question is how large $k$ can be while every $n\times n$ array still admits a full Latin transversal.

This generalizes the classical Ryser–Brualdi–Stein transversal conjectures for Latin squares — the conjecture that every Latin square of odd order $n$ has a full transversal and every Latin square of even order has one of size $n-1$. Stein (1975) conjectured more generally that every equi-$n$-square — an $n\times n$ array in which each symbol occurs exactly $n$ times — has a partial transversal of size $n-1$; this was refuted by Pokrovskiy and Sudakov (2019), whose counterexamples even lack partial transversals larger than $n-(1/42)\ln n$. The problem belongs to probabilistic combinatorics because the entry point is the Lovász Local Lemma (LLL): if bad events $A_1,\dots,A_m$ in a probability space each have probability at most $p$ and are indexed by a dependency graph of maximum degree $d$ (edges joining dependent events), then all the events can be avoided simultaneously provided $ep(d+1)\le 1$. Erdős and Spencer (1991) introduced the lopsided variant (LLLL): it suffices to have a lopsidependency graph in which conditioning on the avoidance of non-adjacent events cannot increase an event's probability, that is $\Pr[A_i \mid \bigwedge_{j\in S}\overline{A_j}] \le \Pr[A_i]$ whenever $A_i$ is non-adjacent to every $A_j$ with $j\in S$; their paper states the criterion in the form $4dp\le 1$. Applying this to a uniformly random permutation $\sigma$ of the columns (so the chosen cells are $(i,\sigma(i))$), with bad events $A_{iji'j'}$ asserting that two chosen cells carry the same symbol, one has $p=1/(n(n-1))$ and lopsidependency degree at most $4nk$, so $4dp\le 1$ yields exactly $k\le (n-1)/16$.

Three later developments define the modern landscape. First, running the same lopsidependency-graph argument with the sharper symmetric constant gives $k\le (n-1)/(4e)$. The cluster-expansion improvement of the LLL (Bissacot, Fernández, Procacci and Scoppola, 2011) improves this to $k\le (27/256)(n-1)+1$: cluster expansion is a refinement of the Local Lemma, based on Shearer's lemma (the optimal form of the Local Lemma for a fixed dependency graph) and on polymer-model techniques from statistical physics, which gains power when the dependent bad events form cliques, as the collision events sharing a row or a column do here. Harris and Srinivasan turned this into the first polynomial-time algorithm that actually finds such a transversal. Second, Lu and Székely (2007) showed that the space of random injections (a uniformly random permutation is the special case of injections of an $n$-set into an $n$-set) supports an easy-to-verify sufficient condition for negative dependency graphs — their name for graphs satisfying the lopsidependency condition above, with the criterion that the bad events be canonical events with an $S$-intersection property — which made the lopsidependency verifications used throughout this literature routine and started an explicit search for further such graphs (Lu, Mohr and Székely). Third, on the negative side, the addition tables $a_{ij}=(i+j)\bmod n$ of even order $n$ are Latin squares with no transversal at all (multiplicity $n$), and the Pokrovskiy–Sudakov counterexamples to Stein's conjecture, padded by $O(\log n)$ rows and columns, give arrays of symbol multiplicity at most $n-(1/85)\ln n$ with no full Latin transversal; so the threshold is at most $n-\Omega(\log n)$.

Adjacent results delimit the near-full regime without settling it: Montgomery (2023) proved that every sufficiently large Latin square has a transversal of size $n-1$, establishing Brualdi's conjecture — that every Latin square has a partial transversal of size at least $n-1$ — for all large orders (see Montgomery's 2024 survey for an overview of this area); Anastos and Morris (2024) gave a deterministic polynomial-time algorithm finding a transversal of size $(1-\beta/4-o(1))n$ in arrays where no symbol appears more than $\beta n$ times; Chakraborti, Christoph, Hunter, Montgomery and Petrov (2024) found almost-full transversals in equi-$n$-squares; and Alon, Spencer and Tetali (1995) showed that for orders $n$ that are powers of $2$, arrays in which no symbol appears more than $\varepsilon n$ times can even be partitioned into $n$ disjoint Latin transversals for a suitable fixed $\varepsilon>0$. These show that much larger multiplicity can suffice for structured orders or near-full transversals, but the full-transversal multiplicity constant for general $n$ remains governed by the Local Lemma bounds above.

Problem Statement

Determine, or improve the known bounds on, the multiplicity threshold for full Latin transversals: the largest constant $c^\ast$ such that every $n\times n$ array of symbols in which no symbol occurs in more than $c^\ast n$ cells admits a Latin transversal (a set of $n$ cells, one per row and one per column, with pairwise distinct symbols). The current bounds are $27/256\le c^\ast\le 1$; more precisely, $k\le (27/256)(n-1)+1$ suffices (Bissacot et al.; the original Erdős–Spencer bound was $(n-1)/16$), while multiplicity $n-(1/85)\ln n$ does not suffice (Pokrovskiy–Sudakov). The problem is to improve the sufficient constant beyond $27/256$ — by proving that some explicit constant $c>27/256$ suffices, for all $n$ or for all $n\ge n_0$ with explicit $n_0$ and the small-$n$ cases explicitly handled or excluded — to give an explicit construction, for infinitely many unbounded orders $n$, of arrays with maximum symbol multiplicity at most $cn$ for an explicit absolute constant $c<1$ independent of $n$ and with no full Latin transversal, or to determine the exact threshold.

References

1. Paul Erdős and Joel Spencer. Lopsided Lovász Local Lemma and Latin transversals. Discrete Applied Mathematics 30(2-3), 151-154, 1991. DOI: 10.1016/0166-218X(91)90040-4. https://doi.org/10.1016/0166-218X(91)90040-4
2. 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), 709-719, 2011. DOI: 10.1017/S0963548311000253. https://doi.org/10.1017/S0963548311000253. Preprint: arXiv:0910.1824. https://arxiv.org/abs/0910.1824
3. Linyuan Lu and László Székely. Using Lovász Local Lemma in the space of random injections. Electronic Journal of Combinatorics 14(1), #R63, 2007. DOI: 10.37236/981. https://doi.org/10.37236/981
4. Linyuan Lu, Austin Mohr and László Székely. Quest for Negative Dependency Graphs. In: Recent Advances in Harmonic Analysis and Applications (Springer Proceedings in Mathematics & Statistics), 243-258, 2012. DOI: 10.1007/978-1-4614-4565-4_21. https://doi.org/10.1007/978-1-4614-4565-4_21
5. Ian Wanless. Transversals in Latin squares: a survey. In: Surveys in Combinatorics 2011 (London Mathematical Society Lecture Note Series 392), 403-437, 2011. DOI: 10.1017/CBO9781139004114.010. https://doi.org/10.1017/CBO9781139004114.010. Preprint (under the title Transversals in Latin Squares): arXiv:0903.5142. https://arxiv.org/abs/0903.5142
6. Guillem Perarnau and Oriol Serra. Rainbow Matchings: existence and counting. Electronic Notes in Discrete Mathematics 38, 711-716, 2011. DOI: 10.1016/j.endm.2011.10.019. https://doi.org/10.1016/j.endm.2011.10.019. Preprint: arXiv:1104.2702. https://arxiv.org/abs/1104.2702
7. Alexey Pokrovskiy and Benny Sudakov. A counterexample to Stein's Equi-$n$-square Conjecture. Proceedings of the American Mathematical Society 147(6), 2281-2287, 2019. DOI: 10.1090/proc/14220. https://doi.org/10.1090/proc/14220. Preprint: arXiv:1711.00429. https://arxiv.org/abs/1711.00429
8. David G. Harris and Aravind Srinivasan. A Constructive Lovász Local Lemma for Permutations. Theory of Computing 13, Article 17, pp. 1-41, 2017. DOI: 10.4086/toc.2017.v013a017. https://doi.org/10.4086/toc.2017.v013a017. Preprint (under the title A constructive algorithm for the LLL on permutations): arXiv:1612.02663, 2016. https://arxiv.org/abs/1612.02663
9. Dimitris Achlioptas and Fotis Iliopoulos. Random Walks That Find Perfect Objects and the Lovász Local Lemma. Journal of the ACM 63(3), 1-29, 2016. DOI: 10.1145/2818352. https://doi.org/10.1145/2818352
10. Michael Anastos and Patrick Morris. A Note on Finding Large Transversals Efficiently. Journal of Combinatorial Designs 33(9), 338-342, 2025. DOI: 10.1002/jcd.21990. https://doi.org/10.1002/jcd.21990. Preprint: arXiv:2412.05891. https://arxiv.org/abs/2412.05891
11. Debsoumya Chakraborti, Micha Christoph, Zach Hunter, Richard Montgomery and Teo Petrov. Almost-full transversals in equi-$n$-squares. arXiv:2412.07733, 2024. https://arxiv.org/abs/2412.07733
12. Igal Sason. The Lovász Local Lemma: Foundations and Applications. arXiv:2603.07245, 2026. https://arxiv.org/abs/2603.07245
13. Sherman Stein. Transversals of Latin squares and their generalizations. Pacific Journal of Mathematics 59(2), 567-575, 1975. DOI: 10.2140/pjm.1975.59.567. https://doi.org/10.2140/pjm.1975.59.567
14. Noga Alon, Joel Spencer and Prasad Tetali. Covering with latin transversals. Discrete Applied Mathematics 57(1), 1-10, 1995. DOI: 10.1016/0166-218X(93)E0136-M. https://doi.org/10.1016/0166-218X(93)E0136-M
15. Richard Montgomery. A proof of the Ryser-Brualdi-Stein conjecture for large even $n$. arXiv:2310.19779, 2023. https://arxiv.org/abs/2310.19779
16. Richard Montgomery. Transversals in Latin Squares (survey). arXiv:2406.19873, 2024. https://arxiv.org/abs/2406.19873
17. Nicholas J. A. Harvey and Jan Vondrák. Short proofs for generalizations of the Lovász Local Lemma: Shearer's condition and cluster expansion. arXiv:1711.06797, 2017. https://arxiv.org/abs/1711.06797