The Turan number of the balanced double star S_{n-1,n-1} in the hypercube Q_n

Dandan Liu; Shoujun Xu

REVIEW 4 major objections 5 minor 11 references

The Turan number of the balanced double star S_{n-1,n-1} in the hypercube Q_n

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every $n \ge 3$, the densest subgraph of the hypercube $Q_n$ containing no balanced double star $S_{n-1,n-1}$ has exactly $2^{n-3}(4n-3)$ edges, and the paper proves this bound is both necessary and attainable.

desk verdict The lower-bound construction is nice and the formula is plausible, but the upper bound rests on an unproved assertion, so Theorem 1.1 is not established as written. read the letter →

arxiv 2505.05264 v1 pith:OMQNKUR2 submitted 2025-05-08 math.CO

Shoujun Xu , Dandan Liu This is my paper · ORCID

classification math.CO MSC 05C35

keywords TuránnumberbalanceddoublestarhypercubeH-freesubgraphextremalgraphtheorydegreeconditionexactvalue

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper determines the exact Turán number of the balanced double star $S_{n-1,n-1}$ in the $n$-dimensional hypercube $Q_n$: every subgraph that contains no copy of this tree has at most $2^{n-3}(4n-3)$ edges, and there are subgraphs attaining exactly this many, for every $n \ge 3$. The forbidden tree, the double star, is obtained from an edge by attaching $n-1$ further leaves to each endpoint. The key reduction is that in the bipartite hypercube adjacent vertices share no common neighbour, so a copy of the double star appears exactly when the subgraph contains an edge whose two endpoints both have the maximum possible degree $n$; the extremal problem then asks how many edges can be kept while keeping all degree-$n$ vertices mutually non-adjacent. The paper proves the answer by an inductive construction that pairs two extremal subgraphs across the two halves of $Q_{n+1}$, together with an induction for the upper bound. This is the first exact Turán number for a double star in a hypercube, a family whose planar versions have been studied but whose hypercube behaviour was previously open, and one of the few exact answers in a subject where even the four-cycle problem still has only bounds.

What carries the argument

The load-bearing mechanism is the translation of the forbidden double star into a degree condition: since adjacent vertices in $Q_n$ share no common neighbour, a subgraph contains $S_{n-1,n-1}$ exactly when it has an edge joining two vertices of degree $n$, the maximum possible degree. The Turán problem thereby becomes a constrained subgraph problem that the paper handles by induction on dimension, using the factorization $Q_{n+1} = Q_n \times K_2$. The construction step pairs two extremal graphs of $Q_n$ that have disjoint full-degree vertex sets, one in each half of $Q_{n+1}$, and adds all $2^n$ intercube edges; the disjointness guarantees no intercube edge joins two vertices that both reach degree $n+1$. The upper-bound step partitions the surviving vertices of one half into three classes $R_1, R_2, R_3$ according to which cube-edges and intercube-edges are retained, and asserts that any surplus edge must fall in $R_2$ and create two adjacent vertices of degree $n+1$, that is, an $S_{n,n}$.

What would settle it

A direct computer check at $n=4$ would settle the theorem: search subgraphs of $Q_4$ (16 vertices, 32 edges) for one with 27 edges in which no edge joins two vertices of degree 4; existence refutes $\mathrm{ex}(Q_4, S_{3,3}) = 26$, while a maximum of 26 corroborates the construction and the induction base. Such a search can be posed as an integer program or SAT instance with degree-4 variables and a clause forbidding adjacency between two degree-4 endpoints. The $n=3$ case (claimed maximum 9 of 12 edges) is small enough to check exhaustively by the same formulation.

Watch

Extended reading notes

Core claim

Theorem 1.1 states that $\mathrm{ex}(Q_n, S_{n-1,n-1}) = 2^{n-3}(4n-3)$ for every $n \ge 3$, with the special values $0$ for $n=1$ and $2$ for $n=2$. Because $Q_n$ has $n \cdot 2^{n-1}$ edges, this is equivalent to saying that every $S_{n-1,n-1}$-free subgraph must delete at least $3 \cdot 2^{n-3}$ edges, and that a construction deleting exactly that many exists. The paper's core observation is that adjacent vertices of the hypercube have no common neighbour, so the double star is present precisely when an edge joins two vertices of the maximum possible degree $n$; the extremal problem therefore reduces to keeping the full-degree vertices pairwise non-adjacent while maximizing edges. The proof shows that a maximum-edge solution can be assumed to have minimum degree $n-1$; that there are two extremal subgraphs $G_n$ and $G'_n$ with no vertex of degree $n$ common to both; and that placing these two in the two copies of $Q_n$ inside $Q_{n+1} = Q_n \times K_2$, with all $2^n$ intercube edges present, yields extremal subgraphs in the next dimension with $2^{n-2}(4(n+1)-3)$ edges. The upper bound is proved by induction on $n$ through the same two-copy split.

