{"id":"77ed17ca-1b44-425a-a868-eab07eeecdd8","arxiv_id":"2507.03264","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For n at least 6k^3, every n-vertex graph with minimum degree at least n-k contains every connected n-vertex sparse graph with at most n(1+1/(24k-12)) edges and alpha' at least k-1.","lead":"Two theorems give new Ramsey bounds for sparse connected graphs against stars, generalizing a 1982 tree result. The main consequence is that high minimum degree forces containment of every sparse connected spanning subgraph with bounded maximum degree when n is polynomially large in k.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's reductions change α'(H) without tracking it; bounds from Theorem 4/Lemma 9 use the original α', so the t-star Ramsey upper bound is not established as written.","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap: after the reductions in Theorem 5, the parameter α' is not tracked, and the bounds applied from Theorem 4 and Lemma 9 are only valid with the α' of the reduced graph H. The central Theorem 4 and Corollary 1 appear correct; the issue is confined to the secondary claim about r(G, tK1,k). The concern is genuine but likely patchable, since the numerical slack in n≥28t²k³ may force the reduced graph to retain enough leaves to keep α'(H) ≥ k − 1. Thus the reader's CONDITIONAL verdict is the right one, and no change to that verdict is needed. I agree with the reader's diagnosis and recommend the authors supply the missing α'(H) estimate or adjust the argument in Theorem 5.","tokens_in":12723,"tokens_out":34012,"duration_ms":374827,"concrete_test":"Re-derive Theorem 5, Case 3, replacing α' by α'(H) in the single displayed application of Theorem 4, and check whether the subsequent chain still yields a red H inside U. For the two-hub family G = edge vx plus L leaves at each of v and x, after deleting D = (t−1)k + k² − 2k + 2 leaves from v, compute α'(H) = L − D. Determine whether the hypotheses n ≥ 28t²k³ and the leaf-count lower bound from Lemma 1 force L − D ≥ k − 1. If they do not, the displayed inequality in Case 3 fails for k ≥ 3; if they do, the authors need only add the missing estimate α'(H) ≥ k − 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 5, each case reduces G to a smaller connected graph H — by shortening a suspended path (Case 1) or by deleting end-vertices (Cases 2 and 3) — and then invokes Lemma 9 or Theorem 4 with the original parameter α' = α'(G). For example, Case 3 states r(H, K1,k) ≤ max{n−D, n−D+k−1−α'}, where D = (t−1)k + k² − 2k + 2. But Theorem 4's upper bound is valid with α'(H), not α'(G). The equality H_v = G_v (deleted leaves were neighbors of v) only gives α(H_v) ≥ α'; for w ≠ v, H_w is G_w with those leaves removed, so α(H_w) can drop. The minimum can therefore fall below α'. Concretely, if G is the edge vx with L leaves attached to each of v and x, then α'(G) = L, whereas after deleting D leaves from v, α'(H) = L − D because the vertex x sees only the remaining v-leaves. Hence the displayed bound can be false when L − D < k − 1, and the subsequent embedding of H inside U is not guaranteed. The same tracking issue occurs in Case 1's application of Lemma 9. This does not disprove the theorem, but the proof as written leaves the t-star generalization unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Ramsey numbers r(G,K1,k) for connected sparse graphs G on n vertices with at most n(1+ε) edges, and uses them to embed spanning subgraphs into graphs of minimum degree at least n−k. Theorem 4 gives a tight two-sided bound for r(G,K1,k) in terms of n, k and α′(G), generalizing the tree case of Erdős, Faudree, Rousseau and Schelp. Theorem 5 extends this to an upper bound for r(G,tK1,k). The proofs use a structural trichotomy for sparse graphs (Lemma 1, quoted from a preprint), a reduction lemma (Lemma 8) based on deleting or suppressing low-degree vertices, and case analysis depending on whether G has a long suspended path, a large matching of end-edges, or neither.","tokens_in":13011,"tokens_out":46650,"duration_ms":552372,"significance":"If the results are correct, Theorem 4 is a genuine and useful extension of the classic tree-star Ramsey bounds to sparse connected graphs, and Corollaries 1 and 2 give clean sufficient conditions for embedding sparse spanning subgraphs into graphs with prescribed minimum degree. The lower-bound construction in §2.1 is explicit and convincing, and Lemma 8's induction is sound: the reduction operation for a cut vertex of degree two preserves the degrees of its two neighbors, so the stated number of reductions can indeed be performed. The main caveats are that Theorem 4 depends essentially on the unproved structural lemma from a preprint, and that the proof of Theorem 5 does not track how the parameter α′ changes when the graph is reduced to H. The t-star generalization is therefore not established as written, although the underlying theorem may well be true after a repair.","major_comments":[{"comment":"The upper-bound proof for r(G,tK1,k) reduces G to a smaller connected graph H and then applies Lemma 9 or Theorem 4 using the original parameter α′=α′(G). In Case 1 the proof writes r(H,tK1,k) ≤ max{n−(t−1)k, n−(t−1)k+k−2−α′}+(t−1)(k+1); in Case 2 it writes r(H,K1,k) ≤ max{n−2tk+2, n−2tk+2+k−1−α′}; in Case 3 it writes r(H,K1,k) ≤ max{..., n−D+k−1−α′} with D=(t−1)k+k²−2k+2. In each display the parameter on the right is α′(G), but the lemmas invoked require the corresponding parameter of H. Neither equality of α′ nor an inequality controlling α′(H) is proved. Deleting leaves or shortening a suspended path can change α′ substantially; for instance, if G is the union of two adjacent vertices with L leaves at each vertex, then α′(G)=L, while deleting D leaves adjacent to one vertex lowers α′ to L−D. In Case 1 the displayed expression also appears off by one (the term k−2 should be k−1 to match Lemma 9). The theorem may still be true, but the proof as written leaves the t-star generalization unsupported.","section":"§3, Cases 1–3"},{"comment":"Both main theorems rely in their third case on Lemma 1, the sparse-graph trichotomy of Zhang and Chen [8]. This lemma is quoted from an unreferenced preprint and no proof is included. Since the case analysis is built directly on Lemma 1, the manuscript is not self-contained. The paper should either prove Lemma 1 in an appendix or state explicitly that Theorems 4 and 5 are conditional on [8]. This is a load-bearing dependency, not a cosmetic issue.","section":"§2.2, Case 3 and §3, Case 3"}],"minor_comments":[{"comment":"In the lower-bound proof, the sentence 'Obviously, F contains no K1,k' is false for the graph F defined there; what is needed is that the complement of F contains no K1,k. Also, in the decomposition n+k−2−α′−β=tk+s, the parameter s should be allowed to be 0; the stated range '0<s≤k' excludes the case β=1 and remainder r=1.","section":"§2.1"},{"comment":"The operation of shortening a suspended path is used without a formal definition. The proof later relies on the fact that shortening by d internal vertices reduces the edge count by exactly d; this should be stated explicitly, including the fact that an edge is added between the two remaining endpoints.","section":"§2.2, Case 1"},{"comment":"The concluding remark asserts stronger versions of Theorems 4 and 5 for general constants c, with the phrase 'we can show', but no proof is supplied. These statements should be proved or explicitly labelled as conjectural.","section":"§4"},{"comment":"When n≤2k, the inequality e(G)≤n+2k/(2k+1) together with integrality gives e(G)≤n, but the text simply says that G has at most n edges; spelling out the integrality step would improve clarity.","section":"Lemma 8"}],"recommendation":"major_revision","confidential_remarks":"The central issue is that Section 3 needs a genuine repair, not just a typo: the proof must either prove that α′ does not drop under the reductions, or replace α′ by α′(H) and add the necessary inequalities. I did not find a circularity problem with Lemma 1, since its hypotheses do not involve Ramsey numbers, but the dependence on an unpublished preprint should be resolved before acceptance. The lower-bound construction for Theorem 4 and the overall strategy are sound and likely publishable after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's real content is Theorem 4: for connected n-vertex G with at most n(1+1/(24k-12)) edges and α′(G)=α′, r(G,K1,k) is max{n,n+k−1−α′} up to the usual divisibility adjustment, with n≥6k^3. That genuinely extends the Erdős–Faudree–Rousseau–Schelp tree bound to sparse graphs with a controlled number of extra edges, and the corollary on δ(F)≥n−k forcing sparse connected spanning subgraphs is a clean payoff. I found the proof of Theorem 4 mostly convincing. Lemma 8's reduction argument is careful: the induction tracks edge counts, and the reverse embedding uses the no-blue-star condition with room arithmetic that works. The case division from the trichotomy lemma is natural, and the lower bound construction is valid.\n\nThe soft spot is Theorem 5. After each reduction—shortening a suspended path in Case 1, deleting end-vertices in Cases 2 and 3—the proof invokes Lemma 9 or Theorem 4 with the original α′ of G, not α′ of the reduced graph H. That is not justified. Deleting leaves can drop α(H_w) below α′, so bounds like max{n−2tk+2, n−2tk+2+k−1−α′} may be too small. The stress-test example—a double-star with L leaves at each center, after deleting D leaves adjacent to one center, α′ drops from L to L−D—shows the displayed bound can fail. The same issue appears in Case 1's application of Lemma 9. This does not disprove the theorem, but the proof as written leaves r(G,tK1,k) unsupported.\n\nA second, smaller concern: the key Lemma 1 is quoted from a preprint by two of the authors and not proved here. That is acceptable if the preprint is solid, but it makes Theorem 4's foundation depend on an external unpublished result. The final remark's symbolic calculation also deserves a sanity check before publication.\n\nWho is this for? People working on Ramsey numbers and degree conditions for spanning subgraphs. Theorem 4 is a worthwhile contribution and worth a careful referee. Theorem 5 needs a substantial revision—track α′ through the reductions or prove the needed monotonicity—before the paper is accepted.\n\nRecommendation: send to peer review, yes, but with a request to fix the Theorem 5 gap. If the authors can't, Theorem 4 could stand alone.","headline":"Solid generalization of the tree-star Ramsey theorem with a real gap in the t-star extension; Theorem 4 deserves referee time, Theorem 5 needs a fix.","tokens_in":13519,"tokens_out":2044,"would_cite":false,"duration_ms":21941,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C55","05C35","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"For $n\\ge 6k^3$, an $n$-vertex graph with minimum degree at least $n-k$ contains every sparse connected $n$-vertex graph whose $\\alpha'$ parameter is at least $k-1$.","keywords":["Ramsey number","spanning subgraph","minimum degree","star graph","sparse graph","tree trichotomy","suspended path","matching"],"falsifier":"To test the central reduction, compute $\\alpha'$ for the graph $H$ obtained from a sparse connected $G$ by shortening one suspended path by $2k-2$ vertices; if $\\alpha'(H)<\\alpha'(G)$, substitute $\\alpha'(H)$ into the claimed bound and check whether $r(H,K_{1,k})\\le n$ still follows, since the proof of Case 1 needs exactly that inheritance.","tokens_in":12507,"feed_emoji":"⭐","tokens_out":10241,"duration_ms":105747,"temperature":0.7,"pith_summary":"This paper proves that the classical tree theorem of [5] extends from trees to all sparse connected graphs. The main result is a two-sided bound on the Ramsey number $r(G,K_{1,k})$: for $n\\ge 6k^3$ and a connected $G$ on $n$ vertices with at most $n(1+1/(24k-12))$ edges, the value lies between $\\max\\{n,n+k-1-\\alpha'-\\beta\\}$ and $\\max\\{n,n+k-1-\\alpha'\\}$, where $\\alpha'=\\min_v\\alpha(G-N[v])$ and $\\beta$ is a parity correction. The spanning-subgraph consequence is that every $n$-vertex graph $F$ with minimum degree at least $n-k$ contains every such $G$ with $\\alpha'\\ge k-1$ as a spanning subgraph. A parallel bound is proved for $r(G,tK_{1,k})$, the Ramsey number against $t$ disjoint stars.","feed_headline":"Minimum degree n−k forces every sparse connected graph inside","feed_subtitle":"Once n is at least 6k^3, every n-vertex graph F with minimum degree n−k contains every such G as a spanning subgraph.","key_machinery":"The argument is carried by an enhanced tree trichotomy for sparse graphs, stated as Lemma 1 in [8]. It says that a connected graph on $n$ vertices with $n+\\ell$ edges either has a suspended path of length $q$ (a path whose internal vertices have degree 2), or a matching of $s$ end-edges, or a vertex adjacent to roughly $n/(s-1)$ leaves. Around this, the proof builds a reduction engine: Lemma 8 shows $r(G,K_{1,k})\\le n+2k-2$ for any connected graph with at most $n(1+1/(2k+1))$ edges, by repeatedly deleting or suppressing vertices of degree at most 2 and then extending the embedded smaller graph back using red neighborhoods. In the three cases the proof shortens a suspended path and re-extends it, completes a matching of end-edges via Hall's theorem, or embeds a leaf-heavy graph and uses the large red neighborhood of one vertex; the parameter $\\alpha'(G)$ controls how many vertices of an independent set in $G-N[u]$ must be accounted for when avoiding a blue star.","core_discovery":"Stated on the paper's own terms, the discovery is a tight Ramsey evaluation. For $k\\ge 1$, $n\\ge 6k^3$, and a connected graph $G$ on $n$ vertices with $e(G)\\le n(1+1/(24k-12))$ and $\\alpha'(G)=\\alpha'$, the paper establishes $\\max\\{n,n+k-1-\\alpha'-\\beta\\}\\le r(G,K_{1,k})\\le \\max\\{n,n+k-1-\\alpha'\\}$, with $\\beta=0$ if $k\\mid n+k-2-\\alpha'$ and $\\beta=1$ otherwise. This reproduces, for general sparse connected graphs, the bounds that [5] proved for trees, and it lowers the required size of $n$ from $O(k^3)$ to $6k^3$. When $\\alpha'\\ge k-1$ the bounds collapse to $r(G,K_{1,k})=n$, which is exactly the statement that $\\delta(F)\\ge n-k$ forces $G$ as a spanning subgraph of $F$. For $t$ copies of the star the paper proves $r(G,tK_{1,k})\\le \\max\\{n,n+k-1-\\alpha'\\}+t-1$ for $n\\ge 28t^2k^3$, with equality $n+t-1$ in the case $\\alpha'\\ge k-1$.","pith_inferences":["A reader extending these results should first check whether $\\alpha'$ is monotone under the two reductions used in Theorem 5: deleting end-vertices or shortening a suspended path can in principle shrink $\\alpha'(H)$ below $\\alpha'(G)$, and the proof does not isolate this verification.","The complement encoding suggests a general template: $\\delta(F)\\ge n-k$ is equivalent to $\\overline F$ being $K_{1,k}$-free, so the theorem says a $K_{1,k}$-free complement cannot avoid any sparse connected spanning graph above the threshold; the same strategy could be tried with other fixed graphs replacing the star.","The thresholds $6k^3$ and $28t^2k^3$ appear to be artifacts of the case analysis rather than tight bounds, since the concluding remark already exhibits a parameter tradeoff between $n$ and edge density."],"forward_implications":["For $n\\ge 6k^3$, every $n$-vertex graph $F$ with $\\delta(F)\\ge n-k$ contains every connected $n$-vertex graph $G$ with at most $n(1+1/(24k-12))$ edges and $\\alpha'(G)\\ge k-1$ as a spanning subgraph.","In this range the Ramsey number $r(G,K_{1,k})$ is exactly $n$ when $\\alpha'(G)\\ge k-1$, and in general it lies within $k-1-\\alpha'$ of $n$, matching the earlier tree bound up to the parity term.","If additionally $\\Delta(G)<n(1-1/(24k-12))$, the sparse spanning subgraph is guaranteed even without checking $\\alpha'$, because the average-degree estimate forces $\\alpha'\\ge k-1$.","For $t$ disjoint stars, $r(G,tK_{1,k})\\le n+t-1$ when $\\alpha'(G)\\ge k-1$ and $n\\ge 28t^2k^3$, with equality obtained from the construction $K_{n-1}\\cup K_{t-1}$.","The threshold on $n$ and the allowed edge density trade against each other: with density $n(1+1/(12k-12+24k/c))$ the proof works for smaller $n$, and in the limit $c\\to0^+$ it covers all trees and unicyclic graphs on more than $2k^3+13k^2-40k+25$ vertices."],"supporting_citations":[{"why":"Supplies the sparse-graph trichotomy lemma (Lemma 1) that splits the proof into the suspended-path, end-edge matching, and leaf-heavy cases.","marker":"[8]"},{"why":"The tree case that Theorem 4 extends; its Ramsey bounds and parity term are recovered for general sparse connected graphs.","marker":"[5]"},{"why":"Gives the tree-star bound $r(T,K_{1,k})\\le n+k-1$ used in the base case of the reduction and for unicyclic graphs.","marker":"[2]"},{"why":"Hall's matching theorem is used in Case 2 to force either a red matching of end-edges or a blue star.","marker":"[7]"},{"why":"The original trichotomy for trees motivates the structural case split later refined by [8] for sparse graphs.","marker":"[3]"}],"fun_headline_variants":["High min degree forces every sparse connected graph once n is large","Minimum degree n−k is enough to embed any sparse connected graph","Sparse connected graphs forced by min degree n−k for large n","n−k min degree guarantees all sparse connected graphs when n≥6k^3"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reductions that produce a smaller graph $H$ from $G$, by deleting end-vertices or shortening a suspended path, are applied while keeping the original value $\\alpha'(G)$ in the Ramsey bound for $H$; if $\\alpha'(H)$ can be smaller than $\\alpha'(G)$, those bounds may not hold.","fun_headline_variants_meta":{"raw":{"variants":["High min degree forces every sparse connected graph once n is large","Minimum degree n−k is enough to embed any sparse connected graph","Sparse connected graphs forced by min degree n−k for large n","n−k min degree guarantees all sparse connected graphs when n≥6k^3"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001094,"raw_usage":{"total_tokens":4600,"prompt_tokens":1010,"completion_tokens":3590,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":626,"completion_tokens_details":{"reasoning_tokens":3511}},"tokens_in":626,"tokens_out":3590,"duration_ms":25282,"temperature":1.0,"reasoning_tokens":3511,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:19:30.760799+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To test the central reduction, compute $\\alpha'$ for the graph $H$ obtained from a sparse connected $G$ by shortening one suspended path by $2k-2$ vertices; if $\\alpha'(H)<\\alpha'(G)$, substitute $\\alpha'(H)$ into the claimed bound and check whether $r(H,K_{1,k})\\le n$ still follows, since the proof of Case 1 needs exactly that inheritance.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the tree-star bound $r(T,K_{1,k})\\le n+k-1$ used in the base case of the reduction and for unicyclic graphs."},{"cited_title":"Hall, On representatives of subsets, J","cited_arxiv_id":null,"evidence_quote":"Hall's matching theorem is used in Case 2 to force either a red matching of end-edges or a blue star."}],"review_version":1}