On the minimum degree required for a triangle decomposition

Daniel Horsley; Peter J. Dukes

REVIEW 3 major objections 4 minor 8 references

On the minimum degree required for a triangle decomposition

T0 review · 3 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 This paper proves that every sufficiently large graph with minimum degree at least 0.852n has a fractional K3-decomposition.

desk verdict A real improvement in the triangle-decomposition threshold, with an elegant middle-range analysis—but the keystone Lemma 18 leans on an unaudited Mathematica grid computation and should not be accepted until the code is released. read the letter →

arxiv 1908.11076 v2 pith:X2PDMDX3 submitted 2019-08-29 math.CO

Peter J. Dukes , Daniel Horsley This is my paper · ORCID

classification math.CO MSC 05C7005C35

keywords fractionaltriangledecompositionminimumdegreethresholdK3-decompositionNash-Williamsconjecturerootedpairswitchflownetworkcomputer-assistedproofdensegraphs

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 establishes a new sufficient condition for decomposing the edges of a dense graph into triangles in a fractional sense: every sufficiently large graph on n vertices with minimum degree at least 0.852n can have nonnegative weights assigned to its triangles so that each edge receives total weight 1. This improves the previous threshold 0.9n, obtained by the method this work refines, and it is a step toward the conjecture that K3-divisible graphs of minimum degree at least 3n/4 decompose into edge-disjoint triangles. The proof works by starting with uniform triangle weights and shifting weight along copies of K4, reducing the task to a min-cut inequality about edge subsets. The hardest parameter range is handled by a computer-assisted verification over a finite grid, so the result is conditional on that verification being correct. A transfer theorem then converts the fractional result into a genuine triangle decomposition for every sufficiently large K3-divisible graph with minimum degree above 0.852n (and, by a continuity argument, at 0.852n).

What carries the argument

The engine is a local switch on a rooted pair: if {ab,cd} is a pair of non-adjacent edges whose four endpoints induce a K4, one can transfer ε of triangle weight from ab to cd by adjusting the four triangles containing those two edges. Repeated switches are organized through an auxiliary flow network whose arcs are rooted pairs; max-flow min-cut then shows a fractional decomposition exists exactly when, for every edge subset A with t_A above average, the number κ_A of rooted pairs separated by A is at least λ_A = (3/(2|A|⌈(1−δ)n−1⌉))(t_A−t_av). The bulk of the paper bounds κ_A from below by convexity estimates, with the middle range reduced by Lemma 17 to a step function f† supported on three levels e0,e1,e2, giving a piecewise function g(α,t_A,m) that must dominate k(α,t_A,m). That dominance is verified by a finite-grid computation with subinterval width 0.00001 plus gradient bounds.

What would settle it

An independent interval-arithmetic or exact rational evaluation of the inequality g(α,τ,μ)>k(α,τ,μ) on the box Ξ={0.446≤α≤0.692, 0.761≤τ≤0.814, 0.852≤μ≤0.863}, at a finer scale than h=0.00001, would either confirm or expose a failure in Lemma 18; a single point where the inequality fails would remove the support for the middle case of Theorem 2.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is Theorem 2: there exists an integer N such that every graph of order n>N with minimum degree at least 0.852n has a fractional K3-decomposition, where a fractional K3-decomposition assigns nonnegative weights to all triangles so that every edge is contained in triangles of total weight 1. The proof uses δ=0.148 and shows, for every subset A of edges with average triangle count t_A above the global average, that the number κ_A of rooted pairs separated by A is at least λ_A, the quantity required by the flow-network criterion. The difficult case, 0.446<α<0.692 and t_A>0.7619n, is dispatched by a computer-assisted check over the parameter box 0.446≤α≤0.692, 0.761≤τ≤0.814, 0.852≤μ≤0.863. From Theorem 2, the transfer theorem gives Theorem 3: for every ε>0, all sufficiently large K3-divisible graphs with minimum degree at least (0.852+ε)n have genuine triangle decompositions; the paper further argues that ε can be taken to be 0.

Load-bearing premise

