Hamilton transversals in random Latin squares

Stephen Gould, Tom Kelly

Research output: Contribution to journalArticlepeer-review

Abstract

Gyárfás and Sárközy conjectured that every Latin square has a “cycle-free” partial transversal of size . We confirm this conjecture in a strong sense for almost all Latin squares, by showing that as , all but a vanishing proportion of Latin squares have a Hamilton transversal, that is, a full transversal for which any proper subset is cycle-free. In fact, we prove a counting result that in almost all Latin squares, the number of Hamilton transversals is essentially that of Taranenko's upper bound on the number of full transversals. This result strengthens a result of Kwan (which in turn implies that almost all Latin squares also satisfy the famous Ryser–Brualdi–Stein conjecture).
Original languageEnglish
JournalRandom Structures and Algorithms
Early online date14 Jun 2022
DOIs
Publication statusE-pub ahead of print - 14 Jun 2022

Keywords

  • arc-colouring
  • distributive absorption
  • Hamilton transver-sals
  • Latin squares
  • rainbow cycle
  • transversals

Fingerprint

Dive into the research topics of 'Hamilton transversals in random Latin squares'. Together they form a unique fingerprint.

Cite this