{"id":"f96ec54a-354a-44ca-8394-4cccb06db71d","arxiv_id":"2511.11331","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every sufficiently large n-vertex tree has gracesize at least (1−ε)n; i.e., an almost graceful labelling exists for all trees.","lead":"This paper proves that every sufficiently large tree can be labelled with its own vertex numbers so that almost all edge length differences are distinct — the asymptotic form of the 60-year-old graceful tree conjecture. It removes the maximum-degree restriction that blocked all previous near-graceful labelling theorems.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.4 omits the low-degree vertex bound needed for Theorem 5.3 and has an invalid Lipschitz step; the rainbow-matching tool, on which the whole embedding proof rests, is therefore not proven as written.","rationale":"The paper's main theorem is a plausible asymptotic breakthrough, and large parts of the structure are sound: Lemma 4.1 (tree splitting), the interval matching construction of Proposition 5.8, and the reduction from Lemma 1.4 to Theorem 1.3 all appear consistent. The bottleneck is Lemma 5.4, which supplies the rainbow matchings used in Lemmas 5.6 and 5.9. The application of Theorem 5.3 to H_P lacks the required low-degree vertex bound: the proof only verifies concentration on the good intervals and never counts bad boundary vertices, despite the hierarchy permitting a Chernoff argument. The stated 2-Lipschitz constant in the McDiarmid step is also incorrect because toggling the coordinate v=b can change d_{H_P}(b) by up to 2s. The covering conclusion in terms of max{|S1|,|S2|} also does not follow directly from the total uncovered count of the 3-partite hypergraph, though this is a constant-factor issue. These are genuine gaps in the proof of the core embedding tool, matching the reader's identified weakest assumption. They appear repairable with standard techniques, so the CONDITIONAL verdict is appropriate; no change is needed.","tokens_in":26548,"tokens_out":31096,"duration_ms":229816,"concrete_test":"Re-derive Lemma 5.4 with a rigorous bound on the number of low-degree vertices: for each bad class (A1∩[1,2s−1], etc.), use Chernoff to show with probability 1−o(1) the number of vertices with degree <(1−√γ)(p^2 μ/10)|H_P| is at most (μ/2)|H_P|; and replace the McDiarmid step for d_{H_P}(b) with a correct concentration bound (e.g., Chernoff on the |A1∩N_R(b)| independent trials conditional on P). If both repairs go through, the concern is resolved; if either fails, the rainbow-matching lemma is false or unproven and the main theorem's proof collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 5.4 is the core embedding tool: Lemma 5.6 uses it to produce rainbow matchings between parts of the random partition, and Lemma 5.9 relies on Lemma 5.6 to embed the auxiliary tree. The proof of Lemma 5.4 invokes Theorem 5.3 on the random 3-uniform hypergraph H_P = R[A_1,B_2,P_2]. Theorem 5.3 requires that at most μ|H_P| vertices have degree below (1−√γ)(p^2 μ/10)|H_P|. The paper proves (P3), degree concentration for vertices in the 'good' intervals [2s, n/2−s], [n/2+2s, n−s], [2s, n−2s], and (P2), an upper bound on all degrees. But it never bounds the number of 'bad' vertices near the boundaries of these intervals, nor shows these vertices have degree above threshold. In fact vertices in A∩[1,2s−1] have d_R(a)=O(s), giving expected degree Θ(p^2 s)=α|H_P|, so the missing bound is not automatic. Meanwhile the concentration argument for b∈B states d_{H_P}(b) is 2-Lipschitz in S2; flipping b itself changes the degree by up to 2s, so the McDiarmid step as written is invalid. Finally, the coverage inference 'all but 2μ max{|S1|,|S2|}' conflates total uncovered vertices of the 3-partite hypergraph (whose colour class is a clone of S2) with per-class uncovered counts; the stated total bound only gives O(μ) max per class. Each of these may be repairable by standard constant absorption and a correct Chernoff argument, but as written Lemma 5.4 does not have a valid proof, and the rest of the paper depends on it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every ε>0, all sufficiently large n-vertex trees T have gracesize at least (1−ε)n, i.e. T admits a bijective labelling into [n] with at least (1−ε)n distinct edge-differences. The proof embeds T almost-rainbowly into the difference-coloured complete graph K[(1+ε)n] via a three-stage argument: (i) a tree-splitting lemma (Lemma 4.1) finds a small set W and a set S_high so that T−W decomposes into many copies of a small rooted forest, with roots adjacent only to S_high; (ii) a random-hypergraph matching lemma (Lemma 5.4) supplies almost-perfect rainbow matchings between vertex parts; (iii) an auxiliary-tree construction (Lemma 5.9) uses these matchings to embed the remaining forest rainbowly. The paper improves earlier work by removing all maximum-degree restrictions.","tokens_in":27052,"tokens_out":16681,"duration_ms":125299,"significance":"This is a substantial advance toward the graceful tree conjecture. The main result — an asymptotically optimal gracesize bound for all trees — goes well beyond the previous degree-restricted theorem of Adamaszek–Allen–Grosu–Hladký and the constant-factor bound of Rosa–Širáň. The paper is also methodologically attractive: it shifts the problem to anti-Ramsey embeddings, uses a clean tree-splitting lemma, and provides explicit constructions for the rainbow matchings. The proof is mostly elementary and carefully parameterised. However, the core embedding lemma (Lemma 5.4) has proof gaps that, as written, prevent the central claim from being verified; these gaps are locally repairable but require substantial additional estimates.","major_comments":[{"comment":"The verification of the hypotheses of Theorem 5.3 for H_P is incomplete. Theorem 5.3 requires at most μ|H_P| vertices of degree below (1−√γ)(p^2μ/10)|H_P|, but the paper only proves degree concentration (P3) on the 'good' intervals [2s,n/2−s], [n/2+2s,n−s], and [2s,n−2s]. The boundary intervals [1,2s−1], [n/2−s+1,n/2], [n/2+1,n/2+2s−1], and the corresponding colour intervals contain Θ(s)=Θ(μ|H_P|) vertices whose typical degree can be much smaller than the threshold; no bound on the number of such low-degree vertices is given. This is not a cosmetic issue: if all boundary vertices are below threshold, their number can exceed μ|H_P|. The lemma needs a separate estimate for these vertices, or an absorption argument that weakens the hypothesis.","section":"§5.1, Claim 5.5"},{"comment":"The claimed 2-Lipschitz property for d_{H_P}(b) is not justified as written. The product space over which McDiarmid is applied includes the coordinate corresponding to b itself; if that coordinate is switched from 'b∈S2' to 'b∉S2', then d_{H_P}(b) changes from its full value to 0, which can be as large as O(p^2s), not 2. If the intention is to condition on b being in S2 and apply McDiarmid over the remaining random vertices, this should be stated explicitly and the Lipschitz constant should be derived for all varying coordinates. The current text makes the concentration argument formally invalid.","section":"§5.1, McDiarmid step (5.3)"},{"comment":"The proof of Theorem 5.3 contains an impossible inequality. The chain derives that e(H)/χ'(H) is at least (1−μ)(n/r) times (1−γ)/(1+γ+o(1)) and then claims this is at least (1−μ)·2n/r. Since (1−γ)/(1+γ)<1, this cannot hold. The intended bound is that, with γ≪μ, the factor (1−μ)(1−γ)/(1+γ) is at least (1−2μ), giving the desired (1−2μ)n/r. The factor '2' should be replaced by '1−2μ' (or similar), and the corresponding size condition on n adjusted. This is a serious error in a quoted theorem, although the theorem itself is standard and the proof is repairable.","section":"§5.1, Theorem 5.3"}],"minor_comments":[{"comment":"The per-class coverage bound follows from the total bound, but the text skips the arithmetic. Since a matching covers equally many vertices in each of the three classes, the number uncovered per class is at most (1/3)·2μ(|S1|+2|S2|) ≤ 2μ max{|S1|,|S2|}. The paper should spell this out; as it stands the inference is terse but valid.","section":"§5.1, last paragraph of Lemma 5.4"},{"comment":"The final containment is written as K[˜n]∪{0}⊆K[(1+ε/2)n]∪{0}, but the lemma statement and the preceding bound give K[˜n]∪{0}⊆K[(1+ε)n]∪{0}. The ε/2 appears to be a typographical remnant and should be corrected.","section":"§5.2, end of Lemma 5.6"},{"comment":"The final sentence says 'all but at most εn edges have distinct colours', which yields at least n−1−εn distinct colours, just short of (1−ε)n. The argument can be patched by applying the previous steps with a slightly smaller ε (e.g. ε/2) or by tracking the number of repeated colours more carefully. Please adjust the constants.","section":"§6, last line"},{"comment":"The hierarchy notation 0<a≪b≤1 is introduced without stating explicitly that all constants are positive and can be chosen from right to left. This is standard but should be stated in one sentence, as the paper relies heavily on it.","section":"§2.2, Notation"},{"comment":"In the embedding of root vertices, the sentence 'This is possible because d'≤d=|I'_j|' assumes d' is an integer and the interval I'_j has size d, which is correct, but it may help the reader to recall that I'_j was defined with exactly d elements after removing the last 3|S| labels. No change needed beyond clarity.","section":"§5.3, line after (5.10)"}],"recommendation":"major_revision","confidential_remarks":"The main difficulties are concentrated in Lemma 5.4, and they are in the proof rather than in the plausibility of the statement. I believe the lemma is true and can be proved by adding a low-degree-vertex estimate for the boundary intervals and by fixing the McDiarmid setup. The error in Theorem 5.3 is a typo-level error in a standard result. I am not recommending rejection because the overall strategy is sound and the gaps are local. The result, if fixed, is certainly a strong paper for a top combinatorics journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. First, if the proof is correct, this is a major result: it resolves the asymptotic form of the graceful tree conjecture for all trees, removing the Δ=o(n/log n) barrier in Adamaszek–Allen–Grosu–Hladký. Second, as written, the proof does not quite compile in the key matching lemma, and the stress-test note is right about where.\n\nWhat's new and good: the reduction from Lemma 1.4 to Theorem 1.3 is clean, and the idea of embedding an auxiliary tree via rainbow blow-up is genuinely new. The tree-splitting lemma (Lemma 4.1) is solid, and the high-level architecture—split off high-degree vertices, embed the rest by matchings, then absorb waste vertices—is sensible. The paper is written in a way that a knowledgeable reader can actually check the details, which is a credit.\n\nThe soft spots are all in Lemma 5.4. The application of Theorem 5.3 to H_P requires a bound on the number of low-degree vertices; the paper only proves concentration on the 'good' intervals and never counts the boundary vertices, which can have expected degree a constant fraction below the target. The McDiarmid argument for b∈B2 is invalid as written: flipping b itself changes d_{H_P}(b) by up to 2s, so the function is not 2-Lipschitz on the stated product space. And the final coverage count 'all but 2μ max{|S1|,|S2|}' does not follow from the per-hypergraph matching bounds, since the colour class is a clone of S2 and the total vertex count is |S1|+2|S2|. There is also a numerical error in Theorem 5.3's displayed inequality: it requires (1−γ)/(1+γ) ≥ 2, which is impossible. These are not deep conceptual failures—I expect a standard Chernoff/McDiarmid repair plus constant absorption would fix them—but the proof as printed is not complete.\n\nWho should read this: anyone working on graceful labellings or rainbow embeddings. It deserves a serious referee, but the referee should be told to focus on Lemma 5.4 and ask for a corrected version before acceptance. I would not cite it yet; I'd wait for a revised version.","headline":"The main theorem is a genuine breakthrough—every large tree has gracesize (1−o(1))n—but the proof as written has a few holes in the rainbow-matching engine that need fixing before I'd trust it.","tokens_in":27531,"tokens_out":6864,"would_cite":false,"duration_ms":58976,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C78","05C05","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every sufficiently large tree is almost graceful.","keywords":["graceful labelling","gracesize","tree labellings","graceful tree conjecture","difference-coloured complete graph","rainbow subgraphs","hypergraph matchings","asymptotic combinatorics"],"falsifier":"Simulate Lemma 5.4 for, say, n=10⁴, p=0.1, µ=0.05 and count vertices in H_P whose degree deviates from its expectation by more than the γ factor; the theorem predicts such vertices number o(|H_P|), and a counterexample near the boundary would show the proof's matching claim is not guaranteed.","tokens_in":26447,"feed_emoji":"🌲","tokens_out":5407,"duration_ms":52851,"temperature":0.7,"pith_summary":"An n-vertex tree is graceful when its vertices can be labelled 1..n so that the n−1 edge differences are all distinct. The graceful tree conjecture, posed in the 1960s, says this is always possible, and it remains open. This paper proves the next best thing: for every ε>0 and all sufficiently large n, every n-vertex tree has a labelling with at least (1−ε)n distinct edge differences — a near-graceful labelling. The proof recasts the problem as finding an almost-rainbow copy of the tree in the complete graph whose edge colours are absolute differences of the labels, then splits the tree into a few high-degree vertices plus many copies of a small forest and embeds the copies using almost-perfect rainbow matchings obtained from random hypergraphs. A reader should care because the result removes the degree restriction that limited earlier asymptotic progress and shows the remaining gap to the full conjecture is quantitative, not structural.","feed_headline":"Every sufficiently large tree is almost graceful","feed_subtitle":"New theorem: for any ε>0, all large n-vertex trees admit labellings with at least (1−ε)n distinct edge differences.","key_machinery":"Three pieces carry the argument. (1) The difference-coloured complete graph K_X: vertex set X, edge ij coloured |i−j|; a graceful labelling is exactly a rainbow embedding of T into K_[n]. (2) A translation to 3-uniform 3-partite hypergraphs: for disjoint vertex sets A, B and colour set C, an edge ab of colour c becomes the hyperedge {a,b,c}; rainbow matchings in K correspond to hypergraph matchings, so an almost-perfect matching theorem for linear hypergraphs yields almost-perfect rainbow matchings between random sets. (3) A tree-splitting lemma: after deleting a small set W of waste vertices, T∖(W∪S_high) decomposes into ζn disjoint copies of one small forest F, with all edges from copies i","core_discovery":"The paper's central claim, Theorem 1.3, is that for every ε>0 there is n0 such that every n-vertex tree T with n>n0 satisfies gs(T) ≥ (1−ε)n. Equivalently, T embeds into the difference-coloured complete graph on [(1+ε)n] vertices with at least (1−ε)n distinct edge colours appearing. The authors first prove a stronger intermediate statement: even if labels are allowed to range up to (1+ε)n, the same fraction of distinct differences is achievable; a leaf-stripping argument then converts this into the gracesize estimate. The core discovery is that, for all sufficiently large trees, a near-graceful labelling exists regardless of maximum degree — the high-degree vertices are not the obstruction.","pith_inferences":["A full solution of the graceful tree conjecture would likely have to make the rainbow-matching step exact rather than approximate, since the other losses in the proof are introduced deliberately and could in principle be removed by more careful bookkeeping.","The same hypergraph-matching framework may extend to other rainbow embedding problems in difference-coloured complete graphs, such as finding almost-rainbow copies of bounded-degree spanning subgraphs besides trees.","A concrete computational check for moderate n — whether the random hypergraph in the matching lemma really has only o(n) low-degree vertices counting the boundary cases — would either validate the core step or pinpoint a repairable gap near the ends of the label interval.","Because the proof only uses that each vertex set has at most one earlier neighbour in the ordering, it may adapt to forests with bounded component size after deleting a small set, not just trees."],"forward_implications":["Every sufficiently large tree has gracesize at least (1−ε)n, giving the current best universal lower bound toward the graceful tree conjecture.","Every large tree admits a labelling into [(1+ε)n] with at least (1−ε)n distinct edge differences, with no restriction on maximum degree.","The earlier (1−o(1))n bound, known for trees of maximum degree o(n/log n), now follows as a special case of a statement covering all trees.","The paper identifies a natural next target: prove that every tree has a range-relaxed graceful labelling into [(1+o(1))n], which would essentially complete the asymptotic version of the conjecture.","The constructed labelling uses at most εn repeated colours, so the proof gives a linear, arbitrarily small collision budget rather than a merely asymptotic one."],"fun_headline_variants":["Every big tree is almost graceful","Near-graceful labellings exist for all large trees","Gracesize of large trees approaches maximum","Asymptotic proof: all large trees are almost graceful","Large trees: near-perfect graceful labellings always exist"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof rests on the claim that the random hypergraphs built from the difference-coloured graph have almost all vertices of near-expected degree; if many vertices near the boundaries of the label interval fail this, the almost-perfect rainbow matching lemma — the core embedding tool — breaks down.","fun_headline_variants_meta":{"raw":{"variants":["Every big tree is almost graceful","Near-graceful labellings exist for all large trees","Gracesize of large trees approaches maximum","Asymptotic proof: all large trees are almost graceful","Large trees: near-perfect graceful labellings always exist"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000171,"raw_usage":{"total_tokens":1123,"prompt_tokens":771,"completion_tokens":352,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":277}},"tokens_in":515,"tokens_out":352,"duration_ms":4116,"temperature":1.0,"reasoning_tokens":277,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T22:15:04.419531+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate Lemma 5.4 for, say, n=10⁴, p=0.1, µ=0.05 and count vertices in H_P whose degree deviates from its expectation by more than the γ factor; the theorem predicts such vertices number o(|H_P|), and a counterexample near the boundary would show the proof's matching claim is not guaranteed.","supporting_citations":[],"review_version":1}