Hamilton transversals in random Latin squares. Issue 2 (14th June 2022)

• Record Type: Journal Article
• Authors: Gould, Stephen; Kelly, Tom
• Is Part Of: Random structures & algorithms. Volume 62:Issue 2(2023)
• Page Start: 450
• Page End: 478
• Publication Date: 2022-06-14
• Subjects: arc‐colouring -- distributive absorption -- Hamilton transversals -- Latin squares -- rainbow cycle -- transversals; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21102
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Gyárfás and Sárközy conjectured that every n × n $$ n\times n $$ Latin square has a "cycle‐free" partial transversal of size n − 2 $$ n-2 $$ . We confirm this conjecture in a strong sense for almost all Latin squares, by showing that as n → ∞ $$ n\to \infty $$, all but a vanishing proportion of n × n $$ n\times n $$ 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).