A k-plex in a latin square of order n is a selection of kn entries that includes k representatives from each row and column and k occurrences of each symbol. A 1-plex is also known as a transversal. It is well known that if n is even then Bn, the addition table for the integers modulo n, possesses no transversals. We show that there are a great many latin squares that are similar to Bn and have no transversal. As a consequence, the number of species of transversal-free latin squares is shown to be at least n n 3/2(1/2−o(1)) for even n → ∞. We also produce various constructions for latin squares that have no transversal but do have a k-plex for some odd k > 1. We prove a 2002 conjecture of the second author that for all orders n > 4 there is a latin square of order n that contains a 3-plex but no transversal. We also show that for odd k and m > 2, there exists a latin square of order 2km with a k-plex but no k ′ -plex for odd k ′ < k.
['Nicholas J. Cavenagh', 'Ian M. Wanless']
Latin squares with no transversals