The proof of the middle case rests on a computer-assisted grid verification that the paper describes but does not reproduce; if that verification is wrong or incomplete, the claimed 0.852 threshold is not established.

Editorial extensions

If this is right

A minimum degree of 0.852n becomes the best known sufficient condition for fractional triangle decompositions in large graphs.
Every sufficiently large K3-divisible graph with minimum degree at least (0.852+ε)n, for any ε>0, has an actual triangle decomposition, by the transfer theorem.
By the continuity argument in the paper, the ε in the previous statement can be taken to be 0.
The result moves the known degree threshold closer to the conjectured 3/4 bound, while the paper's barrier example shows the rooted-pair switch alone cannot pass δ=1/6.
The proof isolates the hard parameter region (middle α and high t_A) and reduces it to a finite computational check, so future improvements can focus on that region.

Reading between the lines

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

The 0.852 constant is likely an artefact of the proof's inequalities; the paper's own barrier only rules out the rooted-pair switch below δ>1/6, so the true fractional threshold could be lower.
Because the transfer theorem converts fractional decompositions into integral ones, any future improvement of the fractional threshold would immediately improve the integral threshold for K3-divisible graphs; the fractional problem is probably the bottleneck for the dense case of the triangle-decomposition conjecture.
A reproducible certificate for the grid check, such as interval arithmetic or a formal proof, would make the 0.852 result independently checkable; the paper currently relies on a described but unpublished computation.
The three-level classification in Lemma 17 suggests a concrete way to search for near-extremal graphs: realize the three classes as vertex sets and test such constructions computationally to see whether the middle-range analysis is tight.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

The thing to know: this paper genuinely improves the known threshold for fractional triangle decompositions from 0.9n to 0.852n, and most of the proof is classical analytic combinatorics. The exception is Lemma 18, a computer-assisted verification that is load-bearing for the middle parameter range and is not auditable as written. So the main theorem is conditional on an unreproduced computation.

What is actually new: the reduction to (n,δ)-reduced graphs and the flow lemma come from Dross, but the paper strengthens the parameter bounds in Lemmas 8, 9, and 11, and Section 5 introduces a genuinely new way of counting separated rooted pairs by classifying vertices according to e_A(u). The piecewise functions g_i and the extremal argument in Lemma 17 are real work. If Lemma 18 holds, the derivation of Theorem 3 via Barber–Kühn–Lo–Osthus is clean, and the paper honestly notes that Delcourt–Postle later got a better bound.

The soft spot is exactly Lemma 18. It covers 0.446 < α < 0.692 and t_A > 0.7619n, the region no other lemma reaches. The proof says a finite grid with h = 0.00001 and positivity margin 0.00022 was checked, and that Mathematica symbolically maximised gradient norms, but no code, notebook, or certificates appear anywhere. The grid over Ξ has on the order of 1.4×10^11 points, so a referee cannot reproduce it by hand, and without the computing artifacts cannot verify it at all. Table 1 asserts gradient bounds as Mathematica maxima, again with no derivation or output. That makes the proof incomplete as presented. I am not claiming the theorem is false—the analytic scaffolding before Lemma 18 is coherent and the strict inequality may well be true—but this should not be accepted in this form.

Other concerns are minor. The asymptotics in Lemma 15(iii) are a bit compressed, and the O(n) term in Lemma 17 is hand-wavy but standard for large n. The citation pattern is normal and the provenance of the method is clearly attributed.

This paper is for readers working on graph decompositions and the Nash-Williams threshold. It deserves serious referee time, but the referee should be asked to verify that the Lemma 18 computation is real and complete. I would not certify the proof until the code or certificates are supplied.

Referee Report

3 major / 4 minor

