Progress towards Nash-Williams' Conjecture on Triangle Decompositions

Luke Postle; Michelle Delcourt

REVIEW 2 major objections 4 minor 1 cited by

Progress towards Nash-Williams' Conjecture on Triangle Decompositions

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every graph with minimum degree above 0.82733n has a fractional triangle decomposition.

desk verdict Strong new bound on fractional triangle decompositions with a novel delegation/cancellation method; proof has two localized sign slips in the optimization chain that are repairable but must be fixed. read the letter →

arxiv 1909.00514 v3 pith:SIVRXZO2 submitted 2019-09-02 math.CO

Michelle Delcourt , Luke Postle This is my paper · ORCID

classification math.CO MSC 05C7005C3590C30

keywords fractionaltriangledecompositionminimumdegreethresholdedge-gadgetsdelegationcancellationnonlinearoptimization3-chromaticgraphs

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

The paper tackles the 1970 conjecture that every sufficiently large triangle-divisible graph with minimum degree at least $3n/4$ can have its edges split into edge-disjoint triangles. Because recent work shows the fractional version controls the integral version, the paper proves that every $n$-vertex graph with minimum degree at least $((7+\sqrt{21})/14)n \approx 0.82733n$ admits a fractional triangle decomposition. This improves the previous hand-verifiable bound of $0.9n$ and, through a known reduction, gives genuine triangle decompositions for triangle-divisible graphs above this threshold plus any positive epsilon. A sympathetic reader should care because the gap to the conjectured $3/4$ constant is now much smaller, and the same constant bounds decomposition thresholds for all 3-chromatic graphs.

What carries the argument

The argument is carried by a weight-distribution scheme built from edge-gadgets. An edge-gadget is a local assignment of weights to the triangles inside a $K_5$ that changes the total weight of exactly one chosen edge while leaving all other edges unchanged. The paper delegates each edge's demand of $1$ uniformly to the triangles containing it, then through the $K_4$'s containing each triangle, then through the $K_5$'s containing each $K_4$; the resulting triangle weighting automatically has edge sums equal to $1$. The remaining work is to prove this weighting is nonnegative, which is done by rewriting the weight of each ordered triangle as a sum of 'cancelling' pairs of gadget contributions and then solving a maximization program. A symmetrization step reduces the program to ten variables, ramps make the terms nonnegative, and successive monotonicity reductions bring it down to a one-variable bound whose maximum is $3d(1-d)/(1-2d)^2$; requiring this to be at most $1$ fixes $d$ at the stated value.

What would settle it

Evaluate the published objective $\widehat{W}_9(a,b)$ on a fine grid over $0\le a,b\le d$ for $d=(7-\sqrt{21})/14$. If any value exceeds $1$, the claimed chain of inequalities $\mathrm{OPT}(P1)\le \mathrm{OPT}(P10)=1$ is false, so the proof as printed cannot establish Theorem 1.4.

Watch

Extended reading notes

Core claim

The paper's central assertion is Theorem 1.4: if $G$ is a graph on $n$ vertices with minimum degree $\delta(G) \ge ((7+\sqrt{21})/14)n$, then $G$ admits a fractional $K_3$-decomposition—an assignment of nonnegative weights to triangles such that every edge gets total weight $1$. Equivalently, writing $d=(7-\sqrt{21})/14 \approx 0.17267$, the theorem holds whenever $\delta(G) \ge (1-d)n$, and the constant $d$ is the root of $7d^2-7d+1=0$ in $[0,1/4)$. Combined with the iterative-absorption results cited in the paper, this yields that for every $\varepsilon>0$, every sufficiently large $K_3$-divisible graph on $n$ vertices with minimum degree at least $((7+\sqrt{21})/14+\varepsilon)n$ admits an actual $K_3$-decomposition, and similarly for any 3-chromatic forbidden graph $F$.

Load-bearing premise

The load-bearing premise is that the long chain of optimization reductions in Section 5 is correct, but as printed it is not: Claim 5.15.2 miscomputes the derivative of $H(s,t)$ and the final step of Lemma 5.17 asserts $1-5d\le 0$ for $d\in[0,1/5]$, which is false, so the claimed upper bound on the program is not rigorously established until those calculations are repaired.

Editorial extensions

If this is right

