Hamilton transversals in random Latin squares

DOI10.1002/RSA.21102zbMATH Open1522.05019arXiv2104.12718OpenAlexW3158379883MaRDI QIDQ6074871FDOQ6074871

Authors: Stephen Gould, Tom Kelly 

Publication date: 19 October 2023

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Gy'{a}rf'{a}s and S'{a}rk"{o}zy conjectured that every $nimesn$ Latin square has a `cycle-free' partial transversal of size $n-2$. We confirm this conjecture in a strong sense for almost all Latin squares, by showing that as $nightarrowinfty$, all but a vanishing proportion of $nimesn$ Latin squares have a Hamilton transversal, i.e. 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).

Full work available at URL: https://arxiv.org/abs/2104.12718

Recommendations

• Transversals in quasirandom latin squares
• On transversals in Latin squares
• Transversals in Latin squares: a survey
• Transversals in generalized Latin squares
• Intercalates and discrepancy in random Latin squares
• Large deviations in random latin squares
• Random Latin squares and 2-dimensional expanders
• On transversals of homogeneous Latin squares
• A generalization of transversals for Latin squares
• Hamiltonian double Latin squares

zbMATH Keywords

Latin squaresrainbow cycletransversalsarc-colouringdistributive absorptionHamilton transversals

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15)

Cites Work

• Title not available (Why is that?)
• Transversals of latin squares and their generalizations
• An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
• Spanning trees in random graphs
• Combinatorial matrix theory
• Title not available (Why is that?)
• A lower bound for the length of a partial transversal in a Latin square
• A lower bound for the length of a partial transversal in a Latin square
• Counting designs
• On the maximum number of Latin transversals
• Multidimensional permanents and an upper bound on the number of transversals in Latin squares
• Asymptotic behavior of the chromatic index for hypergraphs
• Rainbow matchings and cycle-free partial transversals of Latin squares
• Title not available (Why is that?)
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• On a hypergraph matching problem
• The cycle structure of two rows in a random Latin square
• Rainbow and orthogonal paths in factorizations of \(K_n\)
• Cycle switches in Latin squares
• The solution of van der Waerden's problem for permanents
• Intercalates and discrepancy in random Latin squares
• Most Latin squares have many subsquares
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Hamilton circuits with many colours in properly edge-coloured complete graphs.
• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
• Long rainbow cycles in proper edge-colorings of complete graphs
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• Almost all Steiner triple systems have perfect matchings
• Long directed rainbow cycles and rainbow spanning trees

Cited In (5)

• Title not available (Why is that?)
• The cycle structure of two rows in a random Latin square
• Transversals in quasirandom latin squares
• Quasirandom Latin squares
• New bounds for Ryser’s conjecture and related problems

This page was built for publication: Hamilton transversals in random Latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074871)