Near rainbow Hamilton cycles in dense graphs

Danni Peng; Zhifei Yan

REVIEW 2 major objections 4 minor 10 references

Near rainbow Hamilton cycles in dense graphs

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper proves that every graph on $n$ vertices with minimum degree at least $(1/2+\varepsilon)n$ has a Hamilton cycle with $n-o(n)$ distinct colours whenever its edges are properly coloured with no colour class larger than $n/8$, and…

desk verdict New near-rainbow Hamilton result for Dirac graphs with sharp 1/8 threshold, but the rainbow forest proof has a parameter gap that needs fixing. read the letter →

arxiv 2411.18743 v1 pith:WG6XNR6L submitted 2024-11-27 math.CO

Danni Peng , Zhifei Yan This is my paper · ORCID

classification math.CO MSC 05C4505C1505C7005D40

keywords rainbowHamiltoncyclenear-rainbowproperedge-colouringgloballyboundedcolouringDiracgraphabsorbermethodpathforest

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

Every graph on $n$ vertices with minimum degree at least $(1/2+\varepsilon)n$, for any fixed $\varepsilon>0$, contains a Hamilton cycle using $n-o(n)$ distinct colours, provided its edges are properly coloured and no colour appears on more than $n/8$ edges. The paper proves this and shows the $n/8$ bound is optimal: for any $c>1/8$ there are such graphs whose every Hamilton cycle repeats a positive fraction of colours. This settles the optimal global boundedness threshold for near-rainbow Hamilton cycles in dense graphs, extending earlier results that required complete graphs or colour classes of size $o(n)$. A direct corollary is that every proper edge-colouring of such a graph, with no boundedness assumption at all, has a Hamilton cycle with $n/4-o(n)$ distinct colours.

What carries the argument

The load-bearing object is the rainbow path forest of Lemma 2.1: a collection of at most $n^{1-\alpha}$ vertex-disjoint paths, each of length at least $n^\alpha$, whose edges are all distinctly coloured and which together cover all but $2n^{1-\alpha}$ vertices. To build it, the proof finds an $r$-regular spanning subgraph with $r \approx \delta(G)/2$, partitions the vertices into $m \approx n^\alpha$ equal parts, randomly assigns colours to the parts, and uses two lemmas of [MPS19] to show each bipartite slice is near-regular and contains a near-perfect rainbow matching; these matchings are then glued into paths. Around this forest sit two further mechanisms: an absorber path (from [RRS06]), a short path that can be locally modified to swallow any leftover set of size $o(n^{1-\beta})$ while keeping its endpoints fixed; and a reservoir, a small random set in which every pair of vertices has many common neighbours, used to connect the paths and the absorber into a cycle.

What would settle it

Fix $\alpha = 1/4$ and read the proof of Lemma 2.1 alongside the quoted [MPS19] lemmas: the partition lemma requires $\gamma \ge n^{-1/4}$, while the proof sets $\gamma = n^{-1/2}$. A reader can settle the matter by checking whether the [MPS19] rainbow matching lemma (Lemma 2.6 here) is valid at this smaller $\gamma$, or whether the proof can be modified to use a larger $\gamma$ without losing the $n-o(n)$ vertex coverage; if neither holds, the theorem is not established by the argument given.

Watch

Extended reading notes

Core claim

The central claim is that global colour-class size $n/8$ is the exact boundary for near-rainbow Hamilton cycles in dense graphs. The proof builds a near-spanning rainbow path forest whose edges all have distinct colours, then wraps an absorber path and a reservoir around it so that the forest can be linked into a Hamilton cycle without losing the distinct-colour count; the connecting edges may repeat colours, but the forest alone already contributes $n-o(n)$ distinct colours. The sharpness direction constructs, for every $c>1/8$, a graph with minimum degree at least $(1/2+\varepsilon)n$ and a proper $cn$-bounded colouring in which every Hamilton cycle uses at most $(1-\varepsilon)n$ colours. This confirms that the $n/8$ constant in the main theorem is not an artefact of the method.

Load-bearing premise

The rainbow forest construction applies a lemma about random bipartite subgraphs that is stated under the condition $\gamma \ge n^{-\alpha}$, but the proof works with the smaller error parameter $\gamma = n^{-\sqrt{\alpha}}$; unless that lemma is strengthened or the proof adjusted, the near-perfect rainbow matching step, and with it the whole theorem, has no stated justification.

Editorial extensions

If this is right

