On decomposition thresholds for odd-length cycles and other tripartite graphs

Barbara Maenhaut; Daniel Horsley; Darryn Bryant; Peter Dukes; Richard Montgomery

REVIEW 1 major objections 3 minor 1 cited by

On decomposition thresholds for odd-length cycles and other tripartite graphs

T0 review · 1 major / 3 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 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.

desk verdict 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. read the letter →

arxiv 2411.17232 v3 pith:DGXEBUSO submitted 2024-11-26 math.CO

Darryn Bryant , Peter Dukes , Daniel Horsley , Barbara Maenhaut , Richard Montgomery This is my paper · ORCID

classification math.CO MSC 05C7005C3805C35

keywords graphdecompositioncyclethresholdminimumdegreefractionalweightedtrianglesregularitylemmatripartitegraphs

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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. 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.

The 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.

Overall, 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.

Referee Report

1 major / 3 minor

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^-.

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 (1)

[Section 4, Lemma 4.2 (display before Eq. (5))] 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.

minor comments (3)

[Lemma 4.3] 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.
[Corollary 5.4] 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 4, Lemma 4.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central derivation is self-contained; imported theorems are independent prior results, not fitted or definitional.

full rationale

Walking the claimed derivation chain: Theorem 1.1 is obtained as δ_{C_ℓ} ≤ δ^{0+}_{C_ℓ} (Theorem 1.4, imported from [1]) plus the paper's own Theorems 1.2 and 1.3, which give δ^{0+}_{C_ℓ} ≤ 1/2 + 1/(2ℓ−4). Theorem 1.2 is proved from Theorem 3.2 and Lemmas 3.4–3.5, all proved in the paper from the majorization/Birkhoff lemma (Lemma 3.1); no parameter is fitted to the target threshold, and the bound is explicitly not claimed optimal. Theorem 1.3 is proved from Lemma 4.2, which constructs (F,b,≥δ0,ε)-graph packings from a fractional decomposition of the condensation W, using Lemma 4.3 as a genuine combinatorial construction (the q-blow-up of W has a fractional F-decomposition) rather than as an assumption of the conclusion. The only overlapping-author citation, Theorem 5.1 from [6] (Glock–Kühn–Lo–Montgomery–Osthus), is an external parameter-free theorem about approximate-to-exact decomposition thresholds; it does not assume the present results, so under the review rules it is independent support and does not raise the circularity score. The lower bounds in Corollary 2.2 and Section 5 are self-contained constructions. No fitted parameter is relabelled as a prediction, and no uniqueness theorem or ansatz is imported from the authors' prior work to rule out alternatives. The reviewer-flagged inequality in the proof of Lemma 4.2 is a possible correctness gap, but a false intermediate algebraic inequality is not a circularity; it does not make the conclusion equivalent to an input.

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

The central claim rests on several published theorems and standard tools, all clearly cited. No new entities or fitted parameters are introduced. The proof of the main theorem is not fully self-contained because it imports the iterative absorption equality δ_{Cℓ} = δ^{0+}_{Cℓ}.

assumptions (7)

domain assumption Theorem 1.4 of Barber, Kühn, Lo and Osthus [1]: δ_{Cℓ} = δ^{0+}_{Cℓ} for every ℓ ≥ 3.
Imported without proof; essential to convert approximate Cℓ-decompositions into exact ones in the proof of Theorem 1.1.
domain assumption Theorem 5.1 of Glock, Kühn, Lo, Montgomery and Osthus [6]: δ_F ≤ max{δ^{0+}_F, 1 − 1/(χ+1)} for any graph F.
Imported without proof; used for the tripartite bounds in Section 5.
domain assumption Lemma 4.1 from Haxell and Rödl [8]: dense regular blow-up of F has an F-packing with small leftover.
Imported without proof; used in the proof of Theorem 1.3.
standard math Lemma 4.4 (regularity lemma): any large graph has an equitable partition into a bounded number of classes with few irregular pairs.
Standard form of Szemerédi's regularity lemma.
domain assumption Lemma 4.5 from Girão, Granet, Kühn and Osthus [5]: a regular bipartite graph can be split into subgraphs with prescribed regular densities.
Imported without proof; used to distribute fractional F-copies onto edge-disjoint regular subgraphs.
domain assumption Lemma 4.6 from Haxell and Rödl [8]: a fractional F-decomposition of a weighted graph with edge weights at most 1 can be approximated by one with all copy edge weights bounded below.
Imported without proof; provides the uniform weight lower bound δ0 in Lemma 4.2.
standard math Lemma 3.1, combining Birkhoff's theorem and Hardy-Littlewood-Pólya majorization: sorted vectors with majorization are permuted-vector convex combinations.
Used in the proof of Theorem 3.2 to construct fractional decompositions of weighted triangles.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On decomposition thresholds for odd-length cycles and other tripartite graphs." pith.science (2026). https://pith.science/paper/DGXEBUSO

@misc{pith2026241117232,
  author       = {Pith},
  title        = {Pith review of: On decomposition thresholds for odd-length cycles and other tripartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DGXEBUSO}},
  note         = {Machine review of arXiv:2411.17232}
}

abstract

