{"id":"10c277bb-563e-4837-bc12-1653c5c09cc5","arxiv_id":"2506.04189","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Randomly perturbing a graph with O(n) random edges forces a colour-biased Hamilton cycle, and at the critical minimum degree the bias is proportional to m.","lead":"For any graph with minimum degree at least αn, adding a linear number of random edges guarantees a Hamilton cycle that is biased toward one colour no matter how the edges are coloured. The paper also locates the critical density where the bias scales with the number of added random edges.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.20's key overlap inequality (15) is not derived: the degree-contradiction step fails, leaving Theorem 1.6's Ω(m) lower bound unsupported.","rationale":"The reader's weakest_assumption is exactly the load-bearing point I find. The arithmetic check confirms that the displayed union bound in Lemma 4.20 is not implied by the preceding bounds, and the paper does not supply an alternative reason for the claimed overlap. This matters because the matching obtained in W=V(G_α) minus U is what allows the proof to apply Pósa's theorem and then count non-c* edges in the final Hamilton cycle; without it, the d−q≥2^{−10}m term in (21) disappears and the Ω(m) bias lower bound in Theorem 1.6 does not follow. I also note the independent arithmetic difficulty in Theorem 3.1's final inequality, where the length of the nearly monochromatic path P_1 is at most about 2n/(r+1), which for r=2,3 cannot support a claimed bias of n/(2r) in the displayed inequality; however, the Lemma 4.20 gap is the more fundamental obstruction to the main critical theorem. The results may be salvageable with a corrected argument, but as written the proof of the central claim is incomplete, so the reader's REJECT verdict should stand.","tokens_in":1024,"tokens_out":1363,"duration_ms":129953,"concrete_test":"Recompute the union bound in Lemma 4.20 at the display after (13): set |I(U)|=|I(U_i)|=βn−2^{−4}β²m and |I(U)∩I(U_i)|=βn−7·2^{−6}β²m, which satisfy (13) and the negation of (15), and verify the union has size βn−7·2^{−6}β²m, so the claimed contradiction with δ(G_α)≥αn fails for α=1−β. Then check whether maximality of U_0 plus the sizes of the independent sets can force a larger intersection; if not, Lemma 4.20 needs a new proof before Theorem 4.1 is established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Lemma 4.20, the argument that every U∈U intersects some U_i in at least βn−2^{−6}β²m vertices is the step that lets a random matching of size 2^{−4}β²m inside U_i survive inside U. To prove this, the paper needs |I(U)∪I(U_i)| ≥ βn+2^{−6}β²m, since then any x in the intersection has d(x) ≤ n−|I(U)∪I(U_i)| ≤ (1−β)n−2^{−6}β²m < αn. But from (13) we only have |I(U)|,|I(U_i)| ≥ βn−2^{−4}β²m, and failure of (15) gives |I(U)∩I(U_i)| < βn−2^{−6}β²m. These bounds give |I(U)∪I(U_i)| ≥ 2(βn−2^{−4}β²m)−(βn−2^{−6}β²m) = βn−7·2^{−6}β²m, which is smaller than βn, not larger. Consequently d(x) can be as large as (1−β)n+7·2^{−6}β²m, compatible with δ(G_α)≥αn when α=1−β, as in Theorem 4.1. Maximality of U_0 only guarantees a nonempty intersection, not the quantitative lower bound (15). Since Lemma 4.20 supplies the Ω(m) matching in W=V(G_α) minus U used in (16)–(21) to force the biased Hamilton cycle, this gap is load-bearing for the critical-case lower bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies colour-biased Hamilton cycles in randomly perturbed graphs, i.e. graphs of the form G_α ∪ G(n,m), where G_α has minimum degree at least α n. The main results claimed are: (1) for every α>0, adding O(n) random edges typically forces an Ω(n)-colour-biased Hamilton cycle in every r-edge-colouring; (2) below the threshold α < (r+1)/(2r), o(n) random edges do not suffice; (3) at the critical value α=(r+1)/(2r), adding m random edges typically forces an Ω(m)-colour-biased Hamilton cycle for every 1≪m≤n, and there are examples with O(m) bias. The proofs combine an absorption/sprinkling argument for the O(n)-edge regime and a structural decomposition of graphs without large colour bias for the critical regime, together with Pósa's theorem, Erdős-Gallai, and standard random graph estimates.","tokens_in":24339,"tokens_out":19099,"duration_ms":170658,"significance":"If the theorems are correct, the paper would settle the randomly perturbed threshold for colour-biased Hamilton cycles and give a sharp dependence on m at the critical endpoint, extending results of Freschi–Hyde–Lada–Treglown and Gishboliner–Krivelevich–Michaeli. The paper is written in a standard and readable style, and it contains explicit extremal constructions for the upper bounds. It also makes good use of existing tools without introducing fitted parameters. However, the correctness of the main lower-bound results currently rests on several proof gaps that need to be fixed before the claims can be accepted.","major_comments":[{"comment":"The proof of the overlap claim (15) is not valid. From (13) one has |I(U)|,|I(U_i)| ≥ βn − 2^{−4}β²m, and the negation of (15) gives |I(U)∩I(U_i)| < βn − 2^{−6}β²m. These imply |I(U)∪I(U_i)| ≥ 2(βn − 2^{−4}β²m) − (βn − 2^{−6}β²m) = βn − 7·2^{−6}β²m, which is smaller than βn, not larger. Therefore the displayed bound d_{G_α}(x) ≤ (1−β)n − 2^{−6}β²m does not follow, and the contradiction with δ(G_α) ≥ αn is not obtained. Since this step is used to guarantee that the random matching inside some U_i survives inside every U, and that matching is essential for the Ω(m) lower bound in Theorem 4.1 (and hence Theorem 1.6), this is a load-bearing gap. The argument may be repairable by choosing different constants and using the fact that an independent set in G_α has size at most βn, but a corrected proof must be supplied.","section":"§4.3, Lemma 4.20"},{"comment":"The final numerical claim in the proof is false. After equation (5), the paper asserts that the path P'_1 contains at least (2/(r+1) − 5ε)n − 2ε³n ≥ n/r + n/(2r) edges of one colour. But for every r ≥ 2 one has 2/(r+1) < (r+1)/(2r), so the coefficient 2/(r+1) is strictly smaller than the coefficient 3/(2r) = 1/r + 1/(2r) needed for the claimed n/(2r) colour bias. Thus the path P_1 obtained from the Gishboliner–Krivelevich–Michaeli lemma gives only Ω(n) bias of size about (r−1)n/(r(r+1)), not n/(2r). This invalidates the stated bound in Theorem 3.1 as written. Since Theorem 1.4 only requires Ω(n) bias, the proof may be salvageable by changing the target constant, but all the inequalities in this final step must be adjusted accordingly.","section":"§3.3, proof of Theorem 3.1"},{"comment":"The proof of Lemma 4.5 contains an unjustified averaging claim: it states that some colour c* has at least n·αn·r^{−1} > n²/(2r) edges. Averaging over the r colour classes gives only e_{c*} ≥ e(G)/r ≥ αn²/(2r) = (r+1)n²/(4r²), which is smaller than n²/(2r) for every r ≥ 2. As written, the Erdős–Gallai argument does not apply. This is repairable: since t = 2^{5r} b ≤ n/(32r), the Erdős–Gallai bound can be sharpened to ex(n,P_t) ≤ (t−2)n/2 ≤ n²/(64r), and the averaged colour count is larger than this. But the current proof needs this correction before the existence of the almost-monochromatic cycle F is established.","section":"§4.1, Lemma 4.5"}],"minor_comments":[{"comment":"The numbering in Section 2 is inconsistent: Lemma 2.1 is proved under the name “Proof of Theorem 2.1”, and Lemma 2.2 is referred to as “Theorem 2.2”.","section":"§2"},{"comment":"Proposition 1.5 in the introduction is called “Theorem 1.5” in Section 2; the labels should be harmonized.","section":"§2, Proposition 1.5"},{"comment":"In the statement of Lemma 4.19, the phrase “at least t more edges of colour c” should refer to ℓ, the number of bowties, rather than t; as written it is ambiguous because t is defined earlier as 2^{5r} b.","section":"§4.2, Lemma 4.19"},{"comment":"In the proof of Lemma 4.16, when the selected side-edge colour c' equals c, the cycle H_2 has one more c-edge than H_1, not H_1 more than H_2. The conclusion still follows if the argument is phrased as a difference of ℓ/r in absolute value, but the sentence as written is not correct in that case.","section":"§4.2, Lemma 4.16"},{"comment":"In the greedy connection step, the proof says there are at least 4εn choices and that at most 4εn choices need to be forbidden; this only guarantees a surviving choice if the inequalities are strict or the constants are adjusted. A small constant slack would make the argument clean.","section":"§3.2, proof of Lemma 3.6"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a natural and timely question, and the overall strategy is plausible. The gaps I identified are concentrated in three places: the key overlap inequality in Lemma 4.20, the final bias estimate in Theorem 3.1, and the averaging step in Lemma 4.5. The first of these is load-bearing for the critical-case lower bound, and the second affects the quantitative statement of Theorem 3.1. I do not recommend rejection at this stage because each gap appears potentially repairable by adjusting constants or sharpening an existing bound, but the authors must supply a complete corrected proof, especially for Lemma 4.20, before the claims can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this paper. First, it targets the right question and identifies a genuinely new phenomenon: at the critical minimum degree (r+1)n/2r, the amount of colour bias in randomly perturbed graphs scales with the number m of added random edges, not with n. Second, the written proofs have two load-bearing gaps, and the paper as submitted does not prove its main theorems.\n\nThe good parts are real. The constructions in Section 2 are clean and correct: for alpha below critical, m=o(n) random edges can leave h_r=0, and at critical alpha there is an O(m) upper bound. The structural proposition (Theorem 4.2) is a sensible way to capture the obstruction to large bias, and the absorption framework for the perturbed setting is a natural combination of existing tools. If the gaps are patched, the results would be a solid contribution.\n\nNow the gaps, in order of severity. In Theorem 3.1, the final inequality (2/(r+1)-5eps)n >= n/r+n/(2r) is simply false for r=2,3. For r=2 the left side is about 2n/3 and the right side is 3n/4; for r=3 it's n/2 - 5eps n vs n/2. So the claimed n/(2r) bias is not derived. The proof still yields Omega(n) bias for all r, but not the stated constant; the theorem as written is not established for r=2,3. This is arithmetically fixable if they weaken the bias constant, but as it stands it's wrong.\n\nMore serious is Lemma 4.20. The degree-contradiction step that is supposed to force (15) does not work: from (13) and failure of (15) you only get |I(U) union I(U_i)| >= beta n - 7*2^{-6} beta^2 m, not beta n + 2^{-6} beta^2 m. Consequently d(x) can be as large as (1-beta)n + O(beta^2 m), which is compatible with delta(G_alpha) >= alpha n when alpha = 1-beta. Since this lemma supplies the Omega(m) matching in W that drives the lower bound in Theorem 1.6, the critical-case lower bound is unsupported. The stress-test note is right; I checked the union bounds and the contradiction doesn't go through.\n\nThe concern about the greedy absorption in Lemma 3.6 looks like a minor issue, not a real gap: the matching edges used are vertex-disjoint, so the count of available edges after removals is fine.\n\nBottom line: this is a serious paper with the right idea, but the proof has two holes, one in the dense case and one in the critical case. It deserves a referee, not a desk reject, but the referee should be asked to check the constants and the Lemma 4.20 argument carefully. If the authors can fix those, the paper would likely be right. I would not cite it in its current form.","headline":"Serious paper with a genuinely new critical-case phenomenon, but two load-bearing proof gaps (a false inequality in Thm 3.1 for r=2,3 and a failed degree-contradiction in Lemma 4.20) mean the main theorems are not proven as written.","tokens_in":24955,"tokens_out":11619,"would_cite":false,"duration_ms":98459,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","05C80","05C15","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adding O(n) random edges to any graph with minimum degree αn forces a Hamilton cycle with Ω(n) colour bias, and at the critical degree (r+1)n/2r the bias scales exactly with the number m of added random edges.","keywords":["colour bias","Hamilton cycles","randomly perturbed graphs","minimum degree","edge-colourings","absorption method","random graphs","discrepancy"],"falsifier":"Recompute the union bound in the proof of Lemma 4.20 with the paper's stated constants: two independent sets of size βn−$2^{{−4}}$β²m with intersection βn−$2^{{−6}}$β²m have union βn−7·$2^{{−6}}$β²m, which contradicts the claimed βn+$2^{{−6}}$β²m; checking whether a matching of size Ω(m) still exists under the weaker overlap is a direct finite calculation that would settle the lemma.","tokens_in":23759,"feed_emoji":"🎲","tokens_out":6431,"duration_ms":64350,"temperature":0.7,"pith_summary":"A Hamilton cycle has t colour bias if it contains n/r + t edges of a single colour in an r-edge-colouring; the paper asks how many random edges must be added to a fixed graph of minimum degree αn to guarantee, no matter how the union is coloured, a Hamilton cycle whose colour distribution is forced away from perfect balance. The first result says that for every α>0 a linear number m=O(n) of random edges suffices for Ω(n) bias. The second, at the critical minimum degree (r+1)/2r, pins down the dependence on m: adding m random edges yields Ω(m) bias whenever m is superconstant, and there are colourings that keep every Hamilton cycle at O(m) bias, so the answer is Θ(m). This gives the randomly perturbed threshold for colour-biased Hamilton cycles and shows that the extremal balanced-colouring construction is the only obstruction.","feed_headline":"O(n) random edges force a colour-biased Hamilton cycle","feed_subtitle":"At the critical minimum degree, the colour bias scales exactly with the number m of added random edges.","key_machinery":"The proof of the critical case rests on a structural characterization (Theorem 4.2): if an r-coloured G_α with δ ≥ (r+1)n/2r has no Hamilton cycle with Ω(m) colour bias, then some induced subgraph on αn vertices is almost monochromatic—every matching avoiding the dominant colour c* has at most o(m) edges. Assuming this fails, the authors build a near-monochromatic cycle F of length Θ(m) whose vertices can be absorbed into a spanning cycle H in two ways, using 'bowties' (two triangles sharing a centre vertex) as switching devices that change the colour count by a controlled amount. Together with a Pósa-type spanning-cycle lemma and random-graph lemmas guaranteeing long almost-monochromatic paths and large matchings in every βn-set, this yields the Ω(m) bound.","core_discovery":"The paper establishes two complementary statements. For every α>0 and r≥2, there is m=O(n) such that G_α ∪ G(n,m) with δ(G_α)≥αn typically satisfies h_r(G_α ∪ G(n,m)) = Ω(n): no matter how the union's edges are r-coloured, a Hamilton cycle has many more than n/r edges of one colour. For 0<α<(r+1)/2r, m=o(n) random edges are useless for this purpose—there are graphs of that minimum degree whose every Hamilton cycle is perfectly balanced regardless of the added edges. The critical case α=(r+1)/2r is where the paper's main theorem lies: for any m with 1≪m≤n, the typical value of h_r is Ω(m), and matching constructions force O(m), so the bias is linear in the number of random edges.","pith_inferences":["The structural dichotomy likely extends to a stability statement: graphs near the critical degree whose every Hamilton cycle is nearly balanced must contain a large nearly monochromatic set; a formal quantitative version could connect to discrepancy-stability results for other spanning structures.","The Θ(m) dependence suggests that the natural measure of 'randomness needed' for bias is the number of available random edges themselves; for m=n^{1/2}, the upper construction gives a concrete test case for algorithms that search for biased Hamilton cycles.","A testable extension is to push the Ω(m) result down to the regime where m is a constant (the current theorem needs 1≪m); a direct computation of the matching lemma at constant m would show whether the threshold is sharp at m=Θ(1).","The bowtie switching mechanism provides a colour-count identity that could be reused to bound the discrepancy of perfect matchings or small factors in randomly perturbed hypergraphs and graphs."],"forward_implications":["For any positive minimum degree, a linear number of random edges makes colour bias as large as it can be, matching the deterministic dense threshold up to the constant factor.","At the critical minimum degree (r+1)/2r, even a superconstant number m of random edges produces a superconstant colour bias, so the transition from zero bias to linear bias is governed by how many random edges are present.","The upper-bound constructions show the Ω(m) lower bound is tight up to constants: there are colourings in which every Hamilton cycle has colour bias at most O(m).","The structural dichotomy—no large bias forces a large nearly monochromatic induced subgraph—identifies the balanced-colouring example as the unique extremal obstruction in the critical regime."],"supporting_citations":[{"why":"Supplies the deterministic baseline: the Dirac-type theorem for Ω(d) colour bias at minimum degree (r+1)n/2r+d and the balanced-colouring construction that the critical-case result refines.","marker":"[FHLT21]"},{"why":"Initiated the study of h_r(G) and provided the two-colour base case and the two-cycles idea that the paper adapts in its Lemma 4.4.","marker":"[BCJP20]"},{"why":"Provides the long almost-monochromatic path lemma for random graphs, used as a building block of the Hamilton cycle in Section 3.","marker":"[GKM22]"},{"why":"Introduced the randomly perturbed graph model and proved the O(n) random-edge threshold for Hamiltonicity that Theorem 1.4 strengthens.","marker":"[BFM03]"},{"why":"Gives the k-joined DFS path lemma used to find the second long path in random subgraphs.","marker":"[KLS15]"},{"why":"Supplies the absorption method framework that the paper adapts to build the absorber path.","marker":"[RRS06]"},{"why":"Provides the spanning-cycle-with-prescribed-forest lemma used to build the cycle H that contains the required edges in the structural proof.","marker":"[P´63]"},{"why":"Gives the Kim–Vu concentration inequality used in the appendix to control the number of non-isolated edges and to prove the matching lemmas.","marker":"[KV00]"},{"why":"Supplies the standard conversion between G(n,p) and G(n,m) used in the proof of Theorem 4.1.","marker":"[JLR11]"}],"fun_headline_variants":["O(n) random edges force colour-biased Hamilton cycles","At critical degree, colour bias equals random edge count","Few random edges create Ω(n) colour bias in Hamilton cycles","Randomly perturbed graphs show colour bias in Hamilton cycles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound at the critical degree relies on a lemma that every βn-sized vertex set either contains a large matching already or overlaps one of finitely many exceptional sets in a large independent set, with the overlap bounded away from the whole set; the paper's own inequalities do not force that overlap, so this inheritance step is the load-bearing assumption.","fun_headline_variants_meta":{"raw":{"variants":["O(n) random edges force colour-biased Hamilton cycles","At critical degree, colour bias equals random edge count","Few random edges create Ω(n) colour bias in Hamilton cycles","Randomly perturbed graphs show colour bias in Hamilton cycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000341,"raw_usage":{"total_tokens":1945,"prompt_tokens":1075,"completion_tokens":870,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":691,"completion_tokens_details":{"reasoning_tokens":803}},"tokens_in":691,"tokens_out":870,"duration_ms":9070,"temperature":1.0,"reasoning_tokens":803,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:49:11.775011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the union bound in the proof of Lemma 4.20 with the paper's stated constants: two independent sets of size βn−$2^{{−4}}$β²m with intersection βn−$2^{{−6}}$β²m have union βn−7·$2^{{−6}}$β²m, which contradicts the claimed βn+$2^{{−6}}$β²m; checking whether a matching of size Ω(m) still exists under the weaker overlap is a direct finite calculation that would settle the lemma.","supporting_citations":[],"review_version":1}