{"id":"4bd601e3-a2ca-4136-b3ef-69bc095ff954","arxiv_id":"2509.07934","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Every n-vertex tree with maximum degree at most cn has Ramsey number max{t1 + 2t2, 2t1} - 1, where t1 >= t2 are the sizes of its bipartition classes.","lead":"The authors prove that every tree whose maximum degree is at most a small constant times its number of vertices has its Ramsey number given exactly by the formula max{t1 + 2t2, 2t1} - 1, where t1 and t2 are the sizes of its two color classes. This turns a 2002 approximate bound into an exact one and answers an explicit question posed by Stein in 2020.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.1 is asserted as an \"easy\" extraction from HLT but no derivation is given; the entire stability argument starts from this unproved structure.","rationale":"The paper is a serious, coherent regularity-based proof, and I found no internal contradiction or sign of circularity. The most load-bearing point is exactly the one the reader identified: Theorem 5.1 is a strengthened, unproved version of HLT's theorem, and the four-stage stability argument has no starting point without it. The surrounding material in Section 4 is detailed and appears internally consistent, and the Type I extremal part in Section 6 is largely self-contained. The Type II part is truncated in the received text, but the suspected gap in Theorem 5.1 is more fundamental because even a complete Type II argument would not remove the need for the A-situation. I do not see grounds to reject the paper's claim, but the unstated derivation of Theorem 5.1 is a genuine verification burden: the authors should provide it or cite a version of HLT that includes the remembered clusters. The reader's CONDITIONAL verdict is therefore the appropriate one, and my stress-test does not change it.","tokens_in":82243,"tokens_out":4475,"duration_ms":54811,"concrete_test":"Independently re-derive Theorem 5.1 from [21, Theorem 3] by writing out the extraction: run the HLT argument on an epsilon-regular partition of G, then explicitly identify which clusters become I_A, I_B, and I_C and verify (i) I_C covers at least (1-2epsilon)t2 vertices, (ii) the claimed red adjacency from vertex 0 to I_A and the red perfect matching between I_A and I_B remain (epsilon,1/3)-regular after adding back the clusters outside the HLT structure, and (iii) applying HLT at n=(1-epsilon)(t1+2t2) with alpha=t1/t2 does not require a larger vertex count than G provides. If any of these steps cannot be exhibited, Theorem 5.1 must be proved or cited in verifiable form before Lemma 5.9 can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5 (Theorem 5.1) assumes that the proof of [21, Theorem 3], applied with alpha = t1/t2 and n = (1-epsilon)(t1+2t2), yields an A-situation in which all clusters outside the HLT structure are \"remembered\": a regular partition with clusters of sizes m and t1*m/t2, a partition [k] = I_A union I_B union I_C with |I_A|=|I_B|=|I_C|=k and km >= (1-2epsilon)t2, a red edge from 0 to every vertex of I_A, and a red perfect matching between I_A and I_B. This is not the statement of HLT, and the one-sentence justification does not show how the clusters outside the HLT structure are retained with full regularity after the refinement used inside HLT. If the HLT proof selects a maximal matching/cover and discards surplus clusters, or if applying it to a (1-epsilon)-scaled instance loses exactly the vertices needed to make I_C cover about t2 vertices, then Lemma 5.9 has no input, and the chain Lemmas 5.8 -> 5.5 -> 5.4 cannot start. Since Theorem 2.2 and hence Theorem 1.1 depend on this unverified premise, the central claim is conditional on an external proof obligation that is not exhibited in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves an exact Ramsey-number formula for every n-vertex tree whose maximum degree is at most a small constant times n: R(T) = max{2t_1, t_1+2t_2}-1, where t_1≥t_2 are the bipartition class sizes. This sharpens the asymptotic result of Haxell, Luczak, and Tingley and resolves, in the small-linear-degree regime, a question of Stein and a positive part of Burr's 1974 conjecture. The proof is divided into a stability part, which shows that a red/blue colouring either contains T or is close to one of Burr's two extremal constructions, and an extremal part, which handles both near-extremal cases by a substantial set of new embedding lemmas.","tokens_in":82530,"tokens_out":9716,"duration_ms":119610,"significance":"If the main theorem is correct, it is a significant exact result in Ramsey theory for trees, converting a previously asymptotic statement into an exact one under a natural bounded-degree hypothesis. The paper is also structurally ambitious: it develops a large toolbox of regularity-based embedding methods (EM1a-c, EM2a-d, HLT), and the extremal part contains delicate new arguments needed because small linear maximum degree still permits trees of small diameter. The proof is not circular: the upper bound is compared against Burr's external lower-bound constructions, and the paper explicitly notes the known 7/11+o(1) ceiling from Norin–Sun–Zhao, so the small constant c is not being optimized. However, the entire stability argument rests on an unproved extraction from earlier work, which is a load-bearing gap in the current version.","major_comments":[{"comment":"Theorem 5.1 is the starting point of the stability proof, but it is not proved in this manuscript and is not a stated theorem of [21]. The preceding paragraph says it 'easily follows from the proof of [21, Theorem 3]' applied with alpha=t1/t2 and n=(1-epsilon)(t1+2t2), while 'remembering' regularity clusters outside the HLT structure. This is exactly the kind of modification that needs a proof: one must show that the clusters outside the HLT structure can be retained with the required two sizes m and t1m/t2, that the partition into I_A,I_B,I_C with |I_A|=|I_B|=|I_C|=k and km≥(1-2ε)t2 can be produced, and that the perfect matching and star adjacency survive. No derivation or precise external reference is supplied. Since Lemma 5.9 consumes this structure and the chain Lemmas 5.9 -> 5.8 -> 5.5 -> 5.4 depends on it, the central claim is conditional on an unverified external proof obligation.","section":"Section 5, Theorem 5.1"},{"comment":"As stated, Theorem 5.1 is internally inconsistent in the colour of the structure: it says 'In R*, 0 is adjacent to every a∈I_A' but then 'R_red[I_A,I_B] contains a perfect matching'. If * is blue, these two properties are in different colours and do not form the monochromatic HLT- structure required by Lemma 5.9, whose assumptions Q3 and Q4 are both red. The statement should presumably have R*[I_A,I_B] in the matching bullet. This is not a mere presentation issue, because the colour consistency of the structure is essential for every subsequent stage.","section":"Section 5, Theorem 5.1, bullets"}],"minor_comments":[{"comment":"The reduction to t1≤2t2+1 in Section 2.1 uses t'_2=floor(t1/2), while the analogous reduction in the proof of Theorem 2.2 (Section 5.7) uses t'_2=ceil(t1/2). The two claims are not the same and the notation should be harmonized, with the relevant inequalities checked for both parity cases.","section":"Section 2.1 vs Section 5.7"},{"comment":"There are several typographical slips: 'Let Let I_A,3' at the start of the proof of Lemma 5.9; 'with with a partition' in Lemmas 4.6, 4.8, 4.9, 4.12, 4.13; 'F or' in Section 3; 'simiply' in Section 6.1. These do not affect the mathematics but should be corrected.","section":"Throughout"},{"comment":"The summary of the cascading argument is brief. The formal Lemma 5.10 is clear, but Stage 2 also uses a refinement into clusters of two different sizes (gamma m and gamma t1m/t2) and then requires an application of Lemma 5.5 after 'removing clusters with low degrees'. It would help the reader to state explicitly which hierarchy of constants makes this cluster-size conversion legitimate, since the B-situation in Lemma 5.8 has equal-sized clusters and the C-situation in Lemma 5.5 also assumes equal-sized clusters after refinement.","section":"Section 3, Stage 2"},{"comment":"In the Type II case of Lemma 5.3, the proof is omitted as 'similar'. Since Type II extremality is used in the final theorem, a few sentences indicating the counting and vertex-removal argument would make the dependency explicit.","section":"Section 5.1, Definition 5.2 and Lemma 5.3"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is conditional on Theorem 5.1, which is neither proved nor quoted from a precise source. If that extraction cannot be supplied, the stability part has no starting point. The colour mismatch inside Theorem 5.1's statement must also be corrected. This is likely fixable if the authors can give a full proof of the extracted A-situation from the HLT proof, but it is a substantial external proof obligation, not a local wording issue. The paper is otherwise extremely strong in scope and execution, with no apparent circularity or fitted parameters."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is a serious paper with a real theorem—exact Ramsey numbers for all n-vertex trees with maximum degree at most cn, matching Burr's lower bound. If correct, it answers Stein's 2020 question and sharpens Haxell–Luczak–Tingley from an approximation to equality. The novelty is not just the result; the proof machinery is genuinely new: the EM1a-c and EM2a-d embedding lemmas, the cascading matching lemma, and the split into stability and extremal parts with carefully designed reduced-graph structures. The lower bound side is Burr's external construction, so there is no circularity, no fitted parameters, and no invented entities. I checked the architecture: the embedding lemmas reduce to a common technical core (Lemma 4.2) and the stage diagram in Section 3 is coherent. The extremal parts are also substantial—the Type II case in particular has to navigate the Komlós–Sárközy–Szemerédi obstruction, and the authors do that explicitly.\n\nThe soft spot is real and load-bearing. Theorem 5.1 is the starting point of the entire stability proof, and it is not proved here. The text says it 'easily follows from the proof of [21, Theorem 3]' with a modification to remember the leftover regularity clusters. That is not a direct consequence of HLT's theorem statement, and the details of how the clusters outside the structure survive the refinement are not shown. Since Theorem 2.2 depends on this, the paper is conditional as written. I don't think this is fatal—the claim is plausible, and the authors are clearly aware of the distinction between the statement and the proof—but it needs to be filled in or replaced by a verifiable statement. Also, the received text is truncated near the end of Section 7.7, so the final Type II extremal claims aren't fully checkable from what I saw; that's a completeness issue rather than a mathematical flaw.\n\nWho is this for: anyone working on Ramsey numbers of trees or sparse Ramsey theory. It deserves a serious referee—the result is significant and the machinery is original. In review I would ask for the Theorem 5.1 derivation and the missing end of Section 7.7 before signing off, but I would not desk reject it. My own verdict: conditional, with the condition being a proof obligation rather than a suspected error.","headline":"Exact Ramsey numbers for small-linear-degree trees: real advance, coherent proof, but load-bearing Theorem 5.1 is asserted from HLT rather than proved; conditional as written.","tokens_in":83083,"tokens_out":2773,"would_cite":true,"duration_ms":33350,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C55","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Low-degree trees have exact Ramsey numbers","keywords":["Ramsey numbers","trees","1974 conjecture","regularity method","stability analysis","tree embeddings","extremal colourings","bipartite classes"],"falsifier":"Apply the 2002 proof to an explicit red/blue colouring of K_{t1+2t2-1} with t1≈2t2 and check whether the asserted starting structure appears: clusters of sizes m and (t1/t2)m, three equal parts each covering about (1−2ε)t2 vertices, a perfect matching, and a vertex joined to one side. Any colouring whose reduced graph cannot be partitioned this way while leaving the leftover clusters regular would invalidate the stability start. Alternatively, one counterexample tree with Δ(T)≤cn and R(T) > max{2t1, t1+2t2}−1 would directly falsify Theorem 1.1.","tokens_in":82116,"feed_emoji":"🌳","tokens_out":7160,"duration_ms":81835,"temperature":0.7,"pith_summary":"This paper proves that the Ramsey number of any n-vertex tree T with maximum degree at most c n is determined exactly by its bipartition class sizes: if t1 ≥ t2, then R(T) = max{2t1, t1+2t2} − 1. That formula had been conjectured in 1974 and was known to fail for some trees with very large maximum degree, so the theorem pins down the small-degree regime and answers a question posed explicitly in 2020. A 2002 result gave the formula only up to a (1+ε) factor; the improvement is to exact equality, for a small but fixed c. The proof splits into a stability part, which uses regularity to embed the tree unless the colouring closely matches one of two extremal constructions, and an extremal part, which handles those near-extremal colourings by delicate randomized embeddings.","feed_headline":"Low-degree trees have exact Ramsey numbers","feed_subtitle":"For trees with maximum degree up to a small linear fraction, R(T)=max{2t1, t1+2t2}−1; a 2020 question is resolved.","key_machinery":"The proof's load-bearing mechanism is a four-stage stability analysis on the reduced graph of a regularity partition. It starts from a scaled-down copy of the structure produced by the 2002 asymptotic proof (an 'A-situation': a vertex joined to one side of a nearly complete bipartite matching, with cluster sizes in ratio t1:t2), then passes through B-, C- and D-situations, at each stage either embedding T or concluding the reduced graph is extremal. The embedding workhorse is Lemma 4.2, which cuts T into tiny components through a homomorphism into a fixed auxiliary graph S, randomly assigns components to regular pairs, and uses concentration to keep cluster loads below capacity; specialised","core_discovery":"The central claim is Theorem 1.1: there is an absolute c>0 such that every n-vertex tree T with Δ(T)≤cn and bipartition classes of sizes t1≥t2 has Ramsey number R(T)=max{2t1, t1+2t2}−1. The two extremal colourings from 1974 show R(T) is at least this; the paper proves the matching upper bound by showing every red/blue colouring of K_{max{2t1,t1+2t2}-1} contains a monochromatic copy of T. The proof works by a stability dichotomy: if the colouring is not close to either of those extremal colourings, a regularity-based argument embeds T; if it is close, separate extremal theorems still embed T using structure of the tree and sparse random choices. Since the theorem holds for every tree meeting","pith_inferences":["The constant c is produced by hierarchy arguments and is almost certainly not optimal; a natural next step is to determine the largest c for which the formula survives, with known double-star examples bounding any possible c by 7/11+o(1).","The unstated starting lemma of the stability part, if true, is a reusable 'remembered clusters' version of the 2002 proof; formalising it could simplify future exact Ramsey results that work with a one-vertex deficit.","The sparse-cut and random leaf-embedding techniques in the extremal part may apply to other spanning tree problems in graphs that are almost complete or almost complete bipartite under a few forbidden edges."],"forward_implications":["For every tree with maximum degree at most cn, the Ramsey number is read off from two integers t1,t2 rather than from the tree's shape.","The 1974 formula is exact for all small-linear-degree trees, so any counterexample to the conjecture must have maximum degree exceeding the fixed constant c.","The stability theorem gives a usable dichotomy: non-extremal colourings on exactly the conjectured number of vertices force a monochromatic copy of the tree.","The extremal lemmas show that colourings approximating the two extremal constructions still contain the tree, despite a known obstruction that makes naive embedding fail."],"supporting_citations":[{"why":"supplies the lower-bound constructions and the conjecture that the max formula is tight for every tree","marker":"[5]"},{"why":"contains the 2002 asymptotic upper bound whose proof is the starting point for the stability part via the extracted structure","marker":"[21]"},{"why":"gives double-star counterexamples showing the conjecture fails for large maximum degree and motivating the small-degree restriction","marker":"[17]"},{"why":"gives strong double-star lower bounds that imply c cannot exceed 7/11+o(1)","marker":"[29]"},{"why":"provides an example where an almost-complete cluster with an extra vertex still fails to contain a spanning tree, shaping the extremal-case analysis","marker":"[23]"},{"why":"records the explicit 2020 question answered in the positive by Theorem 1.1","marker":"[34]"}],"fun_headline_variants":["Exact tree Ramsey numbers for low max degree","Tree Ramsey formula proven for small linear degree","Low-degree trees get exact Ramsey bound","Burr's tree conjecture holds for low degree","Ramsey numbers of low-degree trees are exact"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The stability part starts from a version of the 2002 asymptotic proof that is asserted, not derived here, to produce the scaled-down structure while remembering the unused regularity clusters; if that extraction fails, the whole four-stage argument has no foundation.","fun_headline_variants_meta":{"raw":{"variants":["Exact tree Ramsey numbers for low max degree","Tree Ramsey formula proven for small linear degree","Low-degree trees get exact Ramsey bound","Burr's tree conjecture holds for low degree","Ramsey numbers of low-degree trees are exact"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000799,"raw_usage":{"total_tokens":3327,"prompt_tokens":695,"completion_tokens":2632,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":439,"completion_tokens_details":{"reasoning_tokens":2578}},"tokens_in":439,"tokens_out":2632,"duration_ms":22381,"temperature":1.0,"reasoning_tokens":2578,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T21:28:22.451967+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Apply the 2002 proof to an explicit red/blue colouring of K_{t1+2t2-1} with t1≈2t2 and check whether the asserted starting structure appears: clusters of sizes m and (t1/t2)m, three equal parts each covering about (1−2ε)t2 vertices, a perfect matching, and a vertex joined to one side. Any colouring whose reduced graph cannot be partitioned this way while leaving the leftover clusters regular would invalidate the stability start. Alternatively, one counterexample tree with Δ(T)≤cn and R(T) > max{2t1, t1+2t2}−1 would directly falsify Theorem 1.1.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the lower-bound constructions and the conjecture that the max formula is tight for every tree"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"contains the 2002 asymptotic upper bound whose proof is the starting point for the stability part via the extracted structure"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives double-star counterexamples showing the conjecture fails for large maximum degree and motivating the small-degree restriction"},{"cited_title":"Koml´ os, G","cited_arxiv_id":null,"evidence_quote":"provides an example where an almost-complete cluster with an extra vertex still fails to contain a spanning tree, shaping the extremal-case analysis"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"records the explicit 2020 question answered in the positive by Theorem 1.1"}],"review_version":1}