A Note on Finding Large Transversals Efficiently

ABSTRACT In an array filled with symbols, a transversal is a collection of entries with distinct rows, columns and symbols. In this note we show that if no symbol appears more than times, the array contains a transversal of size . In particular, if the array is filled with symbols, each appearing times (an equi‐ square), we get transversals of size . Moreover, our proof gives a deterministic algorithm with polynomial running time, that finds these transversals.