If the theorem is correct, every proper $n/8$-bounded colouring of a graph with $\delta(G) \ge (1/2+\varepsilon)n$ forces a Hamilton cycle that repeats only $o(n)$ colours, so linearly many repetitions are never necessary under this boundedness.
The constant $1/8$ cannot be improved: for every $c>1/8$ there are graphs with $\delta(G) \ge (1/2+\varepsilon)n$ and proper $cn$-bounded colourings in which every Hamilton cycle repeats at least $\varepsilon n$ colours (Proposition 1.2).
With no boundedness condition at all, every proper edge-colouring of such a graph still yields a Hamilton cycle with at least $n/4-o(n)$ distinct colours (Corollary 1.3).
The same absorber-reservoir method gives a Hamilton cycle with $n/2$ distinct colours when $\delta(G) \ge 7n/8$, and the paper conjectures $n/2-o(n)$ colours for all graphs with minimum degree at least $n/2$.

Reading between the lines

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

A natural testable extension is to let the colour-class bound be $(1/8+o(1))n$; the absorption and reservoir steps tolerate $o(n)$ slack, so the near-rainbow conclusion should survive at the threshold rather than only below it.
The proof's shape suggests a general interpolation: for any proper $c$-bounded colouring of a graph with minimum degree at least $n/2$ and $c \in [1/8, 1/2]$, a Hamilton cycle with at least $n - O(cn)$ distinct colours should exist, connecting the main theorem at $c=1/8$ to Corollary 1.3 at $c=1/2$.
Because the sharpness construction is built from random matchings, it would be worth investigating whether the $1/8$ threshold is tied to the chromatic index of the host graph; if so, degree assumptions above $n/2$ might trade colour-class size against the number of distinct colours.

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.

Desk Editor's Note

read the letter

Two things to know. First, the main theorem is a genuine extension: for any graph with δ(G) ≥ (1/2+ε)n, every proper n/8-bounded colouring has a Hamilton cycle with n−o(n) colours, and the 1/8 constant is best possible. That is a natural and likely correct result, and the optimality construction in Section 5 is convincing. Second, the proof of the key rainbow forest lemma (Lemma 2.1) has a parameter mismatch that makes the written argument invalid. This needs to be fixed before the paper is accepted.

Where the paper is solid: the absorber and reservoir lemmas check out, the greedy forest-to-cycle step is fine, and the optimality construction via random matchings is well executed. The paper also engages honestly with the literature, and the conjectures at the end are reasonable. The main idea — adapting the MPS19 rainbow forest machinery to graphs without codegree control — is sound in broad strokes.

The gap: in the proof of Lemma 2.1, the authors set γ = n^{-√α} and then apply Lemma 2.4, whose hypothesis is n^{-α} ≤ γ. Since 0<α<1 gives n^{-√α} < n^{-α}, the application is outside the lemma's stated conditions. The same problem propagates: after Lemma 2.5 the near-regularity parameter is 4γ, and Lemma 2.6 requires the parameter to be at most n^{-√α}; but 4n^{-√α} is larger than n^{-√α}. So the near-perfect matching step, which is the core of the rainbow forest construction, rests on unjustified applications of the MPS19 results. The stress-test note confirms that no choice of γ satisfies both Lemma 2.4's lower bound and Lemma 2.6's upper bound as used. This looks repairable — one can probably prove a direct concentration bound instead of invoking Lemma 2.4 — but the repair is not in the paper.

Overall: the theorem is likely true and worth publishing, but the proof as it stands has a load-bearing gap. I would send it to referees, but the referee report should require the Section 2 parameters to be fixed. Anyone working on rainbow Hamilton cycles will want to cite this, once the proof is solid.

Referee Report

2 major / 4 minor

Summary. The paper studies near-rainbow Hamilton cycles in properly edge-coloured dense graphs. The main result, Theorem 1.1, asserts that every proper n/8-bounded edge-colouring of a graph G on n vertices with minimum degree at least (1/2+epsilon)n contains a Hamilton cycle using n-o(n) distinct colours. Proposition 1.2 shows the constant 1/8 is best possible up to an arbitrarily small improvement. The proof strategy is to construct a rainbow path forest by adapting the Montgomery--Pokrovskiy--Sudakov method, then to connect the forest into a Hamilton cycle using an absorber and a reservoir, following the Rodl--Rucinski--Szemeredi framework. The optimality construction uses random matchings and a carefully chosen colour count. The paper also derives Corollary 1.3 on proper colourings without a global boundedness assumption and discusses two conjectures.

Significance. If the proof is correct, the paper settles the optimal global boundedness threshold for near-rainbow Hamilton cycles in dense graphs, a natural problem introduced in the wake of Andersen's and Balogh--Molla's results for complete graphs and Coulson--Perarnau's work on Dirac graphs. The absorber-reservoir framework is standard but well executed, and the optimality construction in Section 5 is nontrivial and appears sound. The paper also gives a clean corollary for arbitrary proper colourings and identifies appealing open conjectures. However, the proof of the key rainbow-forest lemma has a parameter-regime gap that affects the central claim, so the result cannot currently be considered established.