An (edge) decomposition of a graph $G$ is a set of subgraphs of $G$ whose edge sets partition the edge set of $G$. Here we show, for each odd $\ell \geq 5$, that any graph $G$ of sufficiently large order $n$ with minimum degree at least $(\frac{1}{2}+\frac{1}{2\ell-4}+o(1))n$ has a decomposition into $\ell$-cycles if and only if $\ell$ divides $|E(G)|$ and each vertex of $G$ has even degree. This threshold cannot be improved beyond $\frac{1}{2}+\frac{1}{2\ell-2}$. It was previously shown that the thresholds approach $\frac{1}{2}$ as $\ell$ becomes large, but our thresholds do so significantly more rapidly. Our methods can be applied to tripartite graphs more generally and we also obtain some bounds for decomposition thresholds of other tripartite graphs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Determining decomposition thresholds for long odd cycles
math.CO 2026-06 unverdicted novelty 8.0 of 10

Proves δ_{C_ℓ} = ℓ/(2ℓ-2) for odd ℓ ≥ 73.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

Barber, D

B. Barber, D. K¨ uhn, A. Lo and D. Osthus, Edge decompositions of graphs with high minimum degree, Adv. Math. 288 (2016), 337–385

work page 2016
[6]

Glock, D

S. Glock, D. K¨ uhn, A. Lo, R. Montgomery and D. Osthus, On the decomposition threshold of a given graph, J. Combin. Theory Ser. B 139 (2019), 47–127

work page 2019
[2]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, D. Osthus and A. Taylor, Clique decompositions of multipartite graphs and completion of latin squares, J. Combin, Theory Ser. A 15 1 (2017), 146–201

work page 2017
[3]

Birkhoﬀ, Tres observaciones sobre el algebra lineal, Univ

G. Birkhoﬀ, Tres observaciones sobre el algebra lineal, Univ. Nac . Tucum´ an Rev. Ser. A 5 (1946) 147–151

work page 1946
[4]

Delcourt and L

M. Delcourt and L. Postle, Progress towards Nash-Williams’ conj ecture on triangle decom- positions, J. Combin. Theory Ser. B 146 (2021), 382–416

work page 2021
[5]

Gir˜ ao, B

A. Gir˜ ao, B. Granet, D. K¨ uhn and D. Osthus, Path and cycle de compositions of dense graphs, J. Lond. Math. Soc. 104 (2021), 1085–1134. 14

work page 2021
[7]

Hardy, J.E

G.H. Hardy, J.E. Littlewood and G. P´ olya, Some simple inequalities sa tisﬁed by convex functions, Messenger Math. 58 (1929), 145–152

work page 1929
[8]

Haxell and V

P. Haxell and V. R¨ odl, Integer and fractional packings in dense graphs, Combinatorica 21 (2001), 13–38

work page 2001

Show all 12 references

[9]

Joos and M

F. Joos and M. K¨ uhn, Fractional cycle decompositions in hypergraphs, Random Structures Algorithms 61 (2022), 425–443

2022
[10]

R¨ uschendorf, Ordering of distributions and rearrangement of functions, Annals of Prob- ability 9 (1981), 276–283

L. R¨ uschendorf, Ordering of distributions and rearrangement of functions, Annals of Prob- ability 9 (1981), 276–283

1981
[11]

Taylor, On the exact decomposition threshold for even cycle s, J

A. Taylor, On the exact decomposition threshold for even cycle s, J. Graph Theory 90 (2019), 231–266

2019
[12]

Yuster, Integer and fractional packing of families of graph s, Random Structures Algo- rithms 26 (2005) 110–118

R. Yuster, Integer and fractional packing of families of graph s, Random Structures Algo- rithms 26 (2005) 110–118. 15

2005

Pith tools

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

[1] [1]

Barber, D

B. Barber, D. K¨ uhn, A. Lo and D. Osthus, Edge decompositions of graphs with high minimum degree, Adv. Math. 288 (2016), 337–385

work page 2016

[2] [6]

Glock, D

S. Glock, D. K¨ uhn, A. Lo, R. Montgomery and D. Osthus, On the decomposition threshold of a given graph, J. Combin. Theory Ser. B 139 (2019), 47–127

work page 2019

[3] [2]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, D. Osthus and A. Taylor, Clique decompositions of multipartite graphs and completion of latin squares, J. Combin, Theory Ser. A 15 1 (2017), 146–201

work page 2017

[4] [3]

Birkhoﬀ, Tres observaciones sobre el algebra lineal, Univ

G. Birkhoﬀ, Tres observaciones sobre el algebra lineal, Univ. Nac . Tucum´ an Rev. Ser. A 5 (1946) 147–151

work page 1946

[5] [4]

Delcourt and L

M. Delcourt and L. Postle, Progress towards Nash-Williams’ conj ecture on triangle decom- positions, J. Combin. Theory Ser. B 146 (2021), 382–416

work page 2021

[6] [5]

Gir˜ ao, B

A. Gir˜ ao, B. Granet, D. K¨ uhn and D. Osthus, Path and cycle de compositions of dense graphs, J. Lond. Math. Soc. 104 (2021), 1085–1134. 14

work page 2021

[7] [7]

Hardy, J.E

G.H. Hardy, J.E. Littlewood and G. P´ olya, Some simple inequalities sa tisﬁed by convex functions, Messenger Math. 58 (1929), 145–152

work page 1929

[8] [8]

Haxell and V

P. Haxell and V. R¨ odl, Integer and fractional packings in dense graphs, Combinatorica 21 (2001), 13–38

work page 2001