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 (from-to) | 1109-1136 |
| 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. (Primary Chief Investigator (PCI)), Bryant, D. (Chief Investigator (CI)) & Horsley, D. (Chief Investigator (CI))
ARC - Australian Research Council, Monash University, University of Queensland , University of Melbourne
1/01/15 → 10/10/20
Project: Research
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver