Gould and Kelly proved that almost all Latin squares have a Hamilton transversal, confirming the Ryser–Brualdi–Stein, Andersen, and Gyárfás–Sárközy conjectures for almost all Latin squares and for almost all proper nn-arc-colourings of the complete bidirected graph Kn↔\overleftrightarrow{K_n}, and posed the deterministic, universal versions as open problems — chief among them their Conjecture 1.4: every proper arc-colouring of Kn↔\overleftrightarrow{K_n}, with any number of colours, admits a rainbow directed cycle or path of length at least n−1n-1 (for nn-arc-colourings, equivalently, every Latin square has a connected partial transversal of size n−1n-1). Later literature has resolved the three constituent conjectures asymptotically: Montgomery (2023) proved the n−1n-1 partial-transversal bound for all sufficiently large orders, and Bowtell–Montgomery–Müyesser–Pokrovskiy (2026) proved Andersen's and Gyárfás–Sárközy's conjectures for large nn, including a rainbow directed path on n−1n-1 vertices in every optimally arc-coloured Kn↔\overleftrightarrow{K_n} (an arc-colouring in which each colour appears exactly nn times, i.e. a proper nn-arc-colouring, the setting corresponding to Latin squares). What remains open is: Conjecture 1.4 itself — still one arc beyond the best results even for optimal colourings, and open for colourings far from typical — the exact statements of the constituent conjectures for every nn (currently proved only above unspecified, astronomically large thresholds), and the worst-case quantitative question of Benzing–Pokrovskiy–Sudakov: by how much the n−O(n4/5)n-O(n^{4/5}) bound for a longest rainbow directed cycle in an arbitrary proper arc-colouring can be improved.

Background

A Latin square of order nn is an n×nn\times n array filled with nn symbols so that each symbol appears exactly once in every row and every column. A partial transversal is a set of cells no two of which share a row, a column, or a symbol; a full transversal is a partial transversal with nn cells. The most famous problem on this topic, the Ryser–Brualdi–Stein conjecture, predicts that every n×nn\times n Latin square has a partial transversal of size n−1n-1; this would be best possible, since for even nn the addition table of the integers modulo nn is a Latin square with no full transversal. Approximate forms with error n−O(n)n-O(\sqrt n) date to 1978; the error was reduced to n−O(log⁡2n)n-O(\log^2 n) by Shor (1982; a gap in that proof was repaired by Hatami and Shor in 2008) and to n−O(log⁡n/log⁡log⁡n)n-O(\log n/\log\log n) by Keevash, Pokrovskiy, Sudakov and Yepremyan (2022); in 2023 Montgomery proved the conjectured n−1n-1 bound for all sufficiently large nn.

Several neighbouring conjectures live in the language of edge-coloured graphs. An edge-colouring is proper if no two edges of the same colour share a vertex, and a subgraph is rainbow if no two of its edges share a colour. Andersen (1989) conjectured that every proper edge-colouring of the complete graph KnK_n admits a rainbow path of length n−2n-2, that is, a rainbow path on n−1n-1 vertices; this is best possible, since Maamoun and Meyniel (1984) constructed, for infinitely many nn, proper edge-colourings of KnK_n with no rainbow Hamilton path. Alon, Pokrovskiy and Sudakov (2017) proved that a rainbow path of length n−O(n3/4)n-O(n^{3/4}) always exists, improved to n−O(n1/2log⁡n)n-O(n^{1/2}\log n) by Balogh and Molla (2019).

Latin squares are in bijection with proper nn-arc-colourings of the complete bidirected graph Kn↔\overleftrightarrow{K_n}, the digraph obtained from KnK_n by replacing each edge with two oppositely directed arcs and adding a loop at every vertex: colour the arc with tail ii and head jj with the symbol in cell (i,j)(i,j). A proper arc-colouring is one in which no two arcs with a common tail, or with a common head, share a colour. Under this bijection, a partial transversal corresponds to a rainbow subgraph in which every vertex has in-degree and out-degree at most one; a partial transversal is cycle-free exactly when the corresponding subgraph is a linear directed forest, that is, a disjoint union of directed paths; and a set of cells is connected when the corresponding subgraph of Kn↔\overleftrightarrow{K_n} is weakly connected, that is, connected when arc directions are ignored. Gyárfás and Sárközy (2014) conjectured that every n×nn\times n Latin square has a cycle-free partial transversal of size n−2n-2; before 2026 the best general bound towards it was the polynomial error n−O(n2/3)n-O(n^{2/3}) of Benzing, Pokrovskiy and Sudakov, who also proved that every proper arc-colouring of Kn↔\overleftrightarrow{K_n} contains a rainbow directed cycle of length n−O(n4/5)n-O(n^{4/5}) and asked by how much this bound can be improved.

