Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.07733 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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)}$.