REVIEW 2 major objections 5 minor 17 references
Planar Tur\'an number of quasi-double stars
T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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).
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (2)
- [Theorem 1.2(2)-(3), Abstract, Section 3 lower-bound paragraph] 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 3, lower-bound constructions] 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.
minor comments (5)
- [Section 3.3, Claim 3] 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 3.3, after Claim 3] 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 3.2] 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 3.3, final calculation] 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 1, Theorem 1.1] 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.
Circularity Check
No significant circularity: the bounds are derived from structural lemmas and explicit constructions, not from the target values.
full rationale
The paper's upper bounds are self-contained derivations from structural lemmas about planar W_{h,k}-free graphs, the Euler bound, K_{3,3}-freeness, induction, and degree-sum/charging arguments; the constants 3(h+k)/(h+k+2), 5/2, and 17/6 arise naturally from these arguments rather than being fitted to the claimed conclusions. The lower bounds are supplied by explicit constructions: disjoint unions of maximal planar graphs on h+k+2 vertices and the 5-regular triangulation on 12 vertices. No fitted parameter is renamed as a prediction, and no load-bearing step relies on a self-citation: the cited double-star results are contextual and are not used to derive the new bounds. The noted divisibility restriction on the lower-bound constructions is a statement-level correctness concern about the universal quantifier, not an instance of circularity, because the construction is independent of the upper-bound machinery and the claimed inequality is not used to define the bound. Therefore the derivation chain is not circular.
Assumptions & free parameters
assumptions (3)
- standard math Euler's formula: every simple planar graph has e ≤ 3n-6 (and e ≤ 2n-4 if bipartite)
- standard math Planar graphs are K_{3,3}-free
- standard math Induction on the number of vertices n for the upper bounds
Cite this review
Pith. "Pith review of Planar Tur\'an number of quasi-double stars." pith.science (2026). https://pith.science/paper/XP6PFPWZ
@misc{pith2026250711860,
author = {Pith},
title = {Pith review of: Planar Tur\'an number of quasi-double stars},
year = {2026},
howpublished = {\url{https://pith.science/paper/XP6PFPWZ}},
note = {Machine review of arXiv:2507.11860}
}
abstract
Given a graph H, we call a graph $\textit{H-free}$ if it does not contain H as a subgraph. The planar Tur\'an number of a graph H, denoted by $ex_{\mathcal{P}}(n, H)$, is the maximum number of edges in a planar H-free graph on n vertices. A (h,k)-quasi-double star $W_{h,k}$, obtained from a path $P_3=v_1v_2v_3$ by adding h leaves and k leaves to the vertices $v_1$ and $v_3$, respectively, is a subclass of caterpillars. In this paper, we study $ex_{\mathcal{P}}(n,W_{h,k})$ for all $1\le h\le 2\le k\le 5$, and obtain some tight bounds $ex_{\mathcal{P}}(n,W_{h,k})\leq\frac{3(h+k)}{h+k+2}n$ for $3\le h+k\le 5$ with equality holds if $(h+k+2)\mid n$, and $ex_{\mathcal{P}}(n,W_{1,5})\le \frac{5}{2}n$ with equality holds if $12\mid n$. Also we show that $\frac{9}{4}n\le ex_{\mathcal{P}}(n,W_{2,4})\le \frac{5}{2}n$ and $\frac{5}{2}n\le ex_{\mathcal{P}}(n,W_{2,5})\le \frac{17}{6}n$, respectively.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
J. A. Bondy and U. S. R. Murty.Graph theory. Springer Publishing Company, Incorporated, 2008
2008
-
[2]
C. Dowden. ExtremalC 4-free/C5-free planar graphs.Journal of Graph Theory, 83(3):213–230, 2016
work page 2016
-
[3]
L. Fang, H. Lin, and Y. Shi. Extremal spectral results of planar graphs without vertex-disjoint cycles.Journal of Graph Theory, 106(3):496–524, 2024
work page 2024
-
[4]
L. Fang, B. Wang, and M. Zhai. Planar Tur´ an number of intersecting triangles. Discrete Mathematics, 345(5):112794, 2022
work page 2022
- [5]
- [6]
-
[7]
D. Guan, E. Gy˝ ori, D. Luong-Le, F. Wang, and M. Yang. The planar Tur´ an number of Θ 6-graphs.arXiv preprint arXiv:2406.19584, 2024
work page Pith review arXiv 2024
-
[8]
E. Gy˝ ori, A. Li, and R. Zhou. The planar Tur´ an number of the seven-cycle. arXiv preprint arXiv:2307.06909, 2023. 17
arXiv 2023
Show all 17 references
-
[9]
Harary and A
F. Harary and A. J. Schwenk. The number of caterpillars.Discrete Mathemat- ics, 6(4):359–365, 1973
1973
-
[10]
Lan and Y
Y. Lan and Y. Shi. Planar Tur´ an numbers of short paths.Graphs and Com- binatorics, 35:1035–1049, 2019
2019
-
[11]
Y. Lan, Y. Shi, and Z.-X. Song. Planar Tur´ an numbers of cubic graphs and disjoint union of cycles.Graphs and Combinatorics, 40(2):28, 2024
2024
-
[12]
Liu and S
D. Liu and S. Xu. An upper bound for the planar Tur´ an number of double starS 3,5.arXiv preprint arXiv:2503.03487, 2025
2025 arXiv
-
[13]
R. Shi, Z. Walsh, and X. Yu. Planar Tur´ an number of the 7-cycle.European Journal of Combinatorics, 126:104134, 2025
2025
-
[14]
X. Xu, Y. Hu, and X. Zhang. An improved upper bound for planar Tur´ an number of double starS 2,5.Discrete Applied Mathematics, 358:326–332, 2024
2024
-
[15]
Xu and J
X. Xu and J. Shao. The planar Tur´ an number of double starS 2,4.Discrete Mathematics, 348(11):114571, 2025
2025
-
[16]
X. Xu, X. Zhang, and J. Shao. Planar Tur´ an number of double starS3,4.AIMS Mathematics, 10(1):1628–1644, 2025
2025
-
[17]
X. Xu, Q. Zhou, T. Li, and G. Yan. Planar Tur´ an number for balanced double stars.arXiv preprint arXiv:2406.05758, 2024. 18
2024 arXiv
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.