{"id":"0a62e3fc-e711-425d-9451-a801fc399778","arxiv_id":"1908.11076","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"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.","lead":"Every sufficiently large graph with minimum degree at least 0.852n can be edge-covered by fractional triangle weights. This improves a known 0.9n bound and yields exact triangle decompositions for divisible graphs just above the new threshold.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 18 is the keystone for the middle parameter range, but its computer-assisted grid verification is not reproducible: no code or certificates are given, and the stated h=10^-5 grid has ~10^11 points. Theorem 2 is conditional on this unauditable computation.","rationale":"The reader identified the same weakest point: Lemma 18's computer-assisted grid verification is load-bearing and unauditable. I agree. I considered whether there was also an internal gap in the numerical criterion itself: the paper requires rho n^4/h > max ||nabla g_i|| + ||nabla k|| and takes h = 0.00001, rho = 0.00022, so the threshold is 22 n^4. Although the final line states the gradient sum is at most 22 n^4 + o(n^4), the displayed chain-rule bounds actually give ||nabla g_4|| <= 15.083 n^4 + o(n^4) and ||nabla k|| <= 0.187 n^4, so the sum is below 22 n^4 for large n; the stated margin is therefore internally consistent. What remains is the absence of any reproducible artifact for the grid evaluation itself. The theorem may well be true, and the analytic part before Lemma 18 is plausible, but a proof whose central range rests on an unreproducible computation does not meet the standard for unconditional acceptance. The concrete test, an independent interval-arithmetic rerun with certificates, would settle whether the concern lands. Until then, the correct verdict remains conditional rather than accept or reject.","tokens_in":14983,"tokens_out":15395,"duration_ms":155440,"concrete_test":"Rerun Lemma 18's verification with an independent interval-arithmetic implementation of g1,...,g4 and k on the box Xi at grid spacing h = 0.00001, computing rigorous enclosures for the minimum of (g-k)/n^4 over the grid and rigorous upper bounds for ||nabla g_i|| and ||nabla k||. Publish a machine-readable certificate showing that the grid minimum is at least rho = 0.00022 and that max_i ||nabla g_i|| + ||nabla k|| is strictly below rho/h = 22 for all sufficiently large n, with a positive margin. If the certificate passes, Lemma 18 is verified; if it fails or cannot be produced, the proof of Theorem 2 has an unsupported step in the middle parameter range.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 2 ultimately relies on Lemma 5, which requires kappa_A >= lambda_A for every subset A of edges. Lemmas 12-14 cover low t_A, low alpha, and high alpha; the remaining region 0.446 <= alpha <= 0.692 with t_A >= 0.7619n is supported only by Lemma 18. That lemma reduces the needed inequality to positivity of (g-k)/n^4 on the box Xi, and then asserts a finite-grid verification with h = 0.00001, rho = 0.00022, and gradient bounds from Table 1. As written, this is the sole evidence for the middle range. Three obstacles prevent an auditor from confirming it. First, no code, notebook, or certificate is supplied, even though the paper calls the verification rigorous and computer-assisted. Second, the stated grid over intervals of width about 0.246, 0.053, and 0.011 contains roughly 1.4 x 10^11 points, so the claimed evaluation cannot be repeated by a reader and is far too large to check by hand. Third, the gradient bounds are reported only as Mathematica symbolic maxima, with no derivation or implementation details; any rounding error or mistake in those bounds would invalidate the mean-value step. The analytic reductions before Lemma 18 appear coherent, so I am not claiming the theorem is false; I am claiming the proof is incomplete as presented unless the numerical verification is made auditable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15320,"tokens_out":3747,"duration_ms":39450,"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":[{"comment":"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":"Section 5, Lemma 18"},{"comment":"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.","section":"Section 5, Table 1"},{"comment":"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.","section":"Lemma 18, inequality (12)"}],"minor_comments":[{"comment":"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.","section":"Lemma 18"},{"comment":"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.","section":"Lemma 17"},{"comment":"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.","section":"Introduction"},{"comment":"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.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"This is a paper whose mathematical core is plausible and whose analytic parts are largely in good shape, but the publication of the main theorem as a rigorous result is currently blocked by the unauditable computational verification in Lemma 18. I would suggest that the editor require the authors to supply the missing code and certificates, or otherwise replace the 10^11-point grid with a certified computation, before acceptance. If the authors can do this, the paper would be a strong contribution to the area."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nOther 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.\n\nThis 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.","headline":"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.","tokens_in":15834,"tokens_out":2798,"would_cite":true,"duration_ms":28536,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C70","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every sufficiently large graph with minimum degree at least 0.852n has a fractional K3-decomposition.","keywords":["fractional triangle decomposition","minimum degree threshold","K3-decomposition","Nash-Williams conjecture","rooted pair switch","flow network","computer-assisted proof","dense graphs"],"falsifier":"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.","tokens_in":14770,"feed_emoji":"🔺","tokens_out":9656,"duration_ms":89242,"temperature":0.7,"pith_summary":"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).","feed_headline":"Minimum degree 0.852n suffices for fractional triangle decompositions","feed_subtitle":"Improves the previous 0.9n bound and yields genuine triangle decompositions just above the new threshold.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the rooted-pair switch and the flow-network criterion (Lemmas 4 and 5) that this paper refines and applies.","marker":"[3]"},{"why":"Its transfer theorem converts a fractional triangle decomposition into a genuine triangle decomposition for dense graphs, yielding Theorem 3.","marker":"[1]"},{"why":"The conjecture this work targets: triangle decompositions of K3-divisible graphs with minimum degree at least 3n/4.","marker":"[7]"}],"fun_headline_variants":["Fractional triangle decompositions now at 0.852n","Triangle decompositions threshold lowered to 0.852n","0.852n minimum degree suffices for fractional triangle decompositions","New bound: 0.852n for fractional triangle decompositions","From 0.9n to 0.852n: better triangle decomposition bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fractional triangle decompositions now at 0.852n","Triangle decompositions threshold lowered to 0.852n","0.852n minimum degree suffices for fractional triangle decompositions","New bound: 0.852n for fractional triangle decompositions","From 0.9n to 0.852n: better triangle decomposition bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000177,"raw_usage":{"total_tokens":1268,"prompt_tokens":898,"completion_tokens":370,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":514,"completion_tokens_details":{"reasoning_tokens":278}},"tokens_in":514,"tokens_out":370,"duration_ms":3839,"temperature":1.0,"reasoning_tokens":278,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:25:09.053939+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Dross, Fractional Triangle Decompositions in Graphs with Larg e Minimum Degree, SIAM J","cited_arxiv_id":null,"evidence_quote":"Supplies the rooted-pair switch and the flow-network criterion (Lemmas 4 and 5) that this paper refines and applies."},{"cited_title":"Nash-Williams, An unsolved problem concerning decomposit ion of graphs into triangles, Combinatorial Theory and its Applications III, North Holla nd (1970), 1179–1182","cited_arxiv_id":null,"evidence_quote":"The conjecture this work targets: triangle decompositions of K3-divisible graphs with minimum degree at least 3n/4."}],"review_version":1}