Transversals in Rectangles

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) \geq \left\lfloor \frac{m(n – m + 1) – 1}{m – 1} \right\rfloor \) for \( m > 1 \). Then we show that sporadically \( L(m, n) < \left\lfloor \frac{mn – 1}{m – 1} \right\rfloor \) in the range \( m \leq n \leq m^2 – 3m + 3 \). Define \( n_0(m) \) to be the smallest integer \( z \) such that if \( n \geq z \) then \( L(m, n) = \left\lfloor \frac{mn – 1}{m – 1} \right\rfloor \). We improve \( n_0(m) \) from \( O(m^3) \) to \( O(m^{2.5}) \). Finally, we determine \( L(4, n) \) for all \( n \).