Hamilton transversals in random Latin squares
From MaRDI portal
Publication:6074871
Abstract: Gy'{a}rf'{a}s and S'{a}rk"{o}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, 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).
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
Cites work
- scientific article; zbMATH DE number 4170917 (Why is no real title available?)
- scientific article; zbMATH DE number 3458807 (Why is no real title available?)
- scientific article; zbMATH DE number 3613053 (Why is no real title available?)
- 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
- Almost all Steiner triple systems have perfect matchings
- An \(n\times n\) Latin square has a transversal with at least \(n-\sqrt n\) distinct symbols
- Asymptotic behavior of the chromatic index for hypergraphs
- Combinatorial matrix theory
- Counting designs
- Cycle switches in Latin squares
- Hamilton circuits with many colours in properly edge-coloured complete graphs.
- Intercalates and discrepancy in random Latin squares
- Long directed rainbow cycles and rainbow spanning trees
- Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
- Long rainbow cycles in proper edge-colorings of complete graphs
- Most Latin squares have many subsquares
- Multidimensional permanents and an upper bound on the number of transversals in Latin squares
- On a hypergraph matching problem
- On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
- On the maximum number of Latin transversals
- Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
- Rainbow and orthogonal paths in factorizations of \(K_n\)
- Rainbow matchings and cycle-free partial transversals of Latin squares
- Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
- Spanning trees in random graphs
- The cycle structure of two rows in a random Latin square
- The solution of van der Waerden's problem for permanents
- Transversals of latin squares and their generalizations
Cited in
(5)
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)
