Latin squares with no transversals (Q2363108)

Summary: 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 \(B_n\), 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 \(B_n\) 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\rightarrow\infty\). 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 conjecture of the second author [Electron. J. Comb. 9, No. 1, Research paper R12, 15 p. (2002; Zbl 0993.05033)] that for all even 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\geq 2\), there exists a latin square of order \(2km\) with a \(k\)-plex but no \(k'\)-plex for odd \(k'<k\).