Summary. The paper proves that, for sufficiently large n, every graph of order n and minimum degree at least 0.852n admits a fractional decomposition into triangles (Theorem 2). The proof refines the flow-based method of Dross, reducing the threshold from 0.9n to 0.852n. The argument establishes a sufficient condition (Lemma 5) involving counting rooted pairs separated by a subset A of edges, and then verifies this condition through a series of analytic estimates (Lemmas 12–14) and, for the remaining middle range of parameters, a computer-assisted verification (Lemma 18). Applying the transfer theorem of Barber, Kühn, Lo and Osthus, the authors obtain an asymptotic triangle-decomposition result for K3-divisible graphs with minimum degree above 0.852n (Theorem 3), and they argue that the epsilon can be taken to be zero.

Significance. If the proof is accepted, this is a substantial quantitative improvement in a long-standing line of work on Nash-Williams' triangle decomposition conjecture, bringing the fractional threshold from 0.9n to 0.852n, very close to the 5/6 barrier identified in Lemma 6. The analytic machinery is a genuine contribution: Lemma 11 provides a new convexity bound, and the Section 5 vertex-classification method for the middle range is original. The transfer to integral decompositions via the Barber–Kühn–Lo–Osthus theorem is standard and correctly invoked. However, the central load-bearing step for the middle range (Lemma 18) rests on an unauditable computer-assisted verification: no code, data, or certificates are supplied, and the stated grid has on the order of 10^11 points. The theorem is therefore conditional on a numerical computation that the paper does not make possible to check. This is a serious completeness gap, though it is local and potentially fixable by providing the computational artifacts.

major comments (3)

[Section 5, Lemma 18] The proof of Lemma 18 is not verifiable as written. The lemma is the only support for the case 0.446 ≤ α ≤ 0.692 and tA ≥ 0.7619n, and its conclusion is established solely by a 'rigorous computer-assisted verification' that is not actually reproducible: no code, notebook, input files, or certificates are provided. The stated grid over the box Ξ with h = 0.00001 contains roughly (0.246/10^-5)(0.053/10^-5)(0.011/10^-5) ≈ 1.4 × 10^11 evaluation points, which cannot be repeated by a reader and is far too large to audit by hand. To make the proof complete, the authors should either supply the verification script together with interval-arithmetic certificates or replace the finite-grid check with a smaller, fully certified computation.
[Section 5, Table 1] The gradient bounds in Table 1 are reported only as symbolic maxima obtained with Mathematica, with no derivation or implementation details. Since the mean-value step requires the uniform bound max_i ||∇gi|| + ||∇k|| ≤ 22n^4 + o(n^4), any rounding error or mistake in the symbolic maximizations would invalidate the final inequality. The authors should provide explicit expressions for the maximized functions and the scripts that compute them, or else derive the bounds by hand, so that an auditor can independently confirm Table 1.
[Lemma 18, inequality (12)] The proof of Lemma 18 compares the O(n^4) terms of g and k after writing κA > λA provided the limit of (g-k)/n^4 is positive. The error term in (12) is only described as O(n^3) and 'allows us to neglect' the O(1) differences between n_i and n'_i and the uncovered pairs. For the final positivity conclusion to be rigorous uniformly over the box Ξ, the paper should state an explicit bound on the O(n^3) error term as a function of the parameters α, τ, μ, and check that it is dominated by ρn^4/h for sufficiently large n. The current wording leaves a small but load-bearing gap in the asymptotic comparison.

minor comments (4)

[Lemma 18] The box Ξ uses τ ≥ 0.761, while the hypothesis of the lemma gives τ ≥ 0.7619. Verifying on a slightly larger box is harmless, but the discrepancy should be acknowledged explicitly so the reader does not wonder whether the threshold was shifted.
[Lemma 17] The proof of Lemma 17 introduces the function f† through a lexicographic maximality argument and then concludes that f† maps x vertices to e2 and n−y+1 vertices to e0, with all but at most two of the remaining vertices at e1. It would be helpful to give a short explanation of why the 'at most two' exceptional vertices do not affect the subsequent asymptotic count in n0 and n1, since the current text states this only in passing.
[Introduction] The sentence 'In fact, ε can be taken to equal 0, as we discuss following the proof of Theorem 2' is slightly misleading because the discussion appears only in a final paragraph without an explicit theorem statement; presenting this as an explicit corollary would improve readability.
[References] Reference [2] is a preprint; the authors may wish to update its status if a published version has appeared by the time of final revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the 0.852 threshold emerges from explicit inequality checks; Lemma 18's computational gap is a reproducibility issue, not a circular one.

