An equi-$n$-square is an $n$ by $n$ array of cells filled with the symbols $1,2,\dots,n$ so that each symbol occurs exactly $n$ times. (Every Latin square of order $n$ is an equi-$n$-square, but the converse does not hold.) For $k \le n$, a partial transversal of size $k$ in an equi-$n$-square is a collection of $k$ cells in which the cells all have different rows, columns, and symbols. Stein conjectured that for each $n$, every equi-$n$-square has a partial transversal of size $n-1$. It is also known that an equi-$n$-square always has a partial transversal of size $2n/3$.
For each positive integer $n$, let $s_n$ denote the largest integer such that every equi-$n$-square has a partial transversal of size $s_n$. Pokrovskiy and Sudakov showed that Stein's conjecture is false, by constructing for large $n$ a family of counterexamples. From this construction we therefore know that $s_n \le n - (\ln n)/42$ for all sufficiently large $n$.
My question is quite concrete:
Is anything known about the smallest $n$ such that $s_n \le n-2$?
References:
- S. K. Stein, Transversals of Latin squares and their generalizations, Pacific J. Math. 59(2) 567–575, 1975.
- Alexey Pokrovskiy and Benny Sudakov, A counterexample to Stein's equi-$n$-square conjecture, Proc. AMS 147(6) 2281–2287, 2019. https://doi.org/10.1090/proc/14220
