Covers and partial transversals of Latin squares

Darcy Best, Trent Marbach, Rebecca J. Stones, Ian M. Wanless

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)1109-1136
Number of pages28
JournalDesigns Codes and Cryptography
Volume87
Issue number5
DOIs
Publication statusPublished - 2019

Keywords

  • Covers
  • Latin square
  • Transversal

Cite this