Pith. sign in

REVIEW 2 major objections 5 minor 68 references

A proof of Andersen's rainbow path conjecture for large $n$

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that, once n is sufficiently large, every properly edge-coloured complete graph on n vertices contains a rainbow path on n−1 vertices, and, when at least n colours are used, a rainbow Hamilton path.

desk verdict A serious, detailed proof of Andersen's conjecture for large n built on a genuinely new Hamilton router technique, with one load-bearing unverified strengthening of a co-author's theorem. read the letter →

arxiv 2608.06369 v1 pith:2GPX4A6H submitted 2026-08-06 math.CO

Candida Bowtell , Richard Montgomery , Alp Müyesser , Alexey Pokrovskiy This is my paper
classification math.CO MSC 05C1505C3805C7005B15
keywords rainbowpathsproperedge-colouringcompletegraphsHamiltonroutersortingnetworksLatinsquaretransversalsmatchingstypicaldigraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

For every sufficiently large n, the paper proves that a properly edge-coloured complete graph on n vertices always contains a rainbow path — one whose edges all have distinct colours — on n−1 of the vertices. This settles a 1989 conjecture and strengthens it in the case where at least n colours are used, where a rainbow Hamilton path exists, so every large odd-order proper colouring has a Hamilton path. The same methods prove a directed version for optimally coloured complete digraphs, which says that every large Latin square has a cycle-free transversal of size n−2. The new object that carries the proof is a Hamilton router, a sparse routing structure that converts large rainbow matchings into long rainbow cycles and is built from just O(n) auxiliary vertices.

What carries the argument

The load-bearing object is the Hamilton router. For disjoint sets A and B of equal size, an A,B-Hamilton router is a sparse subgraph such that, for every bijection $\phi:A\to B$, the vertex set can be partitioned into A-to-B paths whose union with the matching $\{(\phi(a),a)\}$ is a single Hamilton cycle. This is a deliberate relaxation of a sorting network: a sorting network must realize arbitrary permutations, while a router only needs one cycle type, so a router can be built with $O(n)$ comparisons instead of $\Omega(n\log n)$. The construction first produces order-2 routers (comparators) of depth 9 inside typical properly coloured digraphs, using a theorem that finds long even cycles avoiding forbidden pairs and a short rainbow connecting lemma, then glues $qn$ of these comparators together. The router allows the host graph to be partitioned into O(1) random parts, so that a rainbow-matching black box can be applied in each part; the resulting rainbow path forest is then merged by the router into a single long rainbow cycle.

What would settle it

Exhibit, for infinitely many large n, a properly edge-coloured complete graph on n vertices with no rainbow path on n−1 vertices; even one such graph would refute the central claim. For the proof's dependency, check whether the companion paper's published text actually implies the strengthened pseudorandomness properties C1* and C7* invoked in Appendix A: if not, Theorem 2.1, and with it Theorems 1.2–1.4, would not be established.

Watch

Extended reading notes

Core claim

The central claim is that, in a proper edge-colouring of a complete graph, the rainbow picture is complete up to one vertex. For all n ≥ n0, every such colouring of Kn contains a rainbow path on n−1 vertices; if it uses at least n colours it contains a rainbow Hamilton path; and every such colouring contains a rainbow cycle on at least n−C vertices for an absolute constant C. The proof also establishes the Latin-square version: every optimally coloured complete digraph on n vertices contains a rainbow directed path on n−1 vertices, equivalently a cycle-free transversal of order n−2 in the associated Latin square. These conclusions replace the earlier approximate bounds of order n−O($n^{{1/2}}$\log n) with the optimal n−1 and resolve two longstanding conjectures for all large n.

Load-bearing premise

The proof depends on a randomized rainbow-matching theorem imported from a companion paper, and the exact form needed here is not stated in that paper; it is justified by a strengthening that the companion's published version is said to include. If that strengthening is not already implicit, the main theorems lack their foundation.

Editorial extensions