Load-bearing premise

The whole upper bound rests on the structural claim, called Subclaim 1 inside Claim 2.3, that no matter which edges between the two halves of $Q_{n+1}$ are deleted, a subgraph that still has too many edges must contain two adjacent vertices of degree $n+1$; the paper states this via a partition of vertices into three classes but gives no derivation of the partition's decisive properties, so the induction collapses if some deletion pattern escapes it.

Editorial extensions

If this is right

The bound is sharp in both directions: keeping more than $2^{n-3}(4n-3)$ edges forces an $S_{n-1,n-1}$, while deleting exactly the complementary $3 \cdot 2^{n-3}$ edges is always possible.
The extremal density is $1 - 3/(4n)$, so a subgraph can keep a fraction tending to 1 of the hypercube's edges while still avoiding a double star whose two wings both have size $n-1$.
For every $n \ge 3$ there are at least two distinct extremal subgraphs, and any maximum-edge $S_{n-1,n-1}$-free subgraph of $Q_n$ can be assumed to have minimum degree exactly $n-1$.
Instantiating the formula gives $\mathrm{ex}(Q_3, S_{2,2}) = 9$ and $\mathrm{ex}(Q_4, S_{3,3}) = 26$, concrete values that anchor the induction and can be checked directly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The reduction 'no two full-degree vertices adjacent' suggests the template extends to nearby double stars $S_{k,l}$: exact values would then be governed by how many degree-$n$ vertices a subgraph can carry with no adjacent pair, a question that is computable in small dimensions and might yield a closed formula for a whole family.
The assembly rule — two extremal graphs with disjoint full-degree sets, one per half of $Q_{n+1}$, plus all cross edges — is a general recipe for degree-constrained Turán problems on Cartesian products; grids and toruses are the natural places to test it next.
Nothing in the proof rules out extremal graphs beyond the two constructed ones; a symmetry classification of the 26-edge subgraphs of $Q_4$ would show whether the construction undercounts the extremal family.
The contrast with the even-cycle problems, where only asymptotic bounds are known, points to a rough heuristic: for trees anchored on one central edge, the extremal number in a bipartite host is set by the local degree budget rather than by isoperimetric density.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the honest read. The paper takes a natural question—the Turan number of a balanced double star in the hypercube—and proposes a clean formula, 2^{n-3}(4n-3). The lower-bound construction in Claim 2.2 is genuinely nice: take two copies of extremal Q_n subgraphs on opposite facets, add all 2^n cross edges, and rely on the condition that no two corresponding vertices are both of full degree. That construction is plausible, and the n=3 base case can be checked by hand, so the lower bound likely holds.

The problem is the upper bound. Claim 2.3 is the whole game, and its Subclaim 1 essentially asserts the induction step: any edge-deleted subgraph of Q_{n+1} with more than the claimed number of edges must contain S_{n,n}, for arbitrary deletion patterns on the cross edges. The proof of that subclaim is a terse partition into R1/R2/R3 with no quantitative counting, no derivation that the extra edge forces two adjacent degree-(n+1) vertices, and no account of how deleting cross edges lowers degrees inside each copy. The phrase "regardless of how edges are removed" is exactly what needs proof, not something you can assume. So as written, Theorem 1.1 is not established.

There are smaller issues too. Claim 2.1's degree-raising transformation is handwavy about why it never creates two adjacent full-degree vertices, and the n=3 upper bound in Claim 2.3 has a couple of "necessarily contains" steps that would need a careful case check. The citation pattern is fine: the authors correctly separate planar double-star results from hypercube cycle results, and the exact value they claim does look new.

For a reader working on hypercube Turan problems, the lower-bound construction is worth knowing, and this paper is a good cautionary example of an induction step being asserted rather than proved. It deserves a serious referee, because the formula may well be true and the lower-bound idea is reusable, but it needs major revision with a complete proof of Claim 2.3 before it can be accepted.

Referee Report

4 major / 5 minor

