{"id":"731fd4fd-adb2-49b2-85c2-95fdb4dbd383","arxiv_id":"2507.11860","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For quasi-double stars W_{h,k} with 1≤h≤2≤k≤5, the paper proves planar Turán bounds of 3(h+k)/(h+k+2)n for h+k≤5, and two-sided bounds of 5/2 n and 17/6 n for larger cases.","lead":"This paper gives upper and lower bounds on the maximum number of edges in a planar graph that avoids a quasi-double star subgraph, for small parameter values. The results extend recent work on double stars and include several exact bounds where the graph size is divisible by a fixed number.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The theorem's unconditional lower bounds are false for small n: 9/4 n ≤ ex_P(n,W_{2,4}) and 5/2 n ≤ ex_P(n,W_{2,5}) fail at n=4, since no 4-vertex graph contains these 9- and 10-vertex caterpillars and the planar maximum is 3n−6=6. The proof only gives constructions for n divisible by 8 (resp.","rationale":"The reader's weakest assumption is exactly the load-bearing concern: the lower-bound construction is limited to n divisible by the block size, while the theorem states the lower bounds unconditionally, and the inequalities are false for small n. I checked that the claimed counterexample is immediate: n=4 gives ex_P=6, below both 9/4 n and 5/2 n. The upper-bound proofs are lengthy and I found no equally clear defect; the h=2,k=5 case has intricate notation, but the lower-bound failure independently forces the theorem to be reworded. The reader's CONDITIONAL verdict is therefore appropriate: the upper bounds may be correct, but the theorem as stated is not. I would not change the reader's judgment, only emphasize that the divisibility restriction must appear in every lower-bound statement, not merely in the equality clauses.","tokens_in":14727,"tokens_out":12612,"duration_ms":138059,"concrete_test":"Evaluate the claimed lower bounds at n=4. Since W_{2,4} has 9 vertices and W_{2,5} has 10 vertices, every 4-vertex graph is free of both, so ex_P(4,W_{2,4})=ex_P(4,W_{2,5})=3·4−6=6. The theorem asserts lower bounds 9 and 10, respectively, giving an immediate counterexample. To check whether a corrected asymptotic claim could be salvaged, test the smallest remainder cases: compute or construct planar W_{2,4}-free (resp. W_{2,5}-free) graphs on n=9,10,11,13,14,15 and compare their edge counts with 9/4 n and 5/2 n; if the ratio is not attained for all these n, the unconditional inequalities cannot be restored without floors.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.2 parts 2 and 3 assert lower bounds for every n: 9/4 n ≤ ex_P(n,W_{2,4}) and 5/2 n ≤ ex_P(n,W_{2,5}). The only lower-bound constructions supplied are disjoint unions of a maximal planar graph on h+k+2 vertices (giving 9/4 n when 8 | n for W_{2,4}) and of the 12-vertex 5-regular triangulation (giving 5/2 n when 12 | n for W_{h,5}). No construction is provided for remainder classes, and the proof does not address them. The universal statements are not merely unproved; they are false. For n=4, W_{2,4} has 9 vertices and W_{2,5} has 10 vertices, so every 4-vertex planar graph is H-free and ex_P(4,H)=3·4−6=6. Yet the theorem claims ex_P(4,W_{2,4}) ≥ 9 and ex_P(4,W_{2,5}) ≥ 10. Thus the abstract and Theorem 1.2 overclaim. The upper-bound arguments appear substantive and may survive intact, but the lower-bound assertions must be restricted to the stated divisibility classes (or to an asymptotic/floor formulation). This is a statement-level correctness defect rather than a flaw in the upper-bound machinery.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the planar Turán number ex_P(n, W_{h,k}) of the (h,k)-quasi-double star W_{h,k}, defined as a path P_3 with h leaves attached to one endpoint and k leaves to the other, for 1 ≤ h ≤ 2 ≤ k ≤ 5. Theorem 1.2 claims: for 3 ≤ h+k ≤ 5, the upper bound ex_P(n, W_{h,k}) ≤ 3(h+k)/(h+k+2) n holds for all n, with equality when (h+k+2) | n; for h+k = 6, the two-sided bounds 9/4 n ≤ ex_P(n, W_{h,k}) ≤ 5/2 n hold, with equality in the right inequality when 12 | n and (h,k) = (1,5); and 5/2 n ≤ ex_P(n, W_{2,5}) ≤ 17/6 n. The upper bounds are proved by induction combined with a detailed analysis of degree classes, planarity, and K_{3,3}-freeness, with a separate long case analysis for W_{2,5}. The lower bounds are explicit constructions: disjoint unions of maximal planar graphs on h+k+2 vertices give the tight bounds in part 1 and the 9/4 n bound, and disjoint copies of the 12-vertex 5-regular triangulation give the 5/2 n bound.","tokens_in":15029,"tokens_out":47817,"duration_ms":455639,"significance":"If the statements are corrected, the paper gives tight or near-tight planar Turán numbers for a natural subclass of caterpillars, extending the recent line of work on double stars. The upper-bound proofs are detailed, self-contained, and appear sound; the derivations are parameter-free with explicit constants, and the final case analysis for W_{2,5} in Section 3.3 is substantial. The lower-bound constructions are simple, explicit, and yield exact values on arithmetic progressions of n. The main defect, identified below, is an overclaim in the universal statements of the lower bounds; this is a statement-level error rather than a flaw in the upper-bound machinery, and it is readily repairable by restricting the lower bounds to the congruence classes for which constructions are provided.","major_comments":[{"comment":"Theorem 1.2(2) and (3) assert the lower bounds 9/4 n ≤ ex_P(n, W_{h,k}) for h+k = 6 and 5/2 n ≤ ex_P(n, W_{2,5}) for every n, but the proofs supply constructions only when n is divisible by the block size: n a multiple of 8 for the 9/4 n bound and n a multiple of 12 for the 5/2 n bound. The unconditional statements are false. For n = 4, the graphs W_{2,4} and W_{2,5} have 9 and 10 vertices, respectively, so every planar graph on 4 vertices is H-free for H equal to either of these, and ex_P(4, W_{2,4}) = ex_P(4, W_{2,5}) = 3·4 − 6 = 6, whereas the theorem claims ex_P(4, W_{2,4}) ≥ 9 and ex_P(4, W_{2,5}) ≥ 10. More generally, the 9/4 n lower bound fails for 4 ≤ n ≤ 7 and the 5/2 n lower bound fails for 4 ≤ n ≤ 11, since in that range ex_P(n, H) cannot exceed the planar upper bound 3n − 6, which is smaller than the claimed lower bounds. The same overclaim appears in the abstract and in the sentence 'In particular, we have ex_P(n, W_{2,4}) ≥ 9/4 n' in Section 3, which follows the divisibility-restricted construction without restating the condition 8 | n. The statements should be restricted to the congruence classes for which constructions are given, or replaced by an asymptotic or floor formulation with the missing argument supplied.","section":"Theorem 1.2(2)-(3), Abstract, Section 3 lower-bound paragraph"},{"comment":"The lower-bound gap is not merely a small-n artifact. Because the constructions are disjoint unions of fixed blocks (maximal planar graphs on h+k+2 vertices and the 12-vertex 5-regular triangulation), they produce edge counts only at multiples of 8 (for 9/4 n) and multiples of 12 (for 5/2 n). For every other n, no lower-bound argument is provided, and the paper invokes no monotonicity, vertex-insertion, or residue-class extension argument. Thus the asserted inequalities 9/4 n ≤ ex_P(n, W_{h,k}) and 5/2 n ≤ ex_P(n, W_{2,5}) are unproven for all non-divisible n, even for large n, and the phrase 'tight bounds' in the abstract is stronger than what is established. The authors must either supply an extension argument for the remaining residue classes or weaken the statements accordingly.","section":"Section 3, lower-bound constructions"}],"minor_comments":[{"comment":"The notation 'S_x ∪ S[xy]' in Claim 3 and in the subsequent edge-counting display appears to be missing an overline: given the convention 'For any ∅ ⊂ T ⊂ V(G), we denote T := V(G) \\ T' introduced at the start of Section 3, the intended object is 'S_x ∪ \\overline{S[xy]}', the union of S_x with the complement of S[xy]. As typeset, 'S_x ∪ S[xy]' equals S[xy] because S_x is already contained in S[xy], which makes the claim confusing.","section":"Section 3.3, Claim 3"},{"comment":"The displayed bound 'e[S_xy, S_x ∪ S_y ∪ S[xy]] ≤ (6 − 2)|S_xy| = 4|S_xy|' is inconsistent with the bound e[S_xy, V(G)] ≤ 6|S_xy| used in the very next display. The later bound is the valid one (each vertex of S_xy has degree at most 6 and contributes at most all of its incident edges), but the intermediate claim as stated needs correction or deletion.","section":"Section 3.3, after Claim 3"},{"comment":"The sentence 'Then V_i ≠ ∅ for 3 ≤ i ≤ 6 and V_i = ∅ otherwise' should presumably assert only that every degree lies in {3,4,5,6}, i.e., V_i = ∅ for i outside that range. As written it claims each degree class V_3, V_4, V_5, V_6 is nonempty, which need not hold for an arbitrary extremal graph.","section":"Section 3.2"},{"comment":"In the final edge count of Section 3.3, the simplified expression should be 17/6 n + (|S'| + 7|S_y| − 29)/6; the typeset line '17/6 n + |S'| + 7|S_y| − 29/6' is missing the division by six. Correspondingly, the next line should read 17/6 n + (11/12)|S_y| − 17/6 rather than 17/6 n + (11/2)|S_y| − 17/6. The final conclusion e(G) < 17/6 n is unaffected once the division is restored.","section":"Section 3.3, final calculation"},{"comment":"Theorem 1.1 is quoted with statements 'for n ≥ 1' such as ex_P(n, S_{2,3}) = 2n, which appear to fail for n smaller than the order of the double star (e.g., n = 4 gives a planar upper bound of 6 < 8). The authors may wish to clarify the convention on the range of n in lower-bound statements, and to state their own new results so that the quantifier over n is unambiguous.","section":"Section 1, Theorem 1.1"}],"recommendation":"major_revision","confidential_remarks":"The overclaim is confined to the statement of the lower bounds and is easily repaired by restricting those bounds to the stated divisibility classes or by adding a residue-class extension argument; the upper-bound proofs, which form the main technical contribution, appear sound and are not affected. I found no circularity: the arguments are self-contained and rely only on standard lemmas. The main remaining risk is the intricate local case analysis in Sections 3.1–3.3, which I checked at the level of the counting identities and the degree-class invariants; the decomposition in Section 3.3 is an identity that does not require S[xy] to be a component, so the proof there is on solid ground. The paper is publishable in this journal after a major revision addressing the quantifier issue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"New upper bounds for planar Turán numbers of quasi-double stars W_{h,k} are real, but the lower-bound statements in Theorem 1.2 overclaim and need a divisibility restriction.\n\nThe paper's actual contribution is the upper-bound work. The family W_{h,k} (a P3 with h leaves on one end and k on the other) has not been treated before, and the paper proves ex_P(n,W_{h,k}) ≤ 3(h+k)/(h+k+2)n for h+k=3,4,5, ex_P(n,W_{1,5}) ≤ 5/2 n, and ex_P(n,W_{2,5}) ≤ 17/6 n, plus intermediate bounds for W_{2,4}. The proofs are genuinely structural: Lemmas 2.2-2.4 control the neighbourhood of high-degree vertices, and the case analysis in Sections 3.1-3.3 is detailed and largely coherent. I did not find a gap in the upper-bound chain. The paper is self-contained, uses only standard planar graph facts, and has no fitted parameters or circular citations. That is solid, reproducible-style work.\n\nThe soft spot is the lower-bound half, and it is load-bearing. Theorem 1.2 parts 2 and 3 state, for all n, that ex_P(n,W_{2,4}) ≥ 9/4 n and ex_P(n,W_{2,5}) ≥ 5/2 n. The constructions are disjoint unions of maximal planar graphs on h+k+2 vertices (for the 3(h+k)/(h+k+2)n bounds) and of the 12-vertex 5-regular triangulation (for the 5/2 n bounds). These only apply when (h+k+2)|n and 12|n respectively. No remainder cases are handled. Worse, the universal statements are false: for n=4, W_{2,4} has 9 vertices and W_{2,5} has 10 vertices, so every 4-vertex planar graph is H-free and ex_P(4,H)=6, while 9/4*4=9 and 5/2*4=10. The same issue affects the equalities in part 1: equality is claimed only when divisibility holds, which is fine, but the lower-bound direction of part 1 is implicitly only for that case, which matches the construction. The abstract repeats the overclaim.\n\nThis is fixable. Restrict the lower bounds to the divisibility classes, or restate them with floors or as asymptotic statements. The upper bounds survive untouched. The h=2,k=5 proof has a dense case analysis with a 'remainder' step in Claim 6 that I found terse but correct; the reader's note about an unhandled range in 3.3 did not materialize for me, so I would not ask for substantial rework there.\n\nWho is this for? Researchers working on planar Turán numbers of trees. It is a modest extension of the double-star catalogue, not a new method. But it is a genuine new application of the established approach, and the upper bounds deserve a serious referee. I would send it out, with the expectation that the authors correct the lower-bound statements before acceptance.","headline":"New upper bounds for planar Turán numbers of quasi-double stars are real, but the stated lower bounds overclaim and need a divisibility restriction.","tokens_in":15584,"tokens_out":2677,"would_cite":false,"duration_ms":27444,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C10","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves planar Turán-number bounds for every quasi-double star $W_{h,k}$ with $1\\le h\\le 2\\le k\\le 5$, giving sharp values whenever a divisibility condition holds and narrowing the other cases to explicit intervals.","keywords":["planar Turán number","quasi-double star","caterpillar","extremal graph theory","planar graph","H-free graph","double star","tight bound"],"falsifier":"For $n=4$, the claimed lower bound $\\frac94 n\\le \\mathrm{ex}_{\\mathcal P}(n,W_{2,4})$ would require at least 9 edges, but every planar graph on 4 vertices has at most $3\\cdot 4-6=6$ edges; checking this single case shows the unconditional inequality as stated in the abstract and theorem is false.","tokens_in":14502,"feed_emoji":"🔺","tokens_out":9893,"duration_ms":98704,"temperature":0.7,"pith_summary":"The paper studies the planar Turán number $\\mathrm{ex}_{\\mathcal P}(n,W_{h,k})$: the largest number of edges a planar graph on $n$ vertices can have without containing a quasi-double star $W_{h,k}$, a tree made from a three-vertex path by attaching $h$ leaves to one end and $k$ leaves to the other. For every pair with $1\\le h\\le 2\\le k\\le 5$, it establishes a linear upper bound of the form $c n$, and in the cases $3\\le h+k\\le 5$ the bound is $\\frac{3(h+k)}{h+k+2}n$, attained whenever $n$ is a multiple of $h+k+2$. For the remaining pairs the paper narrows the true value to a short interval: $\\frac94 n\\le \\mathrm{ex}_{\\mathcal P}(n,W_{2,4})\\le \\frac52 n$ and $\\frac52 n\\le \\mathrm{ex}_{\\mathcal P}(n,W_{2,5})\\le \\frac{17}{6}n$, with the sharp upper endpoint for $W_{1,5}$ when $12\\mid n$. A sympathetic reader would care because these are among the first exact or near-exact planar Turán numbers for this caterpillar family, extending the double-star estimates that motivated the problem.","feed_headline":"Planar Turán bounds settled for quasi-double stars","feed_subtitle":"New proof gives exact densities when n is divisible by the block size, and narrow intervals otherwise.","key_machinery":"The load-bearing object is the component neighborhood $S[xy]=N[x]\\cup N(y)$ of an edge $xy$, together with the distance-two absorption lemma: in a $W_{h,k}$-free graph of minimum degree at least $h+1$, if $x$ has degree at least $h+k$, then every vertex at distance two from $x$ has its whole neighborhood inside $N(x)$, so $N[x]\\cup N^2(x)$ is a component. This lets the proof peel off large components and pass to a graph with all degrees in the interval $[h+1,h+k]$, where simple degree counting gives the upper bound; the same structure also supplies the lower bounds, which are unions of disjoint maximal planar graphs on $h+k+2$ vertices (or, for $W_{h,5}$, a 12-vertex 5-regular triangulation).","core_discovery":"On its own terms, the paper proves Theorem 1.2: for $1\\le h\\le 2\\le k\\le 5$, any planar $W_{h,k}$-free graph has at most $\\frac{3(h+k)}{h+k+2}n$ edges when $3\\le h+k\\le 5$, and this is sharp when $(h+k+2)\\mid n$; it also proves $\\mathrm{ex}_{\\mathcal P}(n,W_{1,5})\\le \\frac52 n$, sharp when $12\\mid n$, and $\\frac94 n\\le \\mathrm{ex}_{\\mathcal P}(n,W_{2,4})\\le \\frac52 n$ with $\\frac52 n\\le \\mathrm{ex}_{\\mathcal P}(n,W_{2,5})\\le \\frac{17}{6}n$. The upper bounds come from an induction on $n$ that first removes low-degree vertices, then uses a structural lemma: a vertex of degree at least $h+k+1$ has its closed neighborhood as a component, and an edge with both ends of degree $h+k$ forces the set $N[x]\\cup N(y)$ to be a component. Once the graph is reduced to minimum degree at least $h+1$ and maximum degree at most $h+k$, a degree-sum inequality yields the claimed linear density.","pith_inferences":["One could conjecture that $\\mathrm{ex}_{\\mathcal P}(n,W_{h,k}) = \\lfloor \\frac{3(h+k)}{h+k+2}n\\rfloor + O(1)$ for all $n$ and all $3\\le h+k\\le 5$, with the $O(1)$ term depending on the residue of $n$ modulo $h+k+2$; the divisibility-restricted construction is the natural starting block.","The same component-peeling machinery may apply to other caterpillars $P_\\ell(s_1,\\ldots,s_\\ell)$ with small total leaf number, where the critical degree $h+k$ becomes $\\sum_i s_i$.","A direct way to probe the gap is to compute $\\mathrm{ex}_{\\mathcal P}(n,W_{2,4})$ exactly for $9\\le n\\le 15$; if the density $\\frac94$ is already exceeded for some $n$ not divisible by 8, the true linear coefficient is strictly larger than $\\frac94$.","The matching interval endpoints for $W_{2,5}$ and for the double star $S_{2,5}$ suggest that quasi-double stars inherit the extremal behavior of their double-star counterparts."],"forward_implications":["For $3\\le h+k\\le 5$, the exact density of planar $W_{h,k}$-free graphs is $\\frac{3(h+k)}{h+k+2}$ whenever $n$ is divisible by $h+k+2$, so extremal graphs can be built from disjoint copies of triangulations on $h+k+2$ vertices.","For $W_{1,5}$, the upper endpoint $\\frac52 n$ is attained by disjoint copies of a 12-vertex 5-regular triangulation, fixing the exact value for $n\\equiv 0\\pmod{12}$.","For $W_{2,4}$, the true planar Turán number lies between $\\frac94 n$ and $\\frac52 n$; the paper does not decide which linear density is correct.","For $W_{2,5}$, the true value lies between $\\frac52 n$ and $\\frac{17}{6}n$.","Since the upper bounds are proved for all $n$ while the lower bounds are only shown on divisibility classes, the paper establishes that every one of these planar extremal densities is linear with a rational coefficient."],"supporting_citations":[{"why":"Supplies the planar edge bounds $e(G)\\le 3n-6$ and $e(G)\\le 2n-4$ used in Lemma 2.1 and throughout the component-counting arguments.","marker":"[1]"},{"why":"Establishes the planar Turán number problem for cycles and supplies the framework of extremal planar $H$-free graphs that this paper extends to quasi-double stars.","marker":"[2]"},{"why":"Gives the double-star estimates that motivate and are extended by the quasi-double-star results, especially the matching interval endpoints for $W_{2,5}$.","marker":"[6]"},{"why":"Introduces caterpillars, the class of trees to which quasi-double stars belong.","marker":"[9]"}],"fun_headline_variants":["Planar Turán bounds for quasi-double stars sharpened","Quasi-double stars: planar Turán numbers narrowed","Planar Turán for quasi-double stars: near-tight bounds","Planar Turán constraints for quasi-double stars firmed up"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound constructions are only shown to work when $n$ is divisible by the block size ($h+k+2$ vertices for the tight cases and 12 vertices for $W_{h,5}$), yet the theorem states lower bounds such as $\\frac94 n\\le \\mathrm{ex}_{\\mathcal P}(n,W_{2,4})$ for every $n$, with no construction for the remaining residue classes.","fun_headline_variants_meta":{"raw":{"variants":["Planar Turán bounds for quasi-double stars sharpened","Quasi-double stars: planar Turán numbers narrowed","Planar Turán for quasi-double stars: near-tight bounds","Planar Turán constraints for quasi-double stars firmed up"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001408,"raw_usage":{"total_tokens":5771,"prompt_tokens":1107,"completion_tokens":4664,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":723,"completion_tokens_details":{"reasoning_tokens":4591}},"tokens_in":723,"tokens_out":4664,"duration_ms":36866,"temperature":1.0,"reasoning_tokens":4591,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:01:59.156934+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $n=4$, the claimed lower bound $\\frac94 n\\le \\mathrm{ex}_{\\mathcal P}(n,W_{2,4})$ would require at least 9 edges, but every planar graph on 4 vertices has at most $3\\cdot 4-6=6$ edges; checking this single case shows the unconditional inequality as stated in the abstract and theorem is false.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the planar Turán number problem for cycles and supplies the framework of extremal planar $H$-free graphs that this paper extends to quasi-double stars."},{"cited_title":"Harary and A","cited_arxiv_id":null,"evidence_quote":"Introduces caterpillars, the class of trees to which quasi-double stars belong."}],"review_version":1}