Transversals in Rectangles

Abstract

Let $L(m,n)$ be the largest integer such that, if each symbol in an $m\times n$ rectangle occurs at most $L(m,n)$ times, then the array must have a transversal. We improve the lower bound to $L(m,n)\ge \lfloor \frac{m(n–m+1)–1}{m–1}\rfloor$ for $m>1$. Then we show that sporadically $L(m,n)<\lfloor \frac{mn–1}{m–1}\rfloor$ in the range $m\le n\le m^2–3m+3$. Define $n_0(m)$ to be the smallest integer $z$ such that if $n\ge z$ then $L(m,n)=\lfloor \frac{mn–1}{m–1}\rfloor$. We improve $n_0(m)$ from $O(m^3)$ to $O(m^{2.5})$. Finally, we determine $L(4,n)$ for all $n$.