Summary. The paper studies the Turán number ex(Q_n, S_{n-1,n-1}) of the balanced double star in the n-dimensional hypercube and claims the exact value 2^{n-3}(4n-3) for all n≥3, with small values for n=1,2. The lower bound is constructed inductively by combining two extremal graphs in the two copies of Q_n inside Q_{n+1}. The upper bound is attempted by induction: the base case n=3 is analyzed by a degree-sum argument, and the induction step is delegated to 'Subclaim 1,' which asserts that any subgraph of Q_{n+1} with more than 2^{n-2}(4(n+1)-3) edges must contain S_{n,n} regardless of how intercube edges are deleted. The paper concludes Theorem 1.1 by combining the lower-bound construction, an upper-bound claim, and a preliminary minimum-degree transformation.

Significance. If the claimed value were established, this would be a clean exact result in the relatively sparse literature on Turán numbers of trees in hypercubes, complementing existing work on even cycles. The lower-bound construction is a genuine contribution and, subject to verification of the base case, appears plausible. However, the upper-bound proof is not a proof: the key subclaim is asserted rather than derived, so the main theorem is currently unsupported. The paper does not include machine-checked proofs or reproducible code, and the figures essential to the lower-bound base case are not included in the text.

major comments (4)

[§2, Claim 2.3, Subclaim 1] Subclaim 1 is the entire induction step for the upper bound, yet its proof is a qualitative sketch: the partition of the left copy into R1/R2/R3 is not defined in terms of the actual deletion set, and the two crucial assertions—that an additional edge can only be added to R2 and that this forces two adjacent vertices of degree n+1 in R2—are stated without proof or counting. No inequality involving the deletion parameter r is given, and the right copy is not analyzed. As written, Subclaim 1 merely restates what must be proved, so Claim 2.3 and Theorem 1.1 do not follow from the text.
[§2, Claim 2.3, part (2)] The induction hypothesis cannot be applied to the left copy Gn when intercube edges are deleted: Gn need not be S_{n-1,n-1}-free, because an S_{n-1,n-1} inside Gn would extend to S_{n,n} only if the two relevant cross edges to the right copy are still present. The proof never quantifies the deleted intercube edges, so the phrase 'regardless of how edges are removed' is exactly the unproven assertion. This is load-bearing, as it breaks the transfer of the no-deletion argument to the deletion case.
[§2, Claim 2.1] The minimum-degree transformation is not rigorously justified. The proof does not show that deleting p1s1 and adding vp1 preserves S_{n-1,n-1}-freeness in all cases, nor does it handle the situation where multiple vertices achieve the minimum degree t and the selected neighbor p1 changes after each operation. Since the final proof of Theorem 1.1 uses Claim 2.1 to assume δ(G_n)=n−1, this gap propagates to the upper-bound argument.
[§2, Claim 2.3, base case n=3] The base case contains invalid inferences; for example, 'Since all neighbors of u5 in G3 have degree 3, it follows that dG3(u5)=3' does not hold if u5 has few or no neighbors, and the case analysis does not rule out u5 having degree 1 or 2. While the n=3 statement is likely true and could be checked by exhaustive search, the written proof is incomplete.

minor comments (5)

[Abstract] The abstract contains a grammatical error: 'the Turán number of the balanced star Sn,n is has been studied' should be 'has been studied.'
[§1] The notation 'd(x) i.e.|N(v)|' is inconsistent; it should be d(v)=|N(v)|.
[§2, Claim 2.2] The base case of Claim 2.2 is justified only by reference to Figure 1, which is not included in the text; the structural difference between G3 and G′3 should be described explicitly.
[§2, Claim 2.3, Subclaim 1] The sentence 'Suppose that deleting at most r intercube edges in e[Qn,Qn], there is no Sn,n-free subgraph Gn+1⊆Qn+1 with e(Gn+1)≥...' has an unclear quantifier; it should be rephrased as 'there exists an Sn,n-free subgraph' or 'every subgraph contains an Sn,n' to match the intended contradiction.
[§3, Theorem 1.1] The statement of Theorem 1.1 in Section 3 as n×2^{n-1}−3×2^{n-3} is equivalent to 2^{n-3}(4n−3), but the equivalence is not noted, and the two forms appearing in the paper may confuse readers.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular reduction: Theorem 1.1 is not fitted or self-cited; the only concern is an unproved Subclaim 1 in the upper-bound proof, which is a proof gap rather than a circular derivation.

full rationale