For every $\varepsilon>0$, every sufficiently large $K_3$-divisible graph with $\delta(G)\ge ((7+\sqrt{21})/14+\varepsilon)n$ has a triangle decomposition, the paper's headline progress on the 1970 conjecture.
The same degree threshold controls decompositions into any 3-chromatic graph $F$: every sufficiently large $F$-divisible graph above $(0.82733+\varepsilon)n$ admits an $F$-decomposition.
The threshold also yields packing corollaries: collections of cycles or 2-regular $n$-vertex graphs pack into hosts of the same high minimum degree as long as their total edge count is bounded away from that of the host.
The constant is not arbitrary: it is the value at which $3d(1-d)/(1-2d)^2=1$, the exact point where the optimization program's upper bound reaches $1$.

Reading between the lines

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

Beyond the paper: if the two sign errors are repaired, the same delegation-cancellation machinery yields the stated constant, but the paper's own footnote suggests that adding an averaging constraint on the reduced variable could lower the threshold further, toward about $0.813n$.
Beyond the paper: the paper's observation that its weighting fails on near-extremal examples such as clique blow-ups of $C_4$ and independent blow-ups of $K_4$ indicates that closing the gap to the conjectured $3/4$ constant will require a new weighting or delegation rule rather than sharper optimization of the current one.
Beyond the paper: a quick numerical check of the published one- and two-variable programs is a testable way to see whether the claimed bound survives the sign corrections.

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

Quick read on 1909.00514. The headline is real: Delcourt and Postle lower the fractional triangle decomposition threshold from 0.9 to 0.82733, beating the independent 0.852 from Dukes-Horsley, and they do it with a hand-verifiable argument rather than computer assistance. The delegation/cancellation scheme is a genuinely new mechanism, and the reduction to a 10-variable nonlinear program is the kind of thing that advances the toolbox for these problems, even if the final optimization is tedious. The corollaries for F-decompositions and cycle packings are straightforward consequences and look sound.

The proof of Theorem 1.4 rests on Theorem 3.12, which is reduced to solving an optimization chain. Most of the chain is careful and checks out: Propositions 3.11 and 4.7 are clean, and the symmetrization steps in Section 4 are a nice way to collapse many variables to ten. The soft spot is Section 5. As written, Claim 5.15.2 miscomputes the derivative of H(s,t); the sign of the 2/(1-d-s) term is reversed, which inverts the monotonicity conclusion the claim needs. Lemma 5.17 has the same flavor: it says E(b) is decreasing and therefore E(b) >= E(0), when the correct inference is <=, and it follows this with 'E(0) <= 1-5d <= 0' — but 1-5d is nonnegative on the stated interval. The intended inequalities appear to be true (the corrected derivative is negative, and the correct E(0) value is negative for d = (7-√21)/14), so these are repairable sign slips, not a structural hole. But they are load-bearing: they are the steps that drop the program from P9 to P10 and evaluate the final bound. A referee should ask for these to be redone carefully.

One smaller issue: the abstract overclaims by dropping the epsilon in the integral corollary. The body (Corollary 1.5) correctly states δ >= (7+√21)/14 + ε for triangle decompositions; the abstract says 0.82733n without epsilon. That should be fixed.

Overall: the main theorem is likely correct and the technique is worth knowing. The paper deserves a serious refereeing, with the Section 5 calculations checked line by line. If the authors supply a corrected version of those two lemmas, I would be comfortable taking the result as established.

Referee Report

2 major / 4 minor

Summary. This paper addresses the fractional version of Nash-Williams' triangle decomposition conjecture. It proves (Theorem 1.4) that every graph on n vertices with minimum degree at least ((7+sqrt(21))/14)n ~ 0.82733n has a fractional K3-decomposition. The proof constructs an explicit triangle weighting w_G by delegating unit demand from each edge through triangles, K4s, and K5s using edge-gadgets; non-negativity of w_G is reformulated as the inequality w_{G,1}(O) <= 1 and then as a sequence of optimization problems (P1) through (P10). Solving (P10) yields the bound 3d(1-d)/(1-2d)^2 <= 1 for d=(7-sqrt(21))/14, which is exactly the stated minimum degree. The paper then uses known iterative-absorption and packing results to derive corollaries for integral triangle decompositions and for packing 2-regular graphs.

Significance. The claimed threshold would be a substantial improvement over the previous best bound delta*_{K3} <= 0.9 (Dross) and a significant step toward the conjectured 0.75 threshold. The construction and main reduction are explicit and hand-checkable, without computer-assisted case analysis (unlike the independent work of Dukes-Horsley), and the delegation/cancellation ideas appear genuinely novel. The paper also gives corollaries for integral decompositions and approximate packings. However, the final monotonicity reductions in Section 5 contain two sign errors that break the chain of inequalities as printed; because these steps are load-bearing for Corollary 5.18 and Theorem 3.12, the manuscript is not yet rigorous in its present form. The errors look localized and numerically repairable, but they must be corrected before the main theorem is established.