If this is right

  • Every large properly coloured complete graph has a rainbow path missing at most one vertex, which is the best possible obstruction because even n can need n−1 colours.
  • Every large odd-order proper colouring has a rainbow Hamilton path, since any such colouring uses at least n colours; this is stronger than the usual Hamilton path statement.
  • Every large properly coloured complete graph has a rainbow cycle of length n−C, and a Hamilton cycle with at least n−2 distinct colours.
  • Every large Latin square contains a cycle-free transversal of order n−2, confirming the Latin-square conjecture for large n.
  • For sufficiently large sets of points with no three collinear, the points can be ordered so that consecutive connecting lines have distinct directions, giving a new proof of the direction-tree conjecture.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The Hamilton router construction is a transferable template: any future strengthening of the underlying rainbow-matching theorem should lift, via the same router, to longer rainbow paths and cycles in complete digraphs.
  • The proof gives no explicit bound on n0, and the hierarchy of constants suggests the threshold is astronomically large; making it concrete would require a separate quantitative analysis.
  • One testable by-product: if the router can be built inside arbitrary properly coloured graphs without the typicality hypothesis used in the stability step, the conjectures would follow in full, not just for large n.
  • The directed Latin-square result hints that near-perfect rainbow matchings in pseudorandom bipartite graphs are equivalent, up to the Hamilton-router conversion, to near-perfect rainbow Hamilton paths in pseudorandom complete digraphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proves that for sufficiently large n, every properly edge-coloured complete graph on n vertices contains a rainbow path on n−1 vertices, and if the colouring uses at least n colours, a rainbow Hamilton path (Theorem 1.2). It also proves a directed analogue for optimally coloured complete digraphs (Theorem 1.4), confirming the Gyárfás–Sárközy conjecture for large n, and a near-spanning rainbow cycle result (Theorem 1.3). The proof introduces Hamilton routers—sparse structures that connect a collection of vertex-disjoint rainbow paths into a single cycle—and combines them with randomly partitioned vertex/colour sets, a nibble-type matching lemma, and a stability reduction. The main technical engine is Theorem 4.1, which proves the result for (n,ε)-typical digraphs, and Theorem 2.1, a randomized rainbow-matching tool imported from Montgomery's Ryser–Brualdi–Stein proof [42].

Significance. If the proof is completed, this resolves Andersen's 1989 conjecture for all large n and improves the best previous bounds (n−O(n^{1/2} log n)) to n−1; for large odd n it also settles Hahn's original Hamilton-path conjecture. The Hamilton router is a novel and promising tool, and the reduction from arbitrary proper colourings to typical digraphs via Lemma 5.3 is elegant. The paper is generally careful and detailed: the case split in Theorem 4.1, the router construction in Section 3, and the stability arguments in Section 5 are all presented with concrete estimates. However, the proof depends at a critical point on a strengthening of Montgomery's matching theorem that is not proved in the manuscript and is relegated to a personal communication; this prevents the paper from being fully self-contained and currently blocks verification of the central claim.