The paper does not fit any parameter from the target value, nor does it use the theorem as a premise. Claim 2.2 supplies an explicit 2^{n-3}(4n-3)-edge construction; Claim 2.3 attempts an upper bound by induction. The lower and upper arguments are independent of each other and of the cited planar-Turán literature, so the self-citations are not load-bearing. The one significant issue is in Claim 2.3, Subclaim 1: for the case with deletions in e[Q_n,Q_n], the proof introduces a partition R1/R2/R3 and asserts without derivation that "the additional edge can only be added to R2" and that "no matter how this edge is added, two vertices of degree n+1 in R2 must become adjacent, thereby forming the balanced double star Sn,n". These assertions are effectively the Sn,n-containment statement to be proved, and no computation or previously proved lemma establishes them. That is an omitted proof or unsupported assertion, not a reduction of the conclusion to its own input. Therefore the circularity score is 1 rather than 0, solely as a small burden for relying on unproved scaffolding; it is not a case of self-definitional, fitted, or self-citation circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper is a pure combinatorics proof with no fitted parameters. The main scaffolding consists of three internal claims (minimum-degree reduction, paired lower-bound constructions, and the edge-deletion upper bound); the first and third are not fully proved in the text.

assumptions (4)

standard math Hypercube adjacency and disjointness of the two leaves sets around an edge, meaning N(u) without v and N(v) without u are disjoint.
Used implicitly whenever an edge between two degree-n vertices is identified with S_{n-1,n-1}; follows from the coordinate-flip definition.
domain assumption Maximum-edge S_{n-1,n-1}-free subgraphs can be assumed to have minimum degree n-1 (Claim 2.1).
This reduction is used to set up the partitions in Claim 2.3; the proof contains a non-sequitur and is not fully rigorous.
ad hoc to paper Subclaim 1 in Claim 2.3: any edge-deleted subgraph above the claimed bound forces an S_{n,n} through the R1/R2/R3 partition.
This is the load-bearing upper-bound step; it is stated without a quantitative derivation.
domain assumption The base case n=3 is correct as shown by the figures and the level-set case analysis.
The text's n=3 argument is abbreviated and refers to figures that are not self-contained in the text; a complete finite verification is not written out.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Turan number of the balanced double star S_{n-1,n-1} in the hypercube Q_n." pith.science (2026). https://pith.science/paper/OMQNKUR2

@misc{pith2026250505264,
  author       = {Pith},
  title        = {Pith review of: The Turan number of the balanced double star S_n-1,n-1 in the hypercube Q_n},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OMQNKUR2}},
  note         = {Machine review of arXiv:2505.05264}
}

read the original abstract

The n-dimensional hypercube Q_n is a graph with vertex set {0,1}^n such that there is an edge between two vertices if and only if they differ in exactly one coordinate. Let H be a graph, and a graph is called H-free if it does not contain H as a subgraph. Given a graph H, the Turan number of H in Q_n, denoted by ex(Q_n, H), is the maximum number of edges of a subgraph of Q_n that is H-free. A double star S_{k,l} is the graph obtained by taking an edge uv and joining u with k vertices, v with l vertices which are different from the k vertices. We say a double star is a balanced double star if k = l. Currently, the Turan number of the balanced star S_{n,n} is has been studied in the planar graphs. In the hypercubes, the researchers look for the maximum number of edges of the graphs that are C_k-free. However, the Turan number of the double star in the hypercube remains unexplored. Building upon prior research, we initiate the first study on the Turan number of the balanced double star in the hypercube. In this paper, we give the exact value of the Turan number of the balanced double star S_{n-1,n-1} in the hypercube Q_n, which is 2^{n-3}*(4n- 3) for all n >= 3.

Figures

Figures reproduced from arXiv: 2505.05264 by the authors.

**Figure 1.** G3 and G ′ 3 . (2) Inductive Step. Suppose that the assertion holds for all hypercubes Qt with t ≤ n; that is there exist two distinct St−1,t−1-free subgraphs Gt and G ′ t of Qt after labelling, each attaining the maximal edge count 2t−3 ×(4t −3) , such that no vertex of degree t is common to both Gt and G ′ t . We now consider Qn+1. By the Cartesian product structure Qn+1 = Qn×K2, we extend Gn and G ′ n ⊆ Qn as fol… view at source ↗

**Figure 2.** Gn+1 and G ′ n+1 . e(Gn) = e(G ′ n ) = 2n−3 ×(4n−3). Moreover, after labelling, no vertex of degree n appears in both Gn and G ′ n . And e[Gn,G ′ n ] = 2n . We can add there edges without any constraints. So e(Gn+1) = e(G ′ n+1 ) = (2n−3 × (4n − 3)) ×2+2n = 2n−2 × (4(n + 1) − 3). Then there exist two distinct subgraphs Gn+1 and G ′ n+1 of Qn+1 after labelling that satisfy the conditions. □ Claim 2.3. For any n-dimen… view at source ↗