Gould and Kelly (2022) proved the typical-case counterparts of all of these conjectures: almost all n×nn\times n Latin squares have not just a transversal but a Hamilton transversal — a full transversal that is connected, equivalent to a rainbow directed Hamilton cycle in the associated arc-colouring — in numbers asymptotically matching the known general upper bound on the number of transversals of a Latin square. Their paper explicitly leaves open the deterministic, universal versions of these statements, and poses as its central new conjecture (their Conjecture 1.4) that every proper arc-colouring of Kn↔\overleftrightarrow{K_n}, with any number of colours, admits a rainbow directed cycle or path of length at least n−1n-1, where length is the number of arcs. In the nn-arc-colouring case this is equivalent to the statement that every n×nn\times n Latin square has a connected partial transversal of size n−1n-1, and, as the authors note, the conjecture implies the Ryser–Brualdi–Stein, Andersen, and Gyárfás–Sárközy conjectures.

The universal statements have since moved dramatically. Montgomery (2023) proved the Ryser–Brualdi–Stein n−1n-1 bound for all sufficiently large nn (with no explicit threshold given; the bound implied by the proof is astronomically large), and Bowtell, Montgomery, Müyesser and Pokrovskiy (2026) proved that every properly edge-coloured KnK_n contains a rainbow path on n−1n-1 vertices (a rainbow Hamilton path when at least nn colours are used) and a rainbow cycle missing at most 101 vertices, resolving Andersen's conjecture for large nn; the same paper proves that every optimally arc-coloured Kn↔\overleftrightarrow{K_n} — an arc-colouring in which each colour appears exactly nn times, equivalently a proper nn-arc-colouring, i.e. one coming from a Latin square — contains a rainbow directed path on n−1n-1 vertices, resolving the Gyárfás–Sárközy conjecture for large nn in a connected form, and that an (n,ε)(n,\varepsilon)-typical properly coloured digraph (one with (1±ε)n(1\pm\varepsilon)n vertices in which each vertex has (1±ε)n(1\pm\varepsilon)n in- and out-neighbours and each colour appears (1±ε)n(1\pm\varepsilon)n times — conditions forcing near-optimal colour counts) with m≥nm\ge n colours contains a rainbow directed Hamilton path. What still separates these results from Gould and Kelly's Conjecture 1.4, together with the worst-case quantitative question for directed rainbow cycles, is the subject of this problem.

Problem Statement

Determine the correct worst-case (universal) guarantees for long rainbow directed paths and cycles in proper arc-colourings of the complete bidirected graph Kn↔\overleftrightarrow{K_n}, and the equivalent connected-transversal statements for Latin squares. The common objective is to replace the 'almost all' theorems of Gould and Kelly by guarantees holding for every colouring; concretely, prove or disprove the following.

(1) Gould–Kelly Conjecture 1.4: every proper arc-colouring of Kn↔\overleftrightarrow{K_n} — with any number of colours — admits a rainbow directed cycle or a rainbow directed path of length at least n−1n-1, where length is the number of arcs. In the special case of proper nn-arc-colourings this is equivalent to: every n×nn\times n Latin square has a connected partial transversal of size n−1n-1. As the source paper notes, a positive answer implies the conjectures in (2).

(2) The all-nn versions of the three constituent conjectures subsumed by (1), each currently proved only for nn above some sufficiently large threshold, with no explicit bound given in the proofs: every n×nn\times n Latin square has a partial transversal of size n−1n-1 (Ryser–Brualdi–Stein); every proper edge-colouring of KnK_n admits a rainbow path of length n−2n-2 (Andersen); every n×nn\times n Latin square has a cycle-free partial transversal of size n−2n-2 (Gyárfás–Sárközy). (The further assertion of Ryser that every odd-order Latin square has a full transversal is a related but distinct conjecture, not implied by (1), and also remains open.)

(3) The quantitative version for cycles alone, asked by Benzing, Pokrovskiy and Sudakov: determine the optimal worst-case bound for the length of a longest rainbow directed cycle in an arbitrary proper arc-colouring of Kn↔\overleftrightarrow{K_n} — that is, the optimal error f(n)f(n) in a worst-case bound of the form n−f(n)n-f(n) — no construction is currently known to force even a superconstant error, and f(n)=Ω(n4/5)f(n)=\Omega(n^{4/5}) would show that the existing error term is essentially best possible. This refines the cycle-only part of (1) and remains meaningful whatever the outcome of (1), since (1) permits paths as well as cycles.

