Covers and partial transversals of Latin squares

We define a cover of a Latin square to be a set of entries that includes at least one representative of each row, column and symbol. A cover is minimal if it does not contain any smaller cover. A partial transversal is a set of entries that includes at most one representative of each row, column and symbol. A partial transversal is maximal if it is not contained in any larger partial transversal. We explore the relationship between covers and partial transversals. We prove the following: (1) The minimum size of a cover in a Latin square of order n is $$n+a$$ if and only if the maximum size of a partial transversal is either $$n-2a$$ or $$n-2a+1$$ . (2) A minimal cover in a Latin square of order n has size at most $$\mu _n=3(n+1/2-\sqrt{n+1/4})$$ . (3) There are infinitely many orders n for which there exists a Latin square having a minimal cover of every size from n to $$\mu _n$$ . (4) Every Latin square of order n has a minimal cover of a size which is asymptotically equal to $$\mu _n$$ . (5) If $$1\leqslant k\leqslant n/2$$ and $$n\geqslant 5$$ then there is a Latin square of order n with a maximal partial transversal of size $$n-k$$ . (6) For any $$\varepsilon >0$$ , asymptotically almost all Latin squares have no maximal partial transversal of size less than $$n-n^{2/3+\varepsilon }$$ .

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.