Projects per year
Abstract
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 (Formula presented.) if and only if the maximum size of a partial transversal is either (Formula presented.) or (Formula presented.). (2) A minimal cover in a Latin square of order n has size at most (Formula presented.). (3) There are infinitely many orders n for which there exists a Latin square having a minimal cover of every size from n to (Formula presented.). (4) Every Latin square of order n has a minimal cover of a size which is asymptotically equal to (Formula presented.). (5) If (Formula presented.) and (Formula presented.) then there is a Latin square of order n with a maximal partial transversal of size (Formula presented.). (6) For any (Formula presented.), asymptotically almost all Latin squares have no maximal partial transversal of size less than (Formula presented.).
Original language  English 

Pages (fromto)  11091136 
Number of pages  28 
Journal  Designs Codes and Cryptography 
Volume  87 
Issue number  5 
DOIs  
Publication status  Published  2019 
Keywords
 Covers
 Latin square
 Transversal
Projects
 1 Finished

Matchings in Combinatorial Structures
Wanless, I., Bryant, D. & Horsley, D.
Australian Research Council (ARC), Monash University, University of Queensland , University of Melbourne
1/01/15 → 10/10/20
Project: Research