{"id":"6cd65db0-71b6-4c69-907f-8125435b40e7","arxiv_id":"2411.17232","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For each odd ℓ ≥ 5, the decomposition threshold for ℓ-cycles is at most 1/2 + 1/(2ℓ−4), improving the previous best bound dramatically.","lead":"The paper proves that every sufficiently large graph whose minimum degree is just above half its vertex count can be decomposed into cycles of any fixed odd length at least five, under the natural divisibility conditions. This lowers the known degree threshold substantially, nearly matching a known lower bound.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Lemma 4.2 applies Lemma 4.5 through a density inequality that is generally false, so the condensation-to-approximate-decomposition step (Theorem 1.3) is not established as written.","rationale":"The paper's approach is attractive and many components check out: the fractional weighted-triangle Theorem 1.2 is algebraically sound, Lemma 3.1 and Theorem 3.2 are clean, and Lemma 4.3 is essentially correct modulo a harmless reciprocal typo. The import of Theorem 1.4 from Barber-Kuhn-Lo-Osthus is a reasonable external assumption if that theorem is correct. However, the critical bridge from a fractional decomposition of the reduced graph to an approximate integral decomposition of the original graph is Lemma 4.2, and that proof contains a concrete gap. The density chain used to justify Lemma 4.5 is false for regular pairs with density below 1, which can certainly occur. This is not a matter of disagreeing with the consensus but an internal correctness issue in a central proof step. If the gap cannot be fixed, Theorem 1.3 and therefore Theorem 1.1 are unsupported as written. However, the gap is likely repairable with a standard epsilon-cleaning argument, so rather than reject, the appropriate verdict is conditional acceptance pending a corrected treatment of the density allocation in Lemma 4.2.","tokens_in":15728,"tokens_out":19126,"duration_ms":169667,"concrete_test":"Re-derive the application of Lemma 4.5 in Lemma 4.2 with eps2-regular pair (A,B) of density d < 1 and subpair (A',B') of size b with density d - eps2; set w_R = d and delta_h = (1-eps2) w_h with sum_h w_h = w_R. Verify that sum_h delta_h = (1-eps2)d > d - eps2 = d(A',B'), so the displayed inequality in the proof fails. Then check whether the eta-budget in Equation (3) and the final estimate (6) can be reorganized to carry the resulting O(eps2 n^2) loss; if no such reorganization is possible without changing the proof, Lemma 4.2 and hence Theorem 1.3 are not established as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Lemma 4.2, to color the edges of each subpair G[Vi,j, Vi',j'] with colors from C_e, the authors need the hypothesis of Lemma 4.5: sum_{h in C_e} delta_h <= d(G[Vi,j], Vi',j'). Their displayed justification is sum_{h} delta_h <= (1-eps2) w_R(ii') <= (1-eps2) d(G[Vi,Vi']) <= d(G[Vi,j], Vi',j'). The last inequality is asserted by 'the definition of R', but it is not valid. An eps2-regular pair of density d can contain a subpair of size b with density as low as d - eps2, while (1-eps2)d > d - eps2 for every d < 1. Thus even in the ideal case w_R(ii') = d(G[Vi,Vi']), the total demand can exceed the subpair capacity by about eps2(1-d). No lower bound on d is available, and the earlier inequalities (3)-(6) do not reserve the eta-slack needed to absorb this per-pair excess. Since Theorem 1.3 is proved solely through Lemma 4.2, and Theorem 1.1 relies on Theorem 1.3, the central claim is not fully supported by the written argument. The gap appears repairable by a standard cleaning argument that discards a small eta-fraction of edges in low-density pairs, but such an argument is absent.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decomposition thresholds for odd cycles and other tripartite graphs. The main result, Theorem 1.1, states that for every odd ℓ ≥ 5 and ε > 0, every sufficiently large C_ℓ-divisible graph with minimum degree at least (1/2 + 1/(2ℓ−4) + ε)n has a C_ℓ-decomposition, while the threshold cannot be improved below 1/2 + 1/(2ℓ−2). The proof combines a new fractional decomposition result for weighted triangles (Theorem 1.2), a condensation argument converting fractional decompositions into approximate integral decompositions (Theorem 1.3), and the imported exact-vs-approximate threshold equality of Barber–Kühn–Lo–Osthus (Theorem 1.4 from [1]). Section 5 applies the same machinery to general tripartite graphs, giving bounds for K_{a,1,1}, K_{a,a,1}, and K_4^-.","tokens_in":16056,"tokens_out":14286,"duration_ms":121094,"significance":"If the proof is completed, this is a substantial improvement: for odd cycles the upper bound moves from a constant away from 1/2 (or a slow O(ℓ^{-1/8!}) rate) to 1/2 + O(1/ℓ), which is within a factor of 2 of the likely optimal threshold. The paper also contributes a clean fractional weighted-triangle decomposition theorem with an explicit degree condition, and it identifies condensation as a useful bridge between fractional and integral decompositions. Strengths include the self-contained derivation of Theorem 1.2 via majorization, the explicit lower-bound constructions in Lemmas 2.1 and 2.3, and the transparent layout of the regularity argument. The main theorem is conditional on the imported equality δ_{C_ℓ} = δ^{0+}_{C_ℓ} from [1, Theorem 1.4]; this dependency is explicitly stated and is standard for this line of work, but it is an external result.","major_comments":[{"comment":"The proof that Lemma 4.5 can be applied to each subpair G[V_{i,j}, V_{i',j'}] relies on the inequality (1−ε₂)d(G[V_i,V_{i'}]) ≤ d(G[V_{i,j},V_{i',j'}]). This is not justified and is generally false: an (ε₂,d)-regular pair of density d can have a subpair of size b with density as low as d − ε₂, and for d < 1 one has (1−ε₂)d > d − ε₂. No lower bound on d is available, so the hypothesis of Lemma 4.5, namely ∑_{h∈C_e} δ_h ≤ d(G[V_{i,j},V_{i',j'}]), is not established. This step is load-bearing: it is exactly how the fractional F-packing of Q is converted into the (F,b,≥δ₀,ε)-graphs, and Lemma 4.2 is the only route to Theorem 1.3, which in turn is needed for Theorem 1.1. The gap appears repairable by a standard cleaning step that discards a small fraction of edges in low-density subpairs and absorbs the loss into the ηn² leftover, but no such argument is present in the manuscript.","section":"Section 4, Lemma 4.2 (display before Eq. (5))"}],"minor_comments":[{"comment":"In the proof of Lemma 4.3, the displayed value δ_e = 1/(|A|q²) is the reciprocal of the correct value. From the preceding line, |A_e| = w_Q(e)|A|/q², so δ_e = w_Q(e)/|A_e| = q²/|A|. With the printed value the weighted graphs do not sum to Q; the subsequent argument only needs a uniform positive weight, so this is a typographical/arithmetic slip rather than a substantive error.","section":"Lemma 4.3"},{"comment":"The lower bound is stated as 1/2 + 1/(2a+a); the computation from Lemma 2.1 with ρ = 1/(a+2) gives 1/2 + 1/(2a+2). The displayed expression should presumably be 1/(2a+2).","section":"Corollary 5.4"},{"comment":"In the displayed inequality preceding Eq. (5), the notation δ_h^e is used before its definition; each δ_h depends on the edge e through the set C_e, and the proof would be easier to follow if this dependence were made explicit in the definition of δ_h.","section":"Section 4, Lemma 4.2"}],"recommendation":"major_revision","confidential_remarks":"The gap in Lemma 4.2 is localized and likely fixable with a short cleaning argument. If the authors supply such an argument, I would be willing to accept; the rest of the proof and the fractional results appear sound. The paper would also benefit from a sentence in the introduction emphasizing that Theorem 1.1 is conditional on the imported equality δ_{C_ℓ}=δ^{0+}_{C_ℓ} from [1]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The condensation method is a genuine advance: Theorem 1.2 gives a clean fractional weighted-triangle decomposition via majorization, and Theorem 1.3 is exactly the kind of bridge result the field needs, turning fractional condensations into approximate F-decompositions. Together they push the odd-cycle decomposition threshold from 1/2 + O(ℓ^{-1/8!}) to 1/2 + 1/(2ℓ−4), nearly matching the lower bound. The lower-bound lemmas in Section 2 are neat, and the paper is upfront about importing Theorem 1.4 from [1] and Theorem 5.1 from [6]; the self-citation there is not a problem.\n\nThe problem is in the proof of Lemma 4.2, and the reader's report missed it. When applying Lemma 4.5 to the subpair G[Vi,j, Vi',j'], the paper needs ∑_{h∈C_e} δ_h ≤ d(G[Vi,j, Vi',j']). It justifies this with (1−ε2) w_R(ii') ≤ (1−ε2) d(G[Vi,Vi']) ≤ d(G[Vi,j, Vi',j']). The last inequality is false. Regularity only tells us the subpair density is at least d(G[Vi,Vi']) − ε2, and (1−ε2)d is larger than d−ε2 by ε2(1−d). So the demand can exceed the capacity of the subpair. The fix is standard—discard a small η-fraction of edges in low-density subpairs before coloring—but that cleaning step is absent. Since Theorem 1.3 is proved only through Lemma 4.2, and Theorem 1.1 depends on Theorem 1.3, the central claim is not fully supported as written. The reciprocal typo in Lemma 4.3 (δ_e should be q^2/|A|, not 1/(|A|q^2)) is harmless and doesn't affect the argument.\n\nOverall, the main idea is valuable and likely correct; the gap is technical, not a hidden counterexample. Specialists in graph decompositions will want to read this. With a repaired Lemma 4.2 it becomes a solid accept. As it stands, it deserves peer review, but the referee should ask for the missing cleaning argument.","headline":"The condensation method is a real step forward, but the proof of Lemma 4.2 has a density-regularity gap that needs patching before the main theorem is established.","tokens_in":16618,"tokens_out":6655,"would_cite":false,"duration_ms":54241,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C38","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"For each odd $\\ell \\geq 5$, every sufficiently large $C_\\ell$-divisible graph with minimum degree at least $(\\frac{1}{2}+\\frac{1}{2\\ell-4}+o(1))n$ has a decomposition into $\\ell$-cycles whenever the trivial divisibility conditions hold.","keywords":["graph decomposition","cycle decomposition","decomposition threshold","minimum degree","fractional decomposition","weighted triangles","regularity lemma","tripartite graphs"],"falsifier":"Construct, for some odd $\\ell \\geq 5$, a $C_\\ell$-divisible $n$-vertex graph with minimum degree at least $(\\frac{1}{2}+\\frac{1}{2\\ell-4}+\\varepsilon)n$ and no $C_\\ell$-decomposition; that would directly refute the main theorem. A cleaner test of the proof chain would be to exhibit a graph with an $\\eta$-approximate $C_\\ell$-decomposition for every $\\eta>0$ but no exact $C_\\ell$-decomposition, since the exactness step assumes no such graph exists.","tokens_in":48,"feed_emoji":"🔄","tokens_out":13147,"duration_ms":186193,"temperature":0.7,"pith_summary":"This paper pins down the asymptotic minimum-degree threshold for decomposing a large graph into cycles of a fixed odd length $\\ell \\geq 5$. It proves that every sufficiently large $C_\\ell$-divisible graph whose minimum degree is at least $(\\frac{1}{2}+\\frac{1}{2\\ell-4}+o(1))n$ splits into $\\ell$-cycles, and that no threshold below $\\frac{1}{2}+\\frac{1}{2\\ell-2}$ can work. The new upper bound improves older bounds that approached $\\frac{1}{2}$ very slowly; the two bounds differ by about $\\frac{1}{2\\ell^2}$. The route goes through fractional decompositions into weighted triangles, a general conversion of fractional decompositions into approximate ones, and a known result promoting approximate cycle decompositions to exact ones.","feed_headline":"Odd cycles split above a sharply lower degree threshold","feed_subtitle":"For odd ℓ≥5, Cℓ-divisible graphs decompose above 1/2+1/(2ℓ−4); the bound cannot drop below 1/2+1/(2ℓ−2).","key_machinery":"The central object is the condensation of a target graph $F$: partition the vertices of $F$ into independent sets, then record for each pair of parts the number of $F$-edges crossing that pair as the weight on an edge of a smaller graph. For an odd cycle $C_\\ell$, a natural condensation is the weighted triangle $T_{\\ell-2,1,1}$. The load-bearing identity is a characterization of when one weighted triangle has a fractional decomposition into scaled copies of another: $T_{w_1,w_2,w_3}$ decomposes into $T_{e_1,e_2,e_3}$ exactly when the smallest relative weight is at least the target's smallest relative weight and the largest relative weight is at most the target's largest, a fact proved by majorization and the doubly stochastic rearrangement theorem. This identity converts a minimum-degree bound into a fractional decomposition, and a regularity-based lemma converts that fractional decomposition into an approximate cycle decomposition.","core_discovery":"The paper's central claim is that for each fixed odd $\\ell \\geq 5$, the exact $C_\\ell$-decomposition threshold lies between $\\frac{1}{2}+\\frac{1}{2\\ell-2}$ and $\\frac{1}{2}+\\frac{1}{2\\ell-4}+o(1)$. The upper bound is reached by showing that above this degree every graph has a fractional decomposition into scaled copies of the weighted triangle $T_{\\ell-2,1,1}$, then converting that fractional object into an approximate $C_\\ell$-decomposition with only $o(n^2)$ leftover edges, and finally promoting the approximate decomposition to an exact one using a previously established equality between exact and approximate cycle decomposition thresholds. The divisibility conditions used are the unavoidable ones: $\\ell$ must divide the number of edges and every vertex degree must be even.","pith_inferences":["The same condensation pipeline could be run with weighted $K_k$ in place of weighted triangles, which would generalize the method to graphs of chromatic number $k>3$ and may beat the current $1-\\frac{1}{\\chi+1}$ ceiling for some families.","The residual gap between the upper and lower cycle thresholds comes mainly from the fractional weighted-triangle step; sharpening the fractional triangle theorem or the companion lower-bound lemmas would tighten the final window without changing the rest of the argument.","For complete tripartite graphs $K_{a,a,1}$, the paper's bounds leave open whether the threshold approaches $\\frac{1}{2}$; checking small $a$ against the fractional triangle conditions would show whether the bottleneck is the weighted-triangle bound or the exactness promotion."],"forward_implications":["The exact threshold for $C_\\ell$-decompositions is pinned between $\\frac{1}{2}+\\frac{1}{2\\ell-2}$ and $\\frac{1}{2}+\\frac{1}{2\\ell-4}$, a window of width about $\\frac{1}{2\\ell^2}$.","Every $C_\\ell$-divisible graph above the upper degree bound has an exact decomposition into $\\ell$-cycles, not merely an approximate one.","For general tripartite graphs, the decomposition threshold is capped by a fractional weighted-triangle bound or by $\\frac{3}{4}$, giving explicit bounds such as $\\frac{4}{5}$ for $K_4^-$ and $\\frac{3}{4}$ for $K_{a,1,1}$.","The previous bound $\\frac{1}{2}+O(\\ell^{-1/8!})$ for odd cycles is replaced by $\\frac{1}{2}+\\frac{1}{2\\ell-4}$, so the threshold approaches $\\frac{1}{2}$ far more quickly as $\\ell$ grows."],"supporting_citations":[{"why":"Supplies the equality of exact and approximate cycle decomposition thresholds, the step that turns the paper's approximate decomposition into an exact one.","marker":"[1]"},{"why":"Provides the doubly stochastic decomposition theorem used inside Lemma 3.1 for the weighted-triangle characterization.","marker":"[3]"},{"why":"Supplies the lemma that splits an epsilon-regular bipartite graph into smaller regular pieces, used in the proof of the approximate-decomposition lemma.","marker":"[5]"},{"why":"Provides the general decomposition-threshold theorem and the 3/4 cap used for the paper's tripartite-graph consequences.","marker":"[6]"},{"why":"Supplies the majorization theorem used inside Lemma 3.1 for the weighted-triangle characterization.","marker":"[7]"},{"why":"Provides the packing lemma that removes almost all leftover edges from an (F,b,delta,epsilon)-graph, a core step in Theorem 1.3.","marker":"[8]"},{"why":"Supplies the approximate-packing method whose framework the proof of Theorem 1.3 follows.","marker":"[12]"}],"fun_headline_variants":["Sharp bound for odd cycle decomposition","Odd cycle splits: degree cutoff near 1/2","Tight threshold for decomposing into odd cycles","Cycle decomposition threshold for odd lengths"],"cache_read_input_tokens":18688,"weakest_assumption_plain":"The proof depends on a previously established guarantee that, for cycles, a decomposition that leaves only a tiny fraction of edges unused can always be upgraded to a true decomposition using no extra edges. If that guarantee failed for some odd length, the approximate decompositions produced here could not be converted into exact ones and the main theorem would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Sharp bound for odd cycle decomposition","Odd cycle splits: degree cutoff near 1/2","Tight threshold for decomposing into odd cycles","Cycle decomposition threshold for odd lengths"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001251,"raw_usage":{"total_tokens":5111,"prompt_tokens":912,"completion_tokens":4199,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":528,"completion_tokens_details":{"reasoning_tokens":4144}},"tokens_in":528,"tokens_out":4199,"duration_ms":27078,"temperature":1.0,"reasoning_tokens":4144,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:22:57.707550+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct, for some odd $\\ell \\geq 5$, a $C_\\ell$-divisible $n$-vertex graph with minimum degree at least $(\\frac{1}{2}+\\frac{1}{2\\ell-4}+\\varepsilon)n$ and no $C_\\ell$-decomposition; that would directly refute the main theorem. A cleaner test of the proof chain would be to exhibit a graph with an $\\eta$-approximate $C_\\ell$-decomposition for every $\\eta>0$ but no exact $C_\\ell$-decomposition, since the exactness step assumes no such graph exists.","supporting_citations":[{"cited_title":"Barber, D","cited_arxiv_id":null,"evidence_quote":"Supplies the equality of exact and approximate cycle decomposition thresholds, the step that turns the paper's approximate decomposition into an exact one."},{"cited_title":"Birkhoff, Tres observaciones sobre el algebra lineal, Univ","cited_arxiv_id":null,"evidence_quote":"Provides the doubly stochastic decomposition theorem used inside Lemma 3.1 for the weighted-triangle characterization."},{"cited_title":"Gir˜ ao, B","cited_arxiv_id":null,"evidence_quote":"Supplies the lemma that splits an epsilon-regular bipartite graph into smaller regular pieces, used in the proof of the approximate-decomposition lemma."},{"cited_title":"Glock, D","cited_arxiv_id":null,"evidence_quote":"Provides the general decomposition-threshold theorem and the 3/4 cap used for the paper's tripartite-graph consequences."},{"cited_title":"Hardy, J.E","cited_arxiv_id":null,"evidence_quote":"Supplies the majorization theorem used inside Lemma 3.1 for the weighted-triangle characterization."},{"cited_title":"Haxell and V","cited_arxiv_id":null,"evidence_quote":"Provides the packing lemma that removes almost all leftover edges from an (F,b,delta,epsilon)-graph, a core step in Theorem 1.3."},{"cited_title":"Yuster, Integer and fractional packing of families of graph s, Random Structures Algo- rithms 26 (2005) 110–118","cited_arxiv_id":null,"evidence_quote":"Supplies the approximate-packing method whose framework the proof of Theorem 1.3 follows."}],"review_version":1}