major comments (2)

[Section 2, proof of Lemma 2.1] In the proof of Lemma 2.1, the authors set gamma = n^(-sqrt(alpha)) and then apply Lemma 2.4, whose stated hypothesis requires n^(-alpha) <= gamma. Since 0 < alpha < 1 implies sqrt(alpha) > alpha, we have n^(-sqrt(alpha)) < n^(-alpha), so the hypothesis of Lemma 2.4 is not satisfied. This is not a purely notational mismatch: the subsequent near-regularity parameters 2gamma and 4gamma all inherit this too-small value, and the concentration argument in Lemma 2.4 is not justified in this regime. This step is load-bearing because the entire rainbow-forest construction rests on it.
[Section 2, application of Lemma 2.6] After applying Lemma 2.5, the graph B_i is stated to be (4gamma, delta/m, 2n')-near-regular with gamma = n^(-sqrt(alpha)). The subsequent application of Lemma 2.6 with q = n^(-2alpha) creates an impossible parameter regime. Lemma 2.6 requires some alpha' with n^(-2sqrt(alpha')) <= 4gamma <= n^(-sqrt(alpha')) and also n^(-2alpha') <= q. The upper bound forces sqrt(alpha') < sqrt(alpha) for large n, while the lower bound q = n^(-2alpha) >= n^(-2alpha') forces alpha' >= alpha. These two requirements are incompatible for 0 < alpha < 1. Thus the existence of the near-perfect rainbow matching M_i is not established. The gap may be repairable by choosing a smaller gamma, such as gamma = n^(-2sqrt(alpha)), and reworking the random-partition concentration estimates, but the manuscript does not provide such an argument.

minor comments (4)

[Abstract and Introduction] The name 'Anderson' should be 'Andersen' in the phrase 'Anderson's problem' and in the related references; the text also contains OCR artifacts such as 'grap hs' and '/greaterorequalslant' that should be cleaned.
[Section 4, proof of Theorem 4.1, final display] The line 'e(F) >= n - bn^beta distinct colours' appears to be a typo: the theorem statement guarantees n - b n^(1-beta), and the counting from the rainbow forest gives n - O(n^(1-2beta)), which is stronger than n - b n^beta but inconsistent with the displayed formula as written.
[Section 2, proof of Lemma 2.1] The proof alternates between G[V_{i-1},V_i] and G'[V_{i-1},V_i] when describing the random bipartite graphs; since the regular subgraph G' is the object being partitioned, the notation should be made uniform.
[Section 5, Conjecture 5.5 discussion] The sentence 'it is even possible that ... contains a Hamilton cycle with delta(G) distinct colours' should read 'with at least delta(G) distinct colours' to match the intended meaning.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the near-rainbow Hamilton cycle theorem is derived from external lemmas (CKO12, MPS19, RRS06) without any fitted input or self-referential definition.

full rationale

The paper's derivation chain is self-contained relative to stated external results. Lemma 2.1 is proved by reducing to an r-regular spanning subgraph (Lemma 2.2, from CKO12), random partitions, and near-regularity/matching lemmas (Lemmas 2.4-2.6) quoted from Montgomery, Pokrovskiy and Sudakov [MPS19]; Lemma 2.7 then assembles those matchings greedily into a rainbow path forest. No parameter is fitted to the final Hamilton cycle and then reported as a prediction; Theorem 4.1 combines the rainbow forest with an absorber (Lemma 3.1) and reservoir (Lemma 3.3) that are themselves proved from the minimum-degree hypothesis. The lower-bound construction (Theorem 5.1 and Proposition 1.2) is an independent explicit construction. The cited sources are external and not by the present authors, so no load-bearing self-citation chain exists. The parameter-regime concern about Lemma 2.4 versus Lemma 2.6 raised by the skeptic is a potential correctness gap in the application of an external lemma, not a circularity, because it does not make the conclusion identical to an input by construction.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No data fitting or fabricated entities. The proof uses universal constants such as ε, α, β and c, and external cited theorems. The only caveat is that the application of MPS19 Lemmas 2.4 through 2.6 uses parameter ranges that are not fully matched in the text, which is a proof-writing issue rather than a fitted-parameter issue.

assumptions (4)

domain assumption Christofides-Kühn-Osthus Theorem 12: every graph with δ(G) > n/2 has an r-regular spanning subgraph with r ≈ δ(G)/2 and even.
Used to pass from G to a regular spanning G′ in Lemma 2.1; cited from [CKO12] and not proved in the paper.
domain assumption MPS19 Lemmas 5.2, 5.3 and 8.8: random bipartite subgraphs of near-regular properly coloured graphs are near-regular and contain near-perfect rainbow matchings.
Core probabilistic engine of Lemma 2.1; the paper quotes them without proof and the parameter conventions are not fully reconciled with Definition 2.3.
standard math Chernoff and Hoeffding concentration inequalities.
Used in Lemmas 3.2, 3.3 and 5.2 to control random matchings, random sets and random graphs.
standard math Common-neighbour bound |N(u) ∩ N(v)| ≥ 2εn whenever δ(G) ≥ (1/2+ε)n.
Used in the absorber and reservoir lemmas; follows from inclusion-exclusion.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Near rainbow Hamilton cycles in dense graphs." pith.science (2026). https://pith.science/paper/WG6XNR6L

@misc{pith2026241118743,
  author       = {Pith},
  title        = {Pith review of: Near rainbow Hamilton cycles in dense graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WG6XNR6L}},
  note         = {Machine review of arXiv:2411.18743}
}

abstract

Finding near-rainbow Hamilton cycles in properly edge-coloured graphs was first studied by Andersen, who proved in 1989 that every proper edge colouring of the complete graph on $n$ vertices contains a Hamilton cycle with at least $n-\sqrt{2n}$ distinct colours. This result was improved to $n-O(\log^2 n)$ by Balogh and Molla in 2019. In this paper, we consider Anderson's problem for general graphs with a given minimum degree. We prove every globally $n/8$-bounded (i.e. every colour is assigned to at most $n/8$ edges) properly edge-coloured graph $G$ with $\delta(G) \geq (1/2+\varepsilon)n$ contains a Hamilton cycle with $n-o(n)$ distinct colours. Moreover, we show that the constant $1/8$ is best possible.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages

[1]

Andersen

L. Andersen. Hamilton circuits with many colours in properly edge-coloured complete graphs. Math. Scand. , 64(1):5--14, 1989

work page 1989
[2]

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

work page 2017
[3]

Balogh and T

J. Balogh and T. Molla. Long rainbow cycles and H amiltonian cycles using many colors in properly edge-colored complete graphs. European J. Combin. , 79:140--151, 2019

work page 2019
[4]

Christofides, D

D. Christofides, D. K\" u hn, and D. Osthus. Edge-disjoint H amilton cycles in graphs. J. Combin. Theory Ser. B , 102(5):1035--1060, 2012

work page 2012
[5]

Coulson and G

M. Coulson and G. Perarnau. A rainbow D irac's theorem. SIAM J. Discrete Math. , 34(3):1670--1692, 2020

work page 2020
[6]

G. Hahn. Un jeu de colouration. Actes du Colloque de Cerisy. , 12:18--18, 1980

work page 1980
[7]

Hoeffding

W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. , 58:13--30, 1963

work page 1963
[8]

Maamoun and H

M. Maamoun and H. Meyniel. On a problem of G . H ahn about coloured H amiltonian paths in K 2n . Discrete Math. , 51(2):213--214, 1984

work page 1984

Show all 10 references

[9]

Montgomery, A

R. Montgomery, A. Pokrovskiy, and B. Sudakov. Decompositions into spanning rainbow structures. Proc. Lond. Math. Soc. , 119(4):899--959, 2019

2019
[10]

R\" o dl, A

V. R\" o dl, A. Ruci\' n ski, and E. Szemer\' e di. A D irac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput. , 15(1-2):229--251, 2006

2006

Pith tools

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

[1] [1]

Andersen

L. Andersen. Hamilton circuits with many colours in properly edge-coloured complete graphs. Math. Scand. , 64(1):5--14, 1989

work page 1989

[2] [2]

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

work page 2017

[3] [3]

Balogh and T

J. Balogh and T. Molla. Long rainbow cycles and H amiltonian cycles using many colors in properly edge-colored complete graphs. European J. Combin. , 79:140--151, 2019

work page 2019

[4] [4]

Christofides, D

D. Christofides, D. K\" u hn, and D. Osthus. Edge-disjoint H amilton cycles in graphs. J. Combin. Theory Ser. B , 102(5):1035--1060, 2012

work page 2012

[5] [5]

Coulson and G

M. Coulson and G. Perarnau. A rainbow D irac's theorem. SIAM J. Discrete Math. , 34(3):1670--1692, 2020

work page 2020

[6] [6]

G. Hahn. Un jeu de colouration. Actes du Colloque de Cerisy. , 12:18--18, 1980

work page 1980

[7] [7]

Hoeffding

W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. , 58:13--30, 1963

work page 1963

[8] [8]

Maamoun and H

M. Maamoun and H. Meyniel. On a problem of G . H ahn about coloured H amiltonian paths in K 2n . Discrete Math. , 51(2):213--214, 1984

work page 1984