major comments (2)

[Section 5.4, Claim 5.15.2] The displayed derivative of H(s,t) has the wrong sign on the 2/(1-d-s) term. The logarithmic derivative is dH/ds = H(s,t)(-2/(1-d-s) - 1/(1-2d-s) + 1/(1-2d-s-t)) = H(s,t)(-2/(1-d-s) + t/((1-2d-s)(1-2d-s-t))), which is negative on the relevant domain for the value of d in question. Thus H is decreasing in s, giving H(a,b) <= H(0,b), exactly the inequality Claim 5.15.2 needs. As printed, the calculation uses +2/(1-d-s) and concludes dH/ds >= 0, which would imply the reverse inequality. The claim appears true, but the proof is invalid as written.
[Section 5.5, Lemma 5.17] The proof has two sign errors. From E'(b) <= 0 it concludes E(b) >= E(0); a decreasing function satisfies E(b) <= E(0). It also states E(0) <= 1-5d <= 0 for d in [0,1/5], but 1-5d is positive for the actual d=(7-sqrt(21))/14 ~ 0.17267. Fortunately E(0) = -1+5d-13d^2-12d^3 is negative at this value, so combining the corrected monotonicity direction with a direct bound on E(0) recovers E(b) <= 0. As printed, however, the proof of G(b) <= G(0) is not rigorous, and this step is necessary for Corollary 5.18.

minor comments (4)

[Section 5.3, proof of Claim 5.13.2] The proof states "Since a >= d", but the domain has a in [0,d]; the subsequent inequality is the one that follows from a <= d.
[Section 5.4, after Lemma 5.15] The text says "we may replace (P8) with a new program (P9)", but the new program introduced immediately afterwards is labelled (P10); this should say "replace (P9) with (P10)".
[Section 5.1, introduction of (P4)] The text says "whose minimum is at most that of (P3)"; since the objective is being replaced by an upper bound, the intended statement is about the maximum.
[Abstract] The abstract's final sentence omits the epsilon-slack that appears in Corollary 1.5; as written, "minimum degree at least 0.82733n" is not the precise statement of the integral decomposition result.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.4 is derived from an explicit construction of the weighting w_G and a reduction to an optimization program solved in closed form; the target statement is neither assumed nor fitted.

full rationale

The paper's central claim is Theorem 1.4, which states that every graph with minimum degree at least ((7+sqrt(21))/14)n has a fractional K3-decomposition. The derivation is self-contained: Definition 3.10 explicitly constructs the triangle weighting w_G, Proposition 3.11 proves that every edge receives total weight 1, and Theorem 3.12 reduces the remaining task to proving non-negativity of w_G. That non-negativity is reformulated as the bound w_{G,1}(O) <= 1 in Theorem 3.17, and Section 4 converts this into the optimization program (P1). Section 5 then solves the program through an explicit chain of reductions, ending with OPT(P1) <= OPT(P10) = 3d(1-d)/(1-2d)^2, and the chosen value d = (7-sqrt(21))/14 is exactly the root of 7d^2 - 7d + 1 = 0 that makes this expression at most 1. Thus the final constant emerges from an inequality derived in the paper, not from a parameter fitted to the conclusion. The edge-gadget used in the proof is cited to Barber, Kuhn, Lo, Montgomery, and Osthus, but it is not a load-bearing self-citation: the paper reproduces the definition (Definition 3.3) and proves the needed one-edge property (Proposition 3.4), so the gadget is a verified tool rather than an assumed result. There are also no uniqueness theorems imported from the authors' earlier work, and no renaming of a known empirical pattern is presented as an explanation. The printed sign errors in Claim 5.15.2 and Lemma 5.17 flagged by the skeptic are genuine correctness concerns about monotonicity steps in the optimization chain, but a gap or error in a written proof is not circularity: the intended argument does not assume Theorem 1.4 or any equivalent of it. Finally, the limitations acknowledged in Section 6, such as the belief that w_G may not prove the asymptotic conjecture and the suggestion that additional averaging bounds could improve d, are honest statements about scope and possible future work, not admissions that the result was built into the assumptions. Therefore the paper's derivation chain is not circular.

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

