Projects per year
Abstract
Gyárfás and Sárközy conjectured that every Latin square has a “cyclefree” 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 cyclefree. 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 language  English 

Journal  Random Structures and Algorithms 
Early online date  14 Jun 2022 
DOIs  
Publication status  Epub ahead of print  14 Jun 2022 
Keywords
 arccolouring
 distributive absorption
 Hamilton transversals
 Latin squares
 rainbow cycle
 transversals
Fingerprint
Dive into the research topics of 'Hamilton transversals in random Latin squares'. Together they form a unique fingerprint.Projects
 1 Finished

Combinatorics, Probability and Algorithms: Fellowship, Establish Career: Professor D Kuhn
Engineering & Physical Science Research Council
1/09/16 → 31/08/21
Project: Research Councils