full rationale

The derivation chain is self-contained and does not reduce to its inputs. Theorem 2 is proved by verifying the sufficient condition κA ≥ λA from Lemma 5 for every subset A of edges. The constant 0.852 is not fitted to the conclusion: δ = 0.148 is fixed as a hypothesis, and Lemmas 12, 13, 14 and 18 establish the required inequality over the parameter regions tA ≤ 0.7619n, α ≤ 0.446, α ≥ 0.692, and the middle box Ξ respectively. The quantities κA and λA are defined in terms of the graph and the partition, not in terms of the existence of a decomposition. The analytic bounds in Lemmas 8, 9, 10, 11, 15, 16 and 17 are derived from the (n, δ)-reduced graph assumptions and convexity, not from the target theorem. Lemma 18 contains a computer-assisted verification of the positivity of (g − k)/n^4 on Ξ, but that verification checks a concrete derived inequality; no parameter is fitted to force the desired result. The absence of code or certificates is a reproducibility or correctness concern, not circularity. The transfer to ordinary triangle decompositions in Theorem 3 relies on the independent external result of Barber, Kühn, Lo and Osthus. Citations to prior work, including Dross, are external and are used as stated ingredients, not as a self-citation chain. No circular step is present.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The proof rests on standard extremal graph theory and one unauditable computer-assisted verification. The only hand-chosen numerical parameter is delta = 0.148, plus the grid constants rho and h used in Lemma 18. No new particles, forces, or physical entities are postulated.

free parameters (2)

delta (deficit parameter) = 0.148
The proof of Theorem 2 is developed for delta = 0.148, giving threshold 0.852. It is not data-fitted, but it is a hand-chosen constant that makes the inequalities in Lemmas 12-18 hold, and the proof is not written for general delta.
rho and h grid verification constants = rho = 0.00022, h = 0.00001
The finite-grid verification in Lemma 18 chooses rho and h so that rho/h dominates the gradient bound; the choice makes the numerical verification work as presented.

assumptions (4)

domain assumption The graph under consideration is finite, simple, and n is sufficiently large for all asymptotic statements.
Throughout Sections 4 and 5, O(1), O(n^2) and O(n^3) terms are absorbed by taking n large, and graphs are implicitly simple.
standard math Max-flow min-cut and the flow network in Lemma 5 correctly characterize when the weight-switching procedure yields a fractional decomposition.
Lemma 5 invokes max-flow min-cut and the reduced-graph degree bound; this is a nontrivial but standard step.
domain assumption The reduction to (n, delta)-reduced graphs by repeatedly deleting triangles preserves the minimum-degree hypothesis.
Used at the start of Section 2 to justify proving the theorem only for reduced graphs; the brief argument there is sound but not fully expanded.
ad hoc to paper The computer-assisted verification in Lemma 18, including the finite grid check and the Mathematica gradient bounds in Table 1, is correct.
The lemma's proof is not a hand derivation; it depends on an external computation with no artifacts provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the minimum degree required for a triangle decomposition." pith.science (2026). https://pith.science/paper/X2PDMDX3

@misc{pith2026190811076,
  author       = {Pith},
  title        = {Pith review of: On the minimum degree required for a triangle decomposition},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X2PDMDX3}},
  note         = {Machine review of arXiv:1908.11076}
}

abstract

We prove that, for sufficiently large $n$, every graph of order $n$ with minimum degree at least $0.852n$ has a fractional edge-decomposition into triangles. We do this by refining a method used by Dross to establish a bound of $0.9n$. By a result of Barber, K\"{u}hn, Lo and Osthus, our result implies that, for each $\epsilon >0$, every graph of sufficiently large order $n$ with minimum degree at least $(0.852+\epsilon)n$ has a triangle decomposition if and only if it has all even degrees and number of edges a multiple of three.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