**Figure 3.** the location of vertices in S. Case 1: There is exactly one vertex in S∩(S0 ∪S3). Assume that u1 ∈ S∩S0, as illustrated in the [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: the edge deletions in e[Qn,Qn]. If we delete one additional edge from e[Qn,Qn], and reintroduce it into the left subgraph Gn ⊆ Qn (see [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: Gn+1 ⊆ Qn+1 with e(Gn+1) ≥ 2 n−2 ×(4(n+1)−3) +1 and e[Qn,Qn]=2n −(r +1). Thus, the additional edge can only be added to R2. However, no matter how this edge is added, two vertices of degree n+1 in R2 must become adjacent, thereby forming the balanced double star Sn,n, …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 6 canonical work pages

[1]

Turán densities of hypercubes

Rahil Baber. Turán densities of hypercubes. arXiv:1201.3587, 2012

arXiv 2012
[2]

Fan R. K. Chung. Subgraphs of a hypercube containing no small even cycles. Journal of Graph Theory, 16(3):273–286, 1992

work page 1992
[3]

Hexagon-free subgraphs of hypercubes

Marston Conder. Hexagon-free subgraphs of hypercubes. Journal of Graph Theory , 17(4):477–479, September 1993

work page 1993
[4]

On some problems in graph theory, combinatorial analysis and combinatorial number theory

Paul Erd ˝os. On some problems in graph theory, combinatorial analysis and combinatorial number theory. Graph Theory Combinatorics, 1-17, 1984

work page 1984
[5]

Planar Turán number of double stars

Debarun Ghosh, Ervin Gy ˝ori, Addisu Paulos, and Chuanqi Xiao. Planar Turán number of double stars. arXiv:2110.10515, October 2021

arXiv 2021
[6]

C10 has positive turán density in the hypercube

Alexandr Grebennikov and João Pedro Marciano. C10 has positive turán density in the hypercube. Journal of Graph Theory, 109(1):31–34, 2025

work page 2025
[7]

An upper bound for the planar Turán number of double star S3,5

Dandan Liu and Shoujun Xu. An upper bound for the planar Turán number of double star S3,5. arXiv:2503.03487, 2025

arXiv 2025
[8]

An improved upper bound for planar Turán number of double star S2,5

Xin Xu, Yue Hu, and Xu Zhang. An improved upper bound for planar Turán number of double star S2,5. Discrete Applied Mathematics, 358:326–332, 2024

work page 2024

Show all 11 references

[9]

The planar Turán number of double star S2,4

Xin Xu and Jiawei Shao. The planar Turán number of double star S2,4. arXiv:2409.01016, September 2024

2024 arXiv
[10]

Planar Turán number of double star S3,4

Xin Xu, Xu Zhang, and Jiawei Shao. Planar Turán number of double star S3,4. AIMS Math- ematics, 10(1):1628–1644, 2025

2025
[11]

Planar turán number for balanced double stars

Xin Xu, Qiang Zhou, Tong Li, and Guiying Yan. Planar turán number for balanced double stars. arXiv:2406.05758, 2024. 6

2024 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Turán densities of hypercubes

Rahil Baber. Turán densities of hypercubes. arXiv:1201.3587, 2012

arXiv 2012

[2] [2]

Fan R. K. Chung. Subgraphs of a hypercube containing no small even cycles. Journal of Graph Theory, 16(3):273–286, 1992

work page 1992

[3] [3]

Hexagon-free subgraphs of hypercubes

Marston Conder. Hexagon-free subgraphs of hypercubes. Journal of Graph Theory , 17(4):477–479, September 1993

work page 1993

[4] [4]

On some problems in graph theory, combinatorial analysis and combinatorial number theory

Paul Erd ˝os. On some problems in graph theory, combinatorial analysis and combinatorial number theory. Graph Theory Combinatorics, 1-17, 1984

work page 1984

[5] [5]

Planar Turán number of double stars

Debarun Ghosh, Ervin Gy ˝ori, Addisu Paulos, and Chuanqi Xiao. Planar Turán number of double stars. arXiv:2110.10515, October 2021

arXiv 2021

[6] [6]

C10 has positive turán density in the hypercube

Alexandr Grebennikov and João Pedro Marciano. C10 has positive turán density in the hypercube. Journal of Graph Theory, 109(1):31–34, 2025

work page 2025

[7] [7]

An upper bound for the planar Turán number of double star S3,5

Dandan Liu and Shoujun Xu. An upper bound for the planar Turán number of double star S3,5. arXiv:2503.03487, 2025

arXiv 2025

[8] [8]

An improved upper bound for planar Turán number of double star S2,5

Xin Xu, Yue Hu, and Xu Zhang. An improved upper bound for planar Turán number of double star S2,5. Discrete Applied Mathematics, 358:326–332, 2024

work page 2024