major comments (2)
  1. [§2.3 and Appendix A.2 (Theorem A.4)] The randomized rainbow-matching theorem (Theorem 2.1) is the foundation of Theorem 4.1, and its BPW case is derived from Theorem A.4, a strengthening of [42, Theorem 3.1] in which C1 is weakened to C1* and C7 is strengthened to C7*. The manuscript does not prove Theorem A.4; it says only that the proof of [42] 'will be updated in the published version of that proof' and cites a personal communication [44]. Because Theorem 4.1(1) and (2) invoke BPW, this unverified external strengthening is load-bearing for Theorems 1.2 and 1.4. Please include a complete proof of Theorem A.4 (or at least a fully detailed derivation of the W3-based adjustment) in the paper; a citation to an in-preparation update cannot substitute for a proof in a submitted manuscript.
  2. [Appendix A.4, properties D7* and PrP.1] The inheritance lemma (Lemma A.7) is the mechanism that produces strong-proper-pseudorandomness in the sampled graph D[X', C', Y']. The proof of property D7* is asserted to follow 'almost verbatim' from [42, Proposition 3.12], but the manuscript does not exhibit the adaptation to the boundary case |Y'| = |X'|−1, which is exactly where C1* becomes relevant. Since the strengthened absorption property W3 is the only reason [42, Theorem 3.1] can be pushed to n−1 colours, this is not a purely presentational point. The authors should either prove D7* directly or give a precise statement of the modification to [42, Claim 8] and Section 9.4.
minor comments (5)
  1. [Section 3.1, Definition 3.1] The phrase 'with endpoints in A×B' is ambiguous; it should say 'with one endpoint in A and the other in B'.
  2. [Section 3.1, Lemma 3.5] The figure showing the comparator is not captioned in the text; please add a caption and refer to it explicitly when describing the paths Q_{1,3}, Q_{2,4}, Q_{1,4}, and Q_{2,3}.
  3. [Section 2.1, Notation] In the definition of 'p-random', the set A is said to be a subset of V with each element included independently with probability p; this is standard, but the notation 'A⊂V' should be 'A⊆V' for clarity when p=0 or 1.
  4. [Appendix A.2] The reference [44] is given as 'Personal communication, 2026'; this is not a stable citation for a load-bearing theorem. Please replace it with a published or arXiv source, or include the proof in the paper.
  5. [Section 4, proof of Theorem 4.1, case (1)] After deleting f and f', the path is stated to have n−1 vertices; because both dummy edges are incident to v2, the vertex v2 is isolated and the remaining vertices form a path. Please state this explicitly, since the Hamilton cycle has n vertices and the deletion step might otherwise appear to leave n vertices.

Circularity Check

1 steps flagged · score 4.0 of 10

The BPW rainbow-matching black box used for the n-1 colour case rests on an unpublished, same-author strengthening of Montgomery's theorem, not proved in the manuscript.

  1. self citation load bearing [Appendix A.2, Theorem A.4; used in Theorem 2.1, BPW case (Section 2.3); applied in Theorem 4.1(1)-(2)]
    "We also observe from the proof of [42, Theorem 3.1] (and as will be updated in the published version of that proof [44]) that it is sufficient for the graph G to have only at least n−1 colours, as opposed to at least n colours as claimed there, under our strengthened proper-pseudorandomness. That is, we can weaken C1 to C1* if we strengthen C7 to C7* in compensation."

    The BPW conclusion of Theorem 2.1 — a rainbow matching of size |X'|-1 when |X'|=|Y'|+1≤|C'| — is the exact input needed for the n−1 colour case of Theorem 4.1, and hence for Theorems 1.2 and 1.4. The proof of this case depends on Theorem A.4, which asserts a strengthened version of Montgomery's [42, Theorem 3.1] under the new properties C1* and C7*. The only justification supplied for this strengthening is the statement that it follows from the proof of [42] 'with very minor adjustments' and that the proof 'will be updated in the published version of that proof', citing [44] — a personal communication by the same author (Montgomery). No formal proof of the C1*/C7* modification is given.

full rationale

The paper's central contribution — constructing Hamilton routers and converting rainbow matchings into rainbow paths/cycles — is genuinely new and internally developed: Proposition 3.7, Lemma 3.8 and Theorem 4.1 are proved from definitions, Theorem 2.7 is proved in Appendix B from a Molloy–Reed nibble statement, and the stability reduction in Section 5 uses the external published Theorem 5.1. The only circularity concern is the import of Theorem 2.1 from Montgomery [42]. For RBS and SPC the manuscript supplies a substantial pseudorandomness-inheritance proof in Appendix A. However, for the BPW case, Theorem A.4 is not proved; it is asserted to follow from the proof of [42, Theorem 3.1] 'with very minor adjustments', with the published version of that proof promised in a personal communication [44] by a coauthor. Since Theorem 4.1(1)–(2) invokes BPW through Theorem 2.1, this is a load-bearing self-citation: the only cited support for the key n−1-colour matching statement is the authors' own unpublished strengthening. This is not a reduction of the final rainbow-path theorem to its own input, because the router argument and nibble argument are independent, so I score it 4 rather than 6 or higher. The proof is not circular in the definitional or fitted-prediction sense; it has a fragile, self-referential foundational link that would need to be closed by a complete proof of Theorem A.4.

Assumptions & free parameters 2 free parameters · 5 assumptions · 1 invented entities

The central claim rests on no data-fitted constants; the hierarchy constants (ε, η, ε̃, q, w, p, t, M, ℓ) are existential choices in the standard ≪ convention (Section 2.1). The paper imports three external results: the randomized matching black box from Montgomery [42] (a co-author's preprint, with asserted modifications, partly documented via [44]), the published Montgomery-Pokrovskiy-Sudakov theorem [45], and Janzer's theorem [32]. The Hamilton router is a proven construction, not a postulated entity with independent-evidence burden.

free parameters (2)
  • typicality and hierarchy constants (ε, η, ε̃, p, q, w) = existential, e.g. 1/n ≪ ε^{poly} ≪ log^{-1} n
    Standard hierarchy convention (Section 2.1): chosen right-to-left to satisfy polynomial inequalities. Not fitted to any data; the main theorems are uniform in n for all sufficiently large n, so these constants do not appear in the conclusions.
  • rounding and auxiliary parameters in Theorem 4.1 (t, M, ℓ, s) = derived from q and n̄, e.g. M ≈ 50q n̄
    Defined by divisibility rounding (M closest to 50q n̄ with (n̄−M)/t integral). Deterministic choices, not fitted to data.
assumptions (5)
  • domain assumption Theorem 2.1 (randomized RBS/BPW/SPC rainbow matchings in typical digraphs) holds as stated, including the asserted modifications to [42]
    Imported from Montgomery [42], a co-author's arXiv preprint. Section 2.3 states it 'follows from its proofs with minor modification'; Appendix A gives the pseudorandomness inheritance, but the strengthening to n−1 colours (C1*, C7*) is partly documented only via the published version of [42] and personal communication [44].
  • domain assumption Montgomery-Pokrovskiy-Sudakov theorem (Theorem 5.1): rainbow Hamilton cycle when at most (1−ε)n colours have more than (1−ε)n/2 edges
    Published result [45] used to cover the non-near-optimal colourings in the stability dichotomy for Theorem 1.2.
  • standard math Janzer's theorem on rainbow Turán numbers (Theorem 3.4)
    Published [32]; used to build comparators (order-2 Hamilton routers) in Lemma 3.5.
  • standard math Molloy-Reed pseudo-random matching decomposition (Lemma B.1)
    Published [40]; used in the nibble lemma (Theorem 2.7).
  • standard math Chernoff, McDiarmid, Azuma concentration bounds
    Used throughout the probabilistic arguments; standard.
invented entities (1)
  • Hamilton router (including order-2 comparators) independent evidence
    purpose: Sparse network that can merge any pairing of endpoint sets into a Hamilton cycle; replaces sorting networks at O(n) cost; bridges rainbow matchings to rainbow paths and cycles.
    Defined in Definition 3.1; existence in arbitrary typical digraphs is proven (Lemmas 3.5 and 3.8); utility is demonstrated by its use in Theorem 4.1. This is a proven construction, not an unverified postulate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A proof of Andersen's rainbow path conjecture for large $n$." pith.science (2026). https://pith.science/paper/2GPX4A6H

@misc{pith2026260806369,
  author       = {Pith},
  title        = {Pith review of: A proof of Andersen's rainbow path conjecture for large $n$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2GPX4A6H}},
  note         = {Machine review of arXiv:2608.06369}
}
abstract

We show that, for sufficiently large $n$, every properly edge-coloured $n$-vertex complete graph contains a path with $n-1$ vertices which uses each colour at most once (that is, a rainbow path). This resolves a conjecture of Andersen from 1989 for all large $n$ and improves previous results of Alon-Pokrovskiy-Sudakov, and then Balogh-Molla, which showed that rainbow paths/cycles of length $n-O(n^{1/2}\log n)$ exist in this setting. Furthermore, with related methods, we show that, for every sufficiently large $n$, every Latin square of order $n$ contains a cycle-free transversal of order $n-2$, confirming a conjecture of Gy\'arf\'as and S\'ark\"ozy from 2014 for large $n$.

Figures

Figures reproduced from arXiv: 2608.06369 by the authors.

Figure 1
Figure 1. The Hamilton router of order 2 we find for Lemma 3.5. All edges are directed from left to [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. A basic Hamilton router of order 4 where (for simplicity) the comparators are depicted as 4-cycles [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Steps in the proof of Theorem 4.1. a) The vertex partition at (1) and the reallocation steps illustrated with t = 4. b) After almost perfect matchings are found between the sets V ′ i and V ′ i+1, i ∈ [t−1], the leftover in each V ′ i is transferred to Vi . c) The final steps of the proof, in case (1). If f and f ′ are present, then there is a perfect matching between Vi ∪ V ′ i and Vi+1 ∪ V ′ i+1 for each i ∈ [t − … view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Relevant structures for C3, C4 and C5 respectively in the definition of proper-pseudorandomness (see Definition A.1). In the picture for C3, we have e = u1u2 and f = v1v2. The edges u4u3 and v4v3 are depicted to have the same colour, but C3 does not require this. In th…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

68 extracted references · 65 canonical work pages

  1. [42]

    Montgomery

    R. Montgomery. A proof of the Ryser-Brualdi-Stein conjecture for large evenn.arXiv preprint arXiv:2310.19779, 2023

    arXiv 2023

  2. [44]

    Montgomery

    R. Montgomery. Personal communication, 2026

    work page 2026

  3. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. AnO(nlogn) sorting network. InProceedings of the fifteenth annual ACM Symposium on Theory of Computing, pages 1–9, 1983

    work page 1983

  4. [2]

    Akbari, O

    S. Akbari, O. Etesami, H. Mahini, and M. Mahmoody. On rainbow cycles in edge colored complete graphs.Australasian Journal of Combinatorics, 37:33, 2007

    work page 2007

  5. [3]

    N. Alon, M. Buci´ c, L. Sauermann, D. Zakharov, and O. Zamir. Essentially tight bounds for rainbow cycles in proper edge-colourings.Proceedings of the London Mathematical Society, 130(4):e70044, 2025

    work page 2025

  6. [4]

    N. Alon, A. Pokrovskiy, and B. Sudakov. Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles.Israel Journal of Mathematics, 222(1):317–331, 2017

    work page 2017

  7. [5]

    Alon and J

    N. Alon and J. H. Spencer.The Probabilistic Method. John Wiley & Sons, 2004

    work page 2004

  8. [6]

    Alrabiah and V

    O. Alrabiah and V. Guruswami. Near-tight bounds for 3-query locally correctable binary linear codes via rainbow cycles. In65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1874–1882. IEEE, 2024. 17

    work page 2024

Show all 68 references
  1. [7]

    L. D. Andersen. Hamilton circuits with many colours in properly edge-coloured complete graphs.Math- ematica Scandinavica, pages 5–14, 1989

    1989

  2. [8]

    Balogh and T

    J. Balogh and T. Molla. Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs.European Journal of Combinatorics, 79:140–151, 2019

    2019

  3. [9]

    Benzing, A

    F. Benzing, A. Pokrovskiy, and B. Sudakov. Long directed rainbow cycles and rainbow spanning trees. European Journal of Combinatorics, 88:103102, 2020

    2020

  4. [10]

    D. Best, K. Pula, and I. M. Wanless. Small Latin arrays have a near transversal.Journal of Combina- torial Designs, 29(8):511–527, 2021

    2021

  5. [11]

    A. E. Brouwer, A. de Vries, and R. Wieringa. A lower bound for the length of partial transversals in a Latin square.Nieuw Archief Voor Wiskunde, 26(2):330–332, 1978

    1978

  6. [12]

    R. A. Brualdi and H. J. Ryser.Combinatorial matrix theory. Cambridge University Press, 1991

    1991

  7. [13]

    Buci´ c, B

    M. Buci´ c, B. Frederickson, A. M¨ uyesser, A. Pokrovskiy, and L. Yepremyan. Towards Graham’s rear- rangement conjecture via rainbow paths.Advances in Mathematics, 492:110892, 2026

    2026

  8. [14]

    Chen and X

    H. Chen and X. Li. Long rainbow path in properly edge-colored complete graphs.arXiv preprint arXiv:1503.04516, 2015

    2015 arXiv

  9. [15]

    Dragani´ c, R

    N. Dragani´ c, R. Montgomery, D. M. Correia, A. Pokrovskiy, and B. Sudakov. Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

    2024 arXiv

  10. [16]

    Ferber, G

    A. Ferber, G. Kronenberg, and E. Long. Packing, counting and covering Hamilton cycles in random directed graphs.Israel Journal of Mathematics, 220(1):57–87, 2017

    2017

  11. [17]

    J. A. Gallian. A dynamic survey of graph labeling.Electronic Journal of Combinatorics, 6(25):4–623, 2022

    2022

  12. [18]

    Gebauer and F

    H. Gebauer and F. Mousset. On rainbow cycles and paths.arXiv preprint arXiv:1207.0840, 2012

    2012 arXiv

  13. [19]

    Gould and T

    S. Gould and T. Kelly. Hamilton transversals in random Latin squares.Random Structures & Algorithms, 62(2):450–478, 2023

    2023

  14. [20]

    R. L. Graham. On sums of integers taken from a fixed sequence. InProceedings of the Washington State University Conference on Number Theory, pages 22–40. Washington State University, Pullman, W A, 1971

    1971

  15. [21]

    Gy´ arf´ as, M

    A. Gy´ arf´ as, M. Ruszink´ o, G. S´ ark¨ ozy, and R. H. Schelp. Long rainbow cycles in proper edge-colorings of complete graphs.Australasian Journal of Combinatorics, 50:45–53, 2011

    2011

  16. [22]

    Gy´ arf´ as and G

    A. Gy´ arf´ as and G. N. S´ ark¨ ozy. Rainbow matchings and cycle-free partial transversals of Latin squares. Discrete Mathematics, 327:96–102, 2014

    2014

  17. [23]

    H¨ aggkvist and A

    R. H¨ aggkvist and A. Thomason. Oriented Hamilton cycles in digraphs.Journal of Graph Theory, 19(4):471–479, 1995

    1995

  18. [24]

    H¨ aggkvist and A

    R. H¨ aggkvist and A. Thomason. Oriented Hamilton cycles in oriented graphs. In B. Bollob´ as and A. Thomason, editors,Combinatorics, Geometry and Probability: A Tribute to Paul Erd˝ os, pages 339–

  19. [25]

    G. Hahn. Un jeu de coloration. InActes du Colloque de Cerisy, volume 12, pages 18–18, 1980

    1980

  20. [26]

    Hatami and P

    P. Hatami and P. W. Shor. A lower bound for the length of a partial transversal in a Latin square. Journal of Combinatorial Theory, Series A, 115(7):1103–1113, 2008

    2008

  21. [27]

    Hsieh, P

    J.-T. Hsieh, P. K. Kothari, S. Mohanty, D. M. Correia, and B. Sudakov. Small even covers, locally decodable codes and restricted subgraphs of edge-colored Kikuchi graphs.International Mathematics Research Notices, 2025(5):rnaf045, 2025. 18

    2025

  22. [28]

    J. Hyde, N. Morrison, A. M¨ uyesser, and M. Pavez-Sign´ e. Spanning trees in pseudorandom graphs via sorting networks.Proceedings of the American Mathematical Society, 153(06):2353–2367, 2025

    2025

  23. [29]

    R. E. Jamison. Few slopes without collinearity.Discrete Mathematics, 60:199–206, 1986

    1986

  24. [30]

    R. E. Jamison. Direction trees.Discrete & Computational Geometry, 2:249–254, 1987

    1987

  25. [31]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski.Random Graphs. John Wiley & Sons, 2011

    2011

  26. [32]

    O. Janzer. Rainbow Tur´ an number of even cycles, repeated patterns and blow-ups of cycles.Israel Journal of Mathematics, 253(2):813–840, 2023

    2023

  27. [33]

    D. Y. Kang, T. Kelly, D. K¨ uhn, A. Methuku, and D. Osthus. Graph and hypergraph colouring via nibble methods: A survey.Proceedings of the 8th European Congress of Mathematics, 2021

    2021

  28. [34]

    Keevash, A

    P. Keevash, A. Pokrovskiy, B. Sudakov, and L. Yepremyan. New bounds for Ryser’s conjecture and related problems.Transactions of the American Mathematical Society, Series B, 9(8):288–321, 2022

    2022

  29. [35]

    D. J. Kleitman and R. Pinchasi. A note on caterpillar-embeddings with no two parallel edges.Discrete & Computational Geometry, 33(2):223–229, 2005

    2005

  30. [36]

    D. E. Knuth.The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973

    1973

  31. [37]

    K¨ uhn, J

    D. K¨ uhn, J. Lapinskas, D. Osthus, and V. Patel. Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments.Proceedings of the London Mathematical Society, 109(3):733– 762, 2014

    2014

  32. [38]

    Letzter, A

    S. Letzter, A. Pokrovskiy, and E. Williams. On the gracesize of trees.arXiv preprint arXiv:2511.11331, 2025

    2025 arXiv

  33. [39]

    Maamoun and H

    M. Maamoun and H. Meyniel. On a problem of G. Hahn about coloured Hamiltonian paths inK 2t. Discrete Mathematics, 51(2):213–214, 1984

    1984

  34. [40]

    Molloy and B

    M. Molloy and B. Reed. Near-optimal list colorings.Random Structures & Algorithms, 17(3-4):376–402, 2000

    2000

  35. [41]

    Montgomery

    R. Montgomery. Hamiltonicity in random directed graphs is born resilient.Combinatorics, Probability and Computing, 29(6):900–942, 2020

    2020

  36. [43]

    Montgomery

    R. Montgomery. Transversals in Latin squares. InSurveys in Combinatorics 2024. Cambridge University Press, 2024

    2024

  37. [45]

    Montgomery, A

    R. Montgomery, A. Pokrovskiy, and B. Sudakov. Decompositions into spanning rainbow structures. Proceedings of the London Mathematical Society, 119(4):899–959, 2019

    2019

  38. [46]

    Montgomery, A

    R. Montgomery, A. Pokrovskiy, and B. Sudakov. A proof of Ringel’s conjecture.Geometric and Func- tional Analysis, 31(3):663–720, 2021

    2021

  39. [47]

    M¨ uyesser

    A. M¨ uyesser. Cycle type in Hall–Paige: a proof of the Friedlander–Gordon–Tannenbaum conjecture. InForum of Mathematics, Sigma, volume 14, page e50. Cambridge University Press, 2026

    2026

  40. [48]

    M¨ uyesser and A

    A. M¨ uyesser and A. Pokrovskiy. On the Graham–Sloane harmonious labelling conjecture.arXiv preprint arXiv:2509.05280, 2025

    2025

  41. [49]

    M¨ uyesser and A

    A. M¨ uyesser and A. Pokrovskiy. A random Hall-Paige conjecture.Inventiones mathematicae, 240:779–867, 2025. 19

    2025

  42. [50]

    Pokrovskiy

    A. Pokrovskiy. Rainbow subgraphs and their applications.London Mathematical Society Lecture Note Series. Cambridge University Press, pages 191–214, 2022

    2022

  43. [51]

    G. Ringel. Theory of graphs and its applications. InProceedings of the Symposium Smolenice, volume 2, 1963

    1963

  44. [52]

    V. R¨ odl. On a packing and covering problem.European Journal of Combinatorics, 6(1):69–78, 1985

    1985

  45. [53]

    A. Rosa. On certain valuations of the vertices of a graph. InTheory of Graphs (Internat. Symposium, Rome), pages 349–355, 1966

    1966

  46. [54]

    H. Ryser. Neuere Probleme der Kombinatorik.Vortr¨ age ¨ uber Kombinatorik, Oberwolfach, pages 69–91, 1967

    1967

  47. [55]

    P. W. Shor. A lower bound for the length of a partial transversal in a Latin square.Journal of Combinatorial Theory, Series A, 33(1):1–8, 1982

    1982

  48. [56]

    S. K. Stein. Transversals of Latin squares and their generalizations.Pacific J. Math., 59:567–575, 1975

    1975

  49. [57]

    B. Sudakov. Restricted subgraphs of edge-colored graphs and applications.arXiv preprint arXiv:2412.13945, 2024

    2024 arXiv

  50. [58]

    Woolbright

    D. Woolbright. Ann×nLatin square has a transversal with at leastn− √ndistinct symbols.Journal of Combinatorial Theory, Series A, 24(2):235–237, 1978. A Proof of Theorem 2.1 Here we give a proof of Theorem 2.1. To start, we recall the notion ofproper-pseudorandomnessfrom [42]. ...

    1978

  51. [60]

    We also provide a slightly altered definition ofC7compared to [42,F7] in that ourC7here assumes a slightly weaker property

    (recalled in Section A.2) can be seen to follow with only the most minor adjustments for any constants 0< α≪p, as long asnis sufficiently large. We also provide a slightly altered definition ofC7compared to [42,F7] in that ourC7here assumes a slightly weaker property. As will ...

  52. [61]

    •x 1y′′, x2y′′ ∈Dwithc D(x1y′′) =c ′ 1 andc D(x2y′′) =c ′ 2

    such thaty ′, y′′, y1, y2 ∈Y ′,x ′ 1, x′ 2 ∈X ′ andc ′ 1, c′ 2 ∈C ′ such that all elements are distinct, and distinct from x1, x2, c1, c2, y, with the exception thaty 1 =y 2 is not forbidden, and the following all hold: •x ′ 1y′, x′ 2y′ ∈Dwithc D(x′ 1y′) =c 1 andc D(x′ 2y′) =c...

  53. [62]

    There are at least (1−3ε)n−20 vertices y′′ /∈ {x1, x2, x′ 1, x′ 2, y, y′}such thatx 1y′′ andx 2y′′ are edges inDwith distinct coloursc ′ 1, c′ 2 /∈ {c1, c2,¯c1,¯c2}

    and ¯c2 :=c(x ′ 2x′ 1). There are at least (1−3ε)n−20 vertices y′′ /∈ {x1, x2, x′ 1, x′ 2, y, y′}such thatx 1y′′ andx 2y′′ are edges inDwith distinct coloursc ′ 1, c′ 2 /∈ {c1, c2,¯c1,¯c2}. Given such a pair of colours (c ′ 1, c′

  54. [63]

    note that there is no choice ofy ′′ yielding the pair of colours (c ′ 1, d), or (d, c′

  55. [64]

    Now, say such a pair (c ′ 1, c′

    for any other colourd. Now, say such a pair (c ′ 1, c′

  56. [65]

    isbadif for somez∈ {x 1, x2, y}we have that c(x′ 1z) =c ′ 1 orc(x ′ 2z) =c ′ 2, orx ′ 1 has no out-edge in colourc ′ 1, orx ′ 2 has no out-edge in colourc ′

  57. [66]

    These correspond to at most 8εn+ 6 bad choices ofy ′′, leaving at least (1−11ε)n−26 good choices

    Since |C(D)| ≤(1 + 3ε)nasDis (n, ε)-typical, every vertex has an in-edge in all but at most 4εncolours inD, and so there are at most 8εn+ 6 bad colour pairs. These correspond to at most 8εn+ 6 bad choices ofy ′′, leaving at least (1−11ε)n−26 good choices. That is, inD, there a...

  58. [67]

    withc(x ′ 1y0) =c 1 andc(x ′ 1y1) =c ′

  59. [68]

    This all follows sinceDis properly edge-coloured.) Thus, any of these pairs for which there is ac 2-colour in-edge incident toy 0 avoiding ¯X∪ ¯Yyields the desired structure. (Note that such an in-edge cannot have its other endpoint asx 1 sincec(x 1y0) =c 1 ̸=c 2, andc 2 was c...

    2000

  60. [354]

    Cambridge University Press, Cambridge, 1997

    1997

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.