8 extracted references · 7 canonical work pages

[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

2016
[2]

Progress towards Nash-Williams' Conjecture on Triangle Decompositions

M. Delcourt and L. Postle, Progress towards Nash-Williams’ conj ecture on triangle decom- positions. Preprint https://arxiv.org/abs/1909.00514

work page Pith review arXiv 1909
[3]

Dross, Fractional Triangle Decompositions in Graphs with Larg e Minimum Degree, SIAM J

F. Dross, Fractional Triangle Decompositions in Graphs with Larg e Minimum Degree, SIAM J. Discrete Math. 30 (2016), 36–42

work page 2016
[4]

Garaschuk, Linear methods for rational triangle decomposit ions

K. Garaschuk, Linear methods for rational triangle decomposit ions. Ph.D. dissertation, University of Victoria, 2014

work page 2014
[5]

Gustavsson, Decompositions of large graphs and digraphs wit h high minimum degree, PhD thesis, Univ

T. Gustavsson, Decompositions of large graphs and digraphs wit h high minimum degree, PhD thesis, Univ. of Stockholm, 1991. 14

work page 1991
[6]

Kirkman, On a problem in combinatorics, Cambridge Dublin Mathe matical Journal, 2 (1847), 191–204

T.P. Kirkman, On a problem in combinatorics, Cambridge Dublin Mathe matical Journal, 2 (1847), 191–204

work page
[7]

Nash-Williams, An unsolved problem concerning decomposit ion of graphs into triangles, Combinatorial Theory and its Applications III, North Holla nd (1970), 1179–1182

C.St.J.A. Nash-Williams, An unsolved problem concerning decomposit ion of graphs into triangles, Combinatorial Theory and its Applications III, North Holla nd (1970), 1179–1182

work page 1970
[8]

Yuster, Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions

R. Yuster, Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions. J. Combin. Theory Ser. B. 95 (2005), 1–11. 15

work page 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 and D. Osthus, Edge decompositions of graphs with high minimum degree, Adv. Math. 288 (2016), 337–385

2016

[2] [2]

Progress towards Nash-Williams' Conjecture on Triangle Decompositions

M. Delcourt and L. Postle, Progress towards Nash-Williams’ conj ecture on triangle decom- positions. Preprint https://arxiv.org/abs/1909.00514

work page Pith review arXiv 1909

[3] [3]

Dross, Fractional Triangle Decompositions in Graphs with Larg e Minimum Degree, SIAM J

F. Dross, Fractional Triangle Decompositions in Graphs with Larg e Minimum Degree, SIAM J. Discrete Math. 30 (2016), 36–42

work page 2016

[4] [4]

Garaschuk, Linear methods for rational triangle decomposit ions

K. Garaschuk, Linear methods for rational triangle decomposit ions. Ph.D. dissertation, University of Victoria, 2014

work page 2014

[5] [5]

Gustavsson, Decompositions of large graphs and digraphs wit h high minimum degree, PhD thesis, Univ

T. Gustavsson, Decompositions of large graphs and digraphs wit h high minimum degree, PhD thesis, Univ. of Stockholm, 1991. 14

work page 1991

[6] [6]

Kirkman, On a problem in combinatorics, Cambridge Dublin Mathe matical Journal, 2 (1847), 191–204

T.P. Kirkman, On a problem in combinatorics, Cambridge Dublin Mathe matical Journal, 2 (1847), 191–204

work page

[7] [7]

Nash-Williams, An unsolved problem concerning decomposit ion of graphs into triangles, Combinatorial Theory and its Applications III, North Holla nd (1970), 1179–1182

C.St.J.A. Nash-Williams, An unsolved problem concerning decomposit ion of graphs into triangles, Combinatorial Theory and its Applications III, North Holla nd (1970), 1179–1182

work page 1970

[8] [8]

Yuster, Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions

R. Yuster, Asymptotically optimal Kk-packings of dense graphs via fractional Kk- decompositions. J. Combin. Theory Ser. B. 95 (2005), 1–11. 15

work page 2005