Each of (1), (2) and (3) stands on its own — resolving any one of them in full is a complete resolution — and since (1) implies (2), settling (1) settles (2) as well.

References

  1. Stephen Gould, Tom Kelly, 'Hamilton transversals in random Latin squares', Random Structures & Algorithms 62 (2022) 450–478, DOI: 10.1002/rsa.21102, https://doi.org/10.1002/rsa.21102; arXiv:2104.12718, https://arxiv.org/abs/2104.12718
  2. Richard Montgomery, 'A proof of the Ryser-Brualdi-Stein conjecture for large even nn', arXiv:2310.19779 (2023), https://arxiv.org/abs/2310.19779
  3. Candida Bowtell, Richard Montgomery, Alp Müyesser, Alexey Pokrovskiy, 'A proof of Andersen's rainbow path conjecture for large nn', arXiv:2608.06369 (2026), https://arxiv.org/abs/2608.06369
  4. Richard Montgomery, 'Transversals in Latin Squares', Surveys in Combinatorics 2024, Cambridge University Press (2024) 131–158, DOI: 10.1017/9781009490559.006, https://doi.org/10.1017/9781009490559.006; arXiv:2406.19873, https://arxiv.org/abs/2406.19873
  5. Frederik Benzing, Alexey Pokrovskiy, Benny Sudakov, 'Long directed rainbow cycles and rainbow spanning trees', European Journal of Combinatorics 88 (2020) 103102, DOI: 10.1016/j.ejc.2020.103102, https://doi.org/10.1016/j.ejc.2020.103102; arXiv:1711.03772, https://arxiv.org/abs/1711.03772
  6. Peter Keevash, Alexey Pokrovskiy, Benny Sudakov, Liana Yepremyan, 'New bounds for Ryser's conjecture and related problems', Transactions of the American Mathematical Society, Series B 9 (2022) 288–321, DOI: 10.1090/btran/92, https://doi.org/10.1090/btran/92; arXiv:2005.00526, https://arxiv.org/abs/2005.00526
  7. P. W. Shor, 'A lower bound for the length of a partial transversal in a latin square', Journal of Combinatorial Theory, Series A 33 (1982) 1–8, DOI: 10.1016/0097-3165(82)90074-7, https://doi.org/10.1016/0097-3165(82)90074-7
  8. Pooya Hatami, Peter W. Shor, 'A lower bound for the length of a partial transversal in a Latin square', Journal of Combinatorial Theory, Series A 115 (2008) 1103–1113, DOI: 10.1016/j.jcta.2008.01.002, https://doi.org/10.1016/j.jcta.2008.01.002
  9. L. D. Andersen, 'Hamilton circuits with many colours in properly edge-coloured complete graphs', Mathematica Scandinavica 64 (1989) 5–14, DOI: 10.7146/math.scand.a-12245, https://doi.org/10.7146/math.scand.a-12245
  10. A. Gyárfás, G. N. Sárközy, 'Rainbow matchings and cycle-free partial transversals of Latin squares', Discrete Mathematics 327 (2014) 96–102, DOI: 10.1016/j.disc.2014.03.010, https://doi.org/10.1016/j.disc.2014.03.010
  11. J. Balogh, T. Molla, 'Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs', European Journal of Combinatorics 79 (2019) 140–151, DOI: 10.1016/j.ejc.2019.02.008, https://doi.org/10.1016/j.ejc.2019.02.008
  12. N. Alon, A. Pokrovskiy, B. Sudakov, 'Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles', Israel Journal of Mathematics 222 (2017) 317–331, DOI: 10.1007/s11856-017-1592-x, https://doi.org/10.1007/s11856-017-1592-x
  13. M. Maamoun, H. Meyniel, 'On a problem of G. Hahn about coloured Hamiltonian paths in K2tK_{2^t}', Discrete Mathematics 51 (1984) 213–214, DOI: 10.1016/0012-365X(84)90073-6, https://doi.org/10.1016/0012-365X(84)90073-6
  14. Debsoumya Chakraborti, Micha Christoph, Zach Hunter, Richard Montgomery, Teo Petrov, 'Almost-full transversals in equi-nn-squares', arXiv:2412.07733 (2024), https://arxiv.org/abs/2412.07733