Almost-full transversals in equi-$n$-squares
Preprint
Abstract
In 1975, Stein made a wide generalisation of the Ryser-Brualdi-Stein conjecture on transversals in Latin squares, conjecturing that every equi-$n$-square (an $n\times n$ array filled with $n$ symbols where each symbol appears exactly $n$ times) has a transversal of size $n-1$. That is, it should have a collection of $n-1$ entries that share no row, column, or symbol. In 2017, Aharoni, Berger, Kotlar, and Ziv showed that equi-$n$-squares always have a transversal with size at least $2n/3$. In 2019, Pokrovskiy and Sudakov disproved Stein's conjecture by constructing equi-$n$-squares without a transversal of size $n-\frac{\log n}{42}$, but asked whether Stein's conjecture is approximately true. I.e., does an equi-$n$-square always have a transversal with size $(1-o(1))n$? We answer this question in the positive. More specifically, we improve both known bounds, showing that there exist equi-$n$-squares with no transversal of size $n-Ω(\sqrt{n})$ and that every equi-$n$-square contains $n-n^{1-Ω(1)}$ disjoint transversals of size $n-n^{1-Ω(1)}$.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- A Note on Finding Large Transversals EfficientlyJournal of Combinatorial Designs, 2025
- Transversals in Latin Squares2024
- A counterexample to Stein’s Equi-𝑛-square ConjectureProceedings of the American Mathematical Society, 2019
- Near-optimal list coloringsRandom Structures & Algorithms, 2000
- On the Degree, Size, and Chromatic Index of a Uniform HypergraphJournal of Combinatorial Theory, Series A, 1997
- Combinatorial Matrix Theory1991
- Transversals of Latin squares and their generalizationsPacific Journal of Mathematics, 1975