{"id":"cba9f0ad-cacb-4128-963e-05ced7f32317","arxiv_id":"2411.18743","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In any proper edge-colouring of a graph with n vertices and minimum degree at least (1/2+ε)n, if every colour appears on at most n/8 edges, there is a Hamilton cycle using n−o(n) distinct colours.","lead":"An almost-rainbow Hamilton cycle problem is solved for dense graphs: every proper edge-colouring in which no colour is used on more than n/8 edges still admits a Hamilton cycle with nearly n distinct colours. The paper also proves that the n/8 bound is the best possible.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.1 cannot satisfy the hypotheses of Lemmas 2.4 and 2.6 simultaneously: Lemma 2.4 needs γ ≥ n^{-α}, while Lemma 2.6 with q = n^{-2α} forces γ ≤ (1/4)n^{-√α}, and n^{-α} > n^{-√α}.","rationale":"Read in good faith: the main theorem is plausible, the lower-bound construction in Section 5 is internally consistent, and the absorber/reservoir machinery is standard. The load-bearing weakness is in Lemma 2.1, the core rainbow-forest step. The reader flagged the Lemma 2.4 parameter mismatch; I agree and sharpen it: as written, no γ can satisfy the union of the quoted hypotheses of Lemmas 2.4 and 2.6, because the former demands γ ≥ n^{-α} while the latter effectively demands γ ≤ O(n^{-√α}) when q = n^{-2α}. This makes the proof non-rigorous at the exact point where near-perfect rainbow matchings are produced. However, the mismatch appears repairable: choosing γ = n^{-2√α} and invoking a weaker concentration bound for random subsets would likely restore the argument, provided MPS19's lemma does not genuinely require γ ≥ n^{-α}. Since the flaw is localized and plausibly cosmetic, conditional acceptance remains the right verdict rather than rejection; the referee should require the authors to supply a consistent parameter choice or a direct proof of the random-partition concentration step.","tokens_in":11578,"tokens_out":27772,"duration_ms":244992,"concrete_test":"Re-derive the random-partition near-regularity bound (MPS19 Lemma 5.2, quoted here as Lemma 2.4) for p = n^{-α} and γ = n^{-2√α} instead of n^{-√α}. Check whether the proof only needs γ ≥ n^{-(1-α)/2}, the order of the sampling deviation, rather than γ ≥ n^{-α}. If the weaker bound suffices, changing γ to n^{-2√α} in Lemma 2.1 and keeping α in Lemma 2.6 repairs the proof; if not, the rainbow forest lemma has a genuine missing hypothesis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Lemma 2.1 the authors set γ = n^{-√α} and apply Lemma 2.4, whose hypothesis is n^{-α} ≤ γ. Since 0 < α < 1 implies √α > α, we have n^{-√α} < n^{-α}, so the stated hypothesis fails. This is not merely a notational clash. After Lemma 2.5 the relevant near-regularity parameter is 4γ, and Lemma 2.6 requires 4γ ≤ n^{-√α'}; its q-condition, with q = n^{-2α}, forces n^{-2α'} ≤ q, i.e. α' ≥ α. Combining with the Lemma 2.4 lower bound γ ≥ n^{-α} gives n^{-α} ≤ γ ≤ (1/4)n^{-√α'} ≤ (1/4)n^{-√α}, impossible for large n because n^{-α} > n^{-√α}. Thus no choice of γ and α' satisfies all quoted hypotheses; the rainbow matching step, and hence Theorem 1.1, rests on an unjustified application. The gap is likely repairable by choosing a smaller γ such as n^{-2√α} and verifying the random-partition concentration directly, but the paper does not do this.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1353,"tokens_out":1336,"duration_ms":43823,"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":[{"comment":"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":"Section 2, proof of Lemma 2.1"},{"comment":"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.","section":"Section 2, application of Lemma 2.6"}],"minor_comments":[{"comment":"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":"Abstract and Introduction"},{"comment":"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":"Section 4, proof of Theorem 4.1, final display"},{"comment":"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":"Section 2, proof of Lemma 2.1"},{"comment":"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.","section":"Section 5, Conjecture 5.5 discussion"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about the parameter regime in Lemma 2.1 is real and I confirmed it on reading the manuscript. This is a central gap, but the overall proof structure and the optimality construction are credible, and the gap looks repairable with a more careful choice of gamma and a direct verification of the random-partition concentration. I therefore recommend major revision rather than rejection. I would also ask the authors to double-check the constant in the final displayed count in Theorem 4.1 and to standardize notation for the regular subgraph."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhere 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.\n\nThe 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.\n\nOverall: 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.","headline":"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.","tokens_in":12375,"tokens_out":5151,"would_cite":true,"duration_ms":90316,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","05C15","05C70","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["rainbow Hamilton cycle","near-rainbow","proper edge-colouring","globally bounded colouring","Dirac graph","absorber method","rainbow path forest"],"falsifier":"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.","tokens_in":11381,"feed_emoji":"🌈","tokens_out":16331,"duration_ms":125226,"temperature":0.7,"pith_summary":"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.","feed_headline":"Colour classes of size n/8 still permit near-rainbow Hamilton cycles","feed_subtitle":"For graphs with degree above n/2, the 1/8 bound is sharp; the proof builds a rainbow forest, an absorber, and a reservoir.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Provides the random-partition near-regularity lemma and the near-perfect rainbow matching lemma that the rainbow forest construction is built on.","marker":"[MPS19]"},{"why":"Supplies the absorber and reservoir constructions that let the proof close the Hamilton cycle around the rainbow forest.","marker":"[RRS06]"},{"why":"Yields the regular spanning subgraph used as the starting point for the random partition in Lemma 2.1.","marker":"[CKO12]"},{"why":"Establishes the Dirac-graph rainbow Hamilton cycle problem with $o(n)$-bounded colourings and gives the construction motivating the sharpness result.","marker":"[CP20]"},{"why":"Introduces the near-rainbow Hamilton cycle question for properly coloured complete graphs and proves the first $n-\\sqrt{2n}$ bound.","marker":"[And89]"},{"why":"Improves the complete-graph bound to $n-O(\\log^2 n)$, the result the dense-graph theorem extends.","marker":"[BM19]"},{"why":"Provides the alternative rainbow forest lemma used to prove the $\\delta(G) \\ge 7n/8$ special case.","marker":"[APS17]"}],"fun_headline_variants":["n/8 colour bound is sharp for near-rainbow Hamilton cycles","Dense graphs get near-rainbow Hamilton cycles up to n/8 colour classes","Exact threshold: n/8 colour classes still allow n-o(n) distinct Hamilton colours","Optimal colour bound for near-rainbow Hamilton cycles in dense graphs","1/8 colour limit is tight for near-rainbow Hamilton cycles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["n/8 colour bound is sharp for near-rainbow Hamilton cycles","Dense graphs get near-rainbow Hamilton cycles up to n/8 colour classes","Exact threshold: n/8 colour classes still allow n-o(n) distinct Hamilton colours","Optimal colour bound for near-rainbow Hamilton cycles in dense graphs","1/8 colour limit is tight for near-rainbow Hamilton cycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000718,"raw_usage":{"total_tokens":3190,"prompt_tokens":877,"completion_tokens":2313,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":2210}},"tokens_in":493,"tokens_out":2313,"duration_ms":14131,"temperature":1.0,"reasoning_tokens":2210,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:57:16.540550+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}