The central claim rests on a new weighting scheme and a long optimization proof. No free parameters are fitted to data: d is the root of an inequality derived in the proof. The main imported assumptions are the fractional-to-integral lifting theorems from prior work. No new particles, forces, or exotic entities are introduced.

assumptions (3)

domain assumption Theorem 1.2 (Barber, Kuhn, Lo, and Osthus [2]; Glock, Kuhn, Lo, Montgomery, and Osthus [9])
The fractional-to-integral lifting theorem is imported from prior work. Corollaries 1.5-1.8 depend on it and inherit its epsilon slack.
standard math Edge-gadget weight function psi_K,e satisfies Proposition 3.4, giving edge sum 1 on e and 0 elsewhere.
Proven by direct check in the paper; used to show w_G gives weight 1 on each edge.
standard math Common-neighbor density Nhat is monotone (Prop 4.2) and supermodular (Prop 4.3), and Nhat(S) > 1 - |S|/4 for |S| <= 4 (Prop 4.4).
Proven in the paper; these bounds define the constraints of the optimization program P1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Progress towards Nash-Williams' Conjecture on Triangle Decompositions." pith.science (2026). https://pith.science/paper/SIVRXZO2

@misc{pith2026190900514,
  author       = {Pith},
  title        = {Pith review of: Progress towards Nash-Williams' Conjecture on Triangle Decompositions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SIVRXZO2}},
  note         = {Machine review of arXiv:1909.00514}
}

abstract

Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large, triangle divisible graph on $n$ vertices with minimum degree at least $0.75 n$ admits a triangle decomposition. In the light of recent results, the fractional version of this problem is of central importance. A fractional triangle decomposition is an assignment of non-negative weights to each triangle in a graph such that the sum of the weights along each edge is precisely 1. We show that for any graph on $n$ vertices with minimum degree at least $0.827327 n$ admits a fractional triangle decomposition. Combined with results of Barber, K\"{u}hn, Lo, and Osthus, this implies that for every sufficiently large triangle divisible graph on $n$ vertices with minimum degree at least $0.82733 n$ admits a triangle decomposition.

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

On the minimum degree required for a triangle decomposition
math.CO 2019-08 conditional novelty 6.0 of 10

For large n, every n-vertex graph of minimum degree at least 0.852n has a fractional decomposition into triangles, and every K3-divisible such graph has an exact triangle decomposition above that threshold.

Reference graph

Works this paper leans on

18 extracted references · 16 canonical work pages · cited by 1 Pith paper

[1]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, R. Montgomery, and D. Osthus, Fr actional clique decom- positions of dense graphs and hypergraphs, Journal of Combinatorial Theory Series B , 127, 2017, 148–186

work page 2017
[2]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, and D. Osthus, Edge-decompositio ns of graphs with high minimum degree, Advances in Mathematics , 288, 2016, 337–385

work page 2016
[3]

Barber, S

B. Barber, S. Glock, D. K¨ uhn, A. Lo, R. Montgomery, and D. Os thus, Minimalist designs, Random Structures and Algorithms , 57, 2020, 47–63

work page 2020
[4]

Condon, J

P. Condon, J. Kim, D. K¨ uhn, and D. Osthus, A bandwidth theore m for approximate decompositions, Proceedings London Mathematical Society, 118, 2019, 1393–1449

work page 2019
[5]

Dross, Fractional triangle decompositions in graphs with large minimum degree, SIAM Journal on Discrete Mathematics , 30(1), 2015, 36–42

F. Dross, Fractional triangle decompositions in graphs with large minimum degree, SIAM Journal on Discrete Mathematics , 30(1), 2015, 36–42

work page 2015
[6]

Dukes, Rational decomposition of dense hypergraphs and so me related eigenvalue estimates, Linear Algebra and Its Applications , 436(9), 2012, 3736–3746

P. Dukes, Rational decomposition of dense hypergraphs and so me related eigenvalue estimates, Linear Algebra and Its Applications , 436(9), 2012, 3736–3746

work page 2012
[7]

Dukes and D

P.J. Dukes and D. Horsley, On the minimum degree required for a tr iangle decomposi- tion, SIAM Journal on Discrete Mathematics, 2020, 597–610

work page 2020
[8]

Garaschuk

K. Garaschuk. Linear methods for rational triangle decomposit ions, PhD thesis, Uni- versity of Victoria, 2014

work page 2014

Show all 18 references

[9]

Glock, D

S. Glock, D. K¨ uhn, A. Lo, R. Montgomery, and D. Osthus, On th e decomposition threshold of a given graph, Journal of Combinatorial Theory Series B , 139, 2019, 47– 127

2019
[10]

Glock, D

S. Glock, D. K¨ uhn, A. Lo, and D. Osthus, The existence of des igns via iterative ab- sorption: Hypergraph F-designs for arbitrary F, To appear in Memoirs of the American Mathematical Society, https://arxiv.org/pdf/1611.06827.pdf

arXiv
[11]

Glock, D

S. Glock, D. K¨ uhn, and D. Osthus, Extremal Aspects of Grap h and Hypergraph De- composition Problems, Submitted, https://arxiv.org/pdf/2008.00 926.pdf

2008
[12]

Haxell and V

P.E. Haxell and V. R¨ odl, Integer and fractional packings in den se graphs, Combinator- ica, 21(1): 2001, 13–38

2001
[13]

Keevash, The existence of designs, Submitted, https://ar xiv.org/pdf/1401.3665.pdf

P. Keevash, The existence of designs, Submitted, https://ar xiv.org/pdf/1401.3665.pdf. 29

arXiv
[14]

Kirkman, On a problem in combinatorics, Cambridge Dublin Mathematical Jour- nal, 2, 1847, 191–204

T.P. Kirkman, On a problem in combinatorics, Cambridge Dublin Mathematical Jour- nal, 2, 1847, 191–204
[15]

Montgomery, Fractional Clique Decompositions of Dense Gra phs, Random Structures and Algorithms , 54(4), 2019, 779–796

R. Montgomery, Fractional Clique Decompositions of Dense Gra phs, Random Structures and Algorithms , 54(4), 2019, 779–796

2019
[16]

Nash-Williams, An unsolved problem concerning decompositio n of graphs into triangles, Combinatorial Theory and its Applications , III, 1970, 1179–1183

C.S.J. Nash-Williams, An unsolved problem concerning decompositio n of graphs into triangles, Combinatorial Theory and its Applications , III, 1970, 1179–1183

1970
[17]

Wilson, Decomposition of complete graphs into subgraphs iso morphic to a given graph, Congressus Numerantium XV , 1975, 647–659

R.M. Wilson, Decomposition of complete graphs into subgraphs iso morphic to a given graph, Congressus Numerantium XV , 1975, 647–659

1975
[18]

Yuster, Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions, Journal of Combinatorial Theory Series B , 95, 2005, 1–11

R. Yuster, Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions, Journal of Combinatorial Theory Series B , 95, 2005, 1–11. 30

2005

Pith tools

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

[1] [1]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, R. Montgomery, and D. Osthus, Fr actional clique decom- positions of dense graphs and hypergraphs, Journal of Combinatorial Theory Series B , 127, 2017, 148–186

work page 2017

[2] [2]

Barber, D

B. Barber, D. K¨ uhn, A. Lo, and D. Osthus, Edge-decompositio ns of graphs with high minimum degree, Advances in Mathematics , 288, 2016, 337–385

work page 2016

[3] [3]

Barber, S

B. Barber, S. Glock, D. K¨ uhn, A. Lo, R. Montgomery, and D. Os thus, Minimalist designs, Random Structures and Algorithms , 57, 2020, 47–63

work page 2020

[4] [4]

Condon, J

P. Condon, J. Kim, D. K¨ uhn, and D. Osthus, A bandwidth theore m for approximate decompositions, Proceedings London Mathematical Society, 118, 2019, 1393–1449

work page 2019

[5] [5]

Dross, Fractional triangle decompositions in graphs with large minimum degree, SIAM Journal on Discrete Mathematics , 30(1), 2015, 36–42

F. Dross, Fractional triangle decompositions in graphs with large minimum degree, SIAM Journal on Discrete Mathematics , 30(1), 2015, 36–42

work page 2015

[6] [6]

Dukes, Rational decomposition of dense hypergraphs and so me related eigenvalue estimates, Linear Algebra and Its Applications , 436(9), 2012, 3736–3746

P. Dukes, Rational decomposition of dense hypergraphs and so me related eigenvalue estimates, Linear Algebra and Its Applications , 436(9), 2012, 3736–3746

work page 2012

[7] [7]

Dukes and D

P.J. Dukes and D. Horsley, On the minimum degree required for a tr iangle decomposi- tion, SIAM Journal on Discrete Mathematics, 2020, 597–610

work page 2020

[8] [8]

Garaschuk

K. Garaschuk. Linear methods for rational triangle decomposit ions, PhD thesis, Uni- versity of Victoria, 2014

work page 2014