{"id":"0c91c8ba-b2c7-4ded-8e4b-221451f56d64","arxiv_id":"2507.17739","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"With minimum degree n/2+Θ(m), graphs whose Hamilton cycles all have color-bias below m must be close to a color-dominant or a symmetric 3-partite construction, and this degree condition is tight for r=2.","lead":"This paper proves sharp stability theorems for Hamilton cycles in edge-colored graphs: any graph whose minimum degree just exceeds n/2, and whose Hamilton cycles all keep each color almost equally frequent, must resemble one of a few explicit extremal constructions. The degree slack Θ(m) is also shown to be optimal when the graph has two colors.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2.5 is false as stated: under the formal Definition of Type B, the paper's own r=2 extremal construction contradicts the asserted single-k dichotomy, and the later proof uses B(k,l) with the two indices reversed.","rationale":"The reader identified the unproved enumeration in Proposition 2.4 as the weakest assumption. I agree that enumeration is asserted too casually, but the more load-bearing, and more easily settled, problem is that Proposition 2.5 is false under the paper's own definitions. The r=2 extremal graph from the introduction satisfies all hypotheses of the main theorem, contains no bad bowties, and yet has vertex set B(1,2) union C(2), so no color k makes Proposition 2.5(1) true. This is not a matter of a missing subcase: it is a direct contradiction between the formal definition of Type B(k,l) (incident color k, neighborhood color l) and the later usage of B(k,l) (incident color l). Since Proposition 2.5 is the bridge from local vertex types to the global partition used in Theorems 1.2 and 1.3, the proof as written cannot be correct. The intended argument is recognizably repairable by systematically swapping the two indices in the dominant-color branch, which is why I do not recommend outright rejection; the paper should remain conditional on a corrected and verified version of the dichotomy. My concrete test isolates exactly that swap and would settle whether the intended statement is recoverable.","tokens_in":13261,"tokens_out":28135,"duration_ms":287896,"concrete_test":"Instantiate the r=2 extremal construction from Section 1 with n divisible by 4 and m=1, so the assumptions of Theorem 1.2 hold. Compute the Type of a vertex in V1 and a vertex in V2 using the formal definition of Type B in Section 2.3, and test both choices of k in Proposition 2.5(1); the asserted equality fails for k=1 and for k=2. Then redo the same check with the reversed convention B(k,l):= vertices whose incident edges all have color l and whose N_l-neighborhood edges all have color k, and verify that Proposition 2.5(1) and the counting in Section 2.4 are consistent only after every dominant-branch occurrence of B(k,l) is replaced by B(l,k).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 2.5 is false as stated under the formal Definition in Section 2.3, even for the paper's own r=2 extremal construction from Section 1. In that construction V1 has size n/4, V2 has size 3n/4, V1-V2 edges are color 1, internal V2 edges are color 2, and V1 is independent. The graph has no bad bowties, so G1=G. A vertex v in V1 has L(v)={1} and N1(v)=V2 with all internal edges of V2 colored 2, hence v is Type B(1,2). A vertex in V2 is Type C(2). Thus V(G1)=B(1,2) union C(2). Proposition 2.5(1) asserts a single k with V(G1)=union over l!=k of B(k,l) union C(k); for k=1 it omits V2 and for k=2 it omits V1. Moreover, the proof in Section 2.4 later treats B(k,l) as the set of vertices whose incident edges are color l, which is the reverse of the formal definition. The dominant-color branch needs B(l,k) in place of B(k,l) throughout; as printed, the structural dichotomy that drives the partition in Theorems 1.2 and 1.3 is internally inconsistent. This concern is independent of the unproved enumeration in Figure 2.1: even granting that enumeration, Proposition 2.5 cannot be true with the stated type definitions.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proves stability theorems for edge-colored graphs in which every Hamilton cycle has small color-bias. Theorem 1.2 (for r≠3) and Theorem 1.3 (for r=3) assert that if δ(G)=n/2+Θ(m) and every Hamilton cycle has discrepancy <m, then G admits a partition into one large and r−1 small parts (or, in the r=3 case, a symmetric tripartite alternative) such that all color-class complements have matchings of size at most O(r²m). The proof removes O(rm) vertices containing 'bad bowties', classifies the remaining vertices into local types A, B, C, proves a global dichotomy for G1, and then converts the dichotomy into matching-exclusion statements. A separate construction with two colors and minimum degree n/2+o(m) shows that the additive Θ(m) error is best possible for r=2.","tokens_in":13508,"tokens_out":32213,"duration_ms":334483,"significance":"If the proof can be completed, the results are significant: they move the structural stability threshold for color-balanced Hamiltonicity from the extremal threshold (r+1)n/(2r) down to the Dirac threshold n/2, with an error term Θ(m), and they establish optimality of the error for r=2. The 'bad bowtie' local-to-global mechanism is a promising new ingredient, and the use of Pósa's lemma to convert local color imbalances into forbidden Hamilton-cycle discrepancies is elegant. The paper is not merely an incremental extension: it addresses the near-balance regime at degrees far below the extremal threshold, and the quantitative lower-bound construction for r=2 is a genuine addition. However, the significance is conditional on repairing several load-bearing gaps in the written proof, which are listed below.","major_comments":[{"comment":"With the formal definition B(k,l) = {v : L(v)={k} and all edges in E(G1[N_k(v)]) have color l}, the r=2 extremal construction of Section 1 (V1 independent, V2 complete, V1-V2 edges color 1, internal V2 edges color 2) contains no bad bowties, so G1=G; it satisfies V(G1)=B(1,2)∪C(2). Proposition 2.5(1) claims a single k with V(G1)=⋃_{l≠k}B(k,l)∪C(k), but for k=1 the right-hand side is only V1 and for k=2 it is only V2. Thus Proposition 2.5 is false as stated. The proof and Section 2.4 systematically use B(k,l) with the reverse meaning, namely 'vertices whose incident edges all have color l', which corresponds to B(l,k). The indices must be reversed consistently throughout the dominant-color branch before the structural dichotomy can be true.","section":"Section 2.3 (Definition of B(k,l)), Proposition 2.5(1), and Section 2.4"},{"comment":"The proof that two vertex-disjoint edges in G1[N(v)] of different types create a bad bowtie is the entire justification for the trichotomy into types A, B, C, but it rests on the assertion that the enumeration of non-bad bowties in Fig. 2.1 is complete and on the phrase 'one can easily check'. No proof of the completeness of that enumeration is provided, and the figure is not described in the text. Since every subsequent step, including Proposition 2.5 and Theorems 1.2 and 1.3, depends on this uniqueness-of-type fact, the enumeration needs a rigorous proof or a machine-checked certificate rather than an assertion.","section":"Section 2.3, proof of Proposition 2.4"},{"comment":"The displayed inequality 2(|A(1,2,3)|−2|V0|) ≤ |A(2,3,1)|+|A(3,1,2)| is incorrect. A vertex in A(2,3,1)∪A(3,1,2) may have both Hamilton-cycle neighbors in A(1,2,3), so the number of cross edges is bounded by 2(|A(2,3,1)|+|A(3,1,2)|), not by that sum. With the correct factor 2, the argument gives only |A(1,2,3)| ≤ n/2+O(rm), which does not imply the claimed |A(1,2,3)| ≤ n/3+10rm. The balance |A_i| ≈ n/3 needs a different proof, for example by counting the three color classes through the incidence identities 2|A_i| = (number of Hamilton edges of the corresponding pair of colors) + O(|V0|) and using dχ(H)<m.","section":"Section 2.4, proof of Theorem 1.3(1)"},{"comment":"The line 'no vertex in G1 can be adjacent to an edge colored with any color outside of {j,k,l}, which implies that r=3' is not a valid inference as written. An r-coloring need not be surjective, and colors outside {j,k,l} could appear on edges incident to the removed set V0; both are compatible with r>3. If the intended argument is that any Hamilton cycle would then have too few edges of a color outside {j,k,l}, that color-bias argument must be written out and must account for the up to O(rm) edges incident to V0. As printed, the A-type case is not excluded for r>3.","section":"Section 2.3, proof of Proposition 2.5(2)"}],"minor_comments":[{"comment":"The theorems state δ(G)=n/2+6r²m (and δ(G)=n/2+54m for r=3), while the abstract and the proofs use the condition 'exceeding' or 'at least'. The statements should say δ(G) ≥ n/2+6r²m (respectively ≥ n/2+54m).","section":"Theorem 1.2 and Theorem 1.3 statements"},{"comment":"The displayed bounds |V(M_i)| ≤ |W_i| are false for matchings whose edges have exactly one endpoint in W_i and one endpoint outside; the correct bound is 2|W_i|. Since 2·40r²m = 80r²m < 100r²m, the quantitative conclusions still survive after this correction, but the inequalities should be repaired.","section":"Section 2.4, matching-exclusion bounds"},{"comment":"The proof section begins with the assumption dχ(H) ≤ m for every Hamilton cycle, whereas Theorems 1.2 and 1.3 assume dχ(H) < m. These should be aligned.","section":"Section 2, opening paragraph"},{"comment":"There are several typographical errors, including 'an graph' in Lemma 2.1 and 'n-vetrex' in the introduction; the manuscript would benefit from a careful proofreading pass.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are plausible and the high-level strategy is attractive, but the written proof is not reliable in its current form: the false index convention in Proposition 2.5, the unproved bowtie enumeration in Proposition 2.4, the invalid averaging inequality in the A-type case, and the unsupported 'r=3' inference each need substantial repair. I would not recommend rejection because the identified issues appear repairable within the paper's framework, and the r=2 lower-bound construction is a solid contribution that should be preserved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The main results are natural and likely correct: Theorems 1.2 and 1.3 locate the structural stability threshold for color-biased Hamilton cycles at the Hamiltonicity threshold n/2, with additive error optimal for r=2, and the r=3 symmetric case is handled carefully. The proof idea—remove bad bowties, classify vertices, force a global dichotomy—is sound. But the written proof has a load-bearing inconsistency in the classification. Under the formal definition of Type B(k,l) (Section 2.3), a vertex has all incident edges colored k and all edges inside its neighborhood colored l. Proposition 2.5 then claims that for r≠3, all vertices lie in union of B(k,l) over l≠k plus C(k). The paper's own r=2 extremal construction refutes this: V1 vertices are B(1,2), V2 vertices are C(2), and no single k gives the claimed union. Section 2.4 later counts as if B(k,l) meant the opposite—vertices whose incident edges are color l—and with that reading the dichotomy works. So the fix is likely a systematic index swap, but as printed the proof cannot be verified.\n\nSecond soft spot: Proposition 2.4's trichotomy depends on an unproved enumeration of non-bad bowtie color patterns in Figure 2.1 ('one can easily check'). That gap is independent of the indexing bug and needs a real argument. Minor issue at the end: matching-exclusion arguments occasionally write |V(M)| ≤ |W| when the proof only shows M ⊆ E(W); the bounds are the same order, so it's cosmetic.\n\nCredit where due: the paper is not circular, uses Pósa's lemma cleanly, gives a sharp counterexample for the Θ(m) term when r=2, and engages honestly with Chen-Cheng-Yan. No free parameters, no fitted entities beyond the bowtie, which is a legitimate local witness.\n\nBottom line: the theorems deserve proof and are probably true, but this manuscript is not publishable as is. Send it to a serious referee, with instructions to fix the B(k,l) indexing and supply the bowtie enumeration.","headline":"Strong and likely correct stability theorems, but the written proof's central B-type definition is reversed relative to its use, making Proposition 2.5 false as stated.","tokens_in":14148,"tokens_out":10683,"would_cite":false,"duration_ms":102040,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C45","05C15","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that if all Hamilton cycles in a dense edge-colored graph are nearly color-balanced, the graph must be close to one of the known extremal color-partition constructions.","keywords":["color-bias","discrepancy","Hamilton cycles","stability","edge-coloring","bowtie","minimum degree","extremal constructions"],"falsifier":"Enumerate all $3^6$ colorings of the six edges of the bowtie (or all $2^6$ for two colors), compute $f(B,k)$ for each color, and compare the patterns with $f(B,k)=0$ for every $k$ against the list in Fig. 2.1. If any zero-bias coloring is missing from the figure, two vertex-disjoint edges in some neighborhood could carry different types without forming a bad bowtie, and Proposition 2.4 would fail.","tokens_in":12966,"feed_emoji":"🔄","tokens_out":11204,"duration_ms":99311,"temperature":0.7,"pith_summary":"This paper proves a stability theorem for color-balanced Hamilton cycles in edge-colored graphs. It shows that if an $n$-vertex graph with minimum degree just above $n/2$ has every Hamilton cycle deviating from equal color counts by less than $m$, then the graph must be close to one of the known extremal constructions: a partition with one dominant part whose edges are nearly monochromatic, or, for three colors, a nearly balanced tripartite color-symmetric graph. The degree threshold $n/2$ is exactly the classical Hamiltonicity threshold, so it cannot be lowered, and the additive error term $\\Theta(m)$ is shown to be best possible for two colors. The result places the structural stability threshold for balanced Hamiltonicity at $n/2$, strictly below the extremal threshold $(r+1)n/(2r)$ at which color imbalance is forced.","feed_headline":"Just above n/2, near-balanced cycles force an extremal skeleton","feed_subtitle":"Any graph whose Hamilton cycles stay within bias m must almost match a monochromatic-partition construction.","key_machinery":"The load-bearing local object is the bad bowtie: five vertices $v_1,\\dots,v_5$ with edges $v_1v_2,v_1v_3,v_1v_4,v_1v_5,v_2v_3,v_4v_5$, together with the color-shift function $f(B,k)=\\mathbf{1}_k(v_1v_2)+\\mathbf{1}_k(v_1v_3)+\\mathbf{1}_k(v_4v_5)-\\mathbf{1}_k(v_1v_4)-\\mathbf{1}_k(v_1v_5)-\\mathbf{1}_k(v_2v_3)$. A bowtie is bad when some $f(B,k)\\ne 0$; replacing the first three edges by the second three gives a new Hamilton cycle whose color-$k$ count changes by $f(B,k)$. The proof bounds the number of disjoint bad bowties by $2rm$, deletes their vertices, and in the remaining graph classifies every vertex as one of three types $A(j,k,\\ell)$, $B(k,\\ell)$, or $C(k)$ according to the colors that occur inside its neighborhood. The completeness of this trichotomy turns local color patterns into the global dichotomy of Proposition 2.5, and the dichotomy yields the matching-exclusion statements of the theorems.","core_discovery":"On its own terms, the central claim is that the only way for a dense graph to keep all its Hamilton cycles nearly color-balanced is to sit inside one of the extremal color-partition constructions. For $r\\ge 2$, $r\\ne 3$, under $\\delta(G)=n/2+6r^2m$ and $d_\\chi(H)<m$ for every Hamilton cycle $H$, the graph admits a partition $V_1\\cup\\cdots\\cup V_r$ with $|V_k|=(r+1)n/(2r)$ and $|V_i|=n/(2r)$ for $i\\ne k$ such that $G[V_k]$ is $(100r^2m,k)$-nearly monochromatic, each $G[V_i,V_k]$ is $(100r^2m,i)$-nearly monochromatic, and the induced graph on the small parts is $100r^2m$-nearly empty. For $r=3$ there is a second allowed alternative, a balanced three-part structure in which each cross pair $G[V_i,V_j]$ is $(900m,k)$-nearly monochromatic for the third color $k$ and each part is nearly empty. These statements place the stability threshold at $n/2$ and make the additive error linear in $m$; the linear error is optimal for $r=2$.","pith_inferences":["A reader who wants to stress-test the proof should start with the six-edge enumeration: an exhaustive check of $3^6$ colorings would confirm or refute the 'one can easily check' step in Proposition 2.4.","The same bad-bowtie replacement should transfer to Hamilton paths or perfect matchings, yielding analogous stability dichotomies for other spanning subgraphs in edge-colored graphs.","For $r\\ge 3$ the optimality of the $\\Theta(m)$ error remains open; if counterexamples exist, they may interpolate between the dominant-hub and the balanced tripartite extremal forms.","If the paper's final local-resilience conjecture holds, the structural dichotomy would survive even when the global minimum-degree assumption is replaced by a much weaker robustness hypothesis."],"forward_implications":["For every $r\\ge 2$, $r\\ne 3$, the hypotheses imply a partition into parts of sizes $(r+1)n/(2r)$ and $n/(2r)$ with the three matching-exclusion bounds of Theorem 1.2 holding at scale $100r^2m$.","For $r=3$, any such graph is either the balanced three-part color-symmetric structure or the single-dominant-part structure, and the two alternatives are mutually exclusive.","The degree condition cannot be relaxed to $n/2+o(m)$ without allowing the two-color counterexample, so the additive error term in the theorem is best possible for $r=2$.","In this degree regime every Hamilton cycle is forced to be nearly uniform in its color counts, and the structural obstruction to imbalance is a large monochromatic hub."],"supporting_citations":[{"why":"supplies the rotation-extension lemma used to extend a small union of vertex-disjoint paths into a Hamilton cycle, the tool that turns a bad bowtie into two cycles of different color counts.","marker":"[30]"},{"why":"provides the sharp extremal threshold and the extremal constructions whose structural proximity the theorems assert.","marker":"[17]"},{"why":"states the sharp color-bias guarantee used as Theorem 1.1, with the quantitative constant the paper compares against.","marker":"[20]"},{"why":"gives the earlier structural stability result at the higher degree $(r+1)n/(2r)$ that this paper strengthens to degree $n/2+6r^2m$.","marker":"[9]"},{"why":"establishes the $n/2$ Hamiltonicity threshold, which makes the leading term of the degree condition optimal.","marker":"[12]"}],"fun_headline_variants":["Near-balanced cycles force dense graphs into extremal partitions","n/2 threshold: balanced cycles force near-extremal structure","Stability at n/2: all cycles near-balanced forces extremal skeleton","Rigid dichotomy: near-balanced Hamilton cycles imply extremal partition"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the small figure listing all non-bad six-edge bowtie colorings is complete; the paper asserts this with 'one can easily check' and gives no proof, and if a coloring is missing the vertex classification collapses.","fun_headline_variants_meta":{"raw":{"variants":["Near-balanced cycles force dense graphs into extremal partitions","n/2 threshold: balanced cycles force near-extremal structure","Stability at n/2: all cycles near-balanced forces extremal skeleton","Rigid dichotomy: near-balanced Hamilton cycles imply extremal partition"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000781,"raw_usage":{"total_tokens":3582,"prompt_tokens":1209,"completion_tokens":2373,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":825,"completion_tokens_details":{"reasoning_tokens":2299}},"tokens_in":825,"tokens_out":2373,"duration_ms":19065,"temperature":1.0,"reasoning_tokens":2299,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:19:03.604992+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all $3^6$ colorings of the six edges of the bowtie (or all $2^6$ for two colors), compute $f(B,k)$ for each color, and compare the patterns with $f(B,k)=0$ for every $k$ against the list in Fig. 2.1. If any zero-bias coloring is missing from the figure, two vertex-disjoint edges in some neighborhood could carry different types without forming a bad bowtie, and Proposition 2.4 would fail.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the rotation-extension lemma used to extend a small union of vertex-disjoint paths into a Hamilton cycle, the tool that turns a bad bowtie into two cycles of different color counts."},{"cited_title":"Freschi, J","cited_arxiv_id":null,"evidence_quote":"provides the sharp extremal threshold and the extremal constructions whose structural proximity the theorems assert."},{"cited_title":"Gishboliner, M","cited_arxiv_id":null,"evidence_quote":"states the sharp color-bias guarantee used as Theorem 1.1, with the quantitative constant the paper compares against."},{"cited_title":"Colour-biased Hamilton cycles in randomly perturbed graphs","cited_arxiv_id":"2506.04189","evidence_quote":"gives the earlier structural stability result at the higher degree $(r+1)n/(2r)$ that this paper strengthens to degree $n/2+6r^2m$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"establishes the $n/2$ Hamiltonicity threshold, which makes the leading term of the degree condition optimal."}],"review_version":1}