The Tur\'{a}n number of the Cartesian product of a star and an edge
Pith reviewed 2026-05-10 16:28 UTC · model grok-4.3
The pith
The Turán number ex(n, B_t) for B_t = K_2 □ S_t satisfies 1/(2√2) ≤ lim ex(n, B_t)/√t ≤ 1/2 as t → ∞, with matching bipartite bounds and sharper constants when t = 2.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The authors prove that for every t ≥ 2 one has 1/(2√2) ≤ liminf_{t→∞} ex(n, B_t)/√t ≤ limsup_{t→∞} ex(n, B_t)/√t ≤ 1/2 together with the bipartite inequalities 1/4 ≤ lim ex_bip(n, B_t)/√t ≤ 1/(2√2). For B_2 they obtain the sharper statements (0.518 + o(1)) n^{3/2} ≤ ex(n, B_2) ≤ (0.603 + o(1)) n^{3/2} and the corresponding bipartite interval (0.385 + o(1)) n^{3/2} ≤ ex_bip(n, B_2) ≤ (0.468 + o(1)) n^{3/2}. In addition, for any tree T with t edges the bipartite Turán number satisfies ex_bip(n, K_2 □ T) ≤ (√t / (2√2)) (1 + o(1)) n^{3/2}. The lower bounds are obtained by taking random subgraphs of extremal C_4-free graphs; the upper bounds follow from double counting or deletion arguments.
What carries the argument
The graph B_t = K_2 □ S_t (equivalently, t copies of C_4 sharing a single edge), together with random subgraphs of maximum C_4-free graphs on n vertices for the lower bounds and standard counting or deletion methods for the upper bounds.
If this is right
- ex(n, B_t) = Θ(√t n^{3/2}) for every fixed t as n → ∞
- ex_bip(n, B_t) = Θ(√t n^{3/2}) with a strictly smaller leading coefficient than the non-bipartite case
- For B_2 the constants are pinned to roughly 0.518–0.603 (general) and 0.385–0.468 (bipartite)
- For any tree T with t edges, ex_bip(n, K_2 □ T) ≤ (√t / (2√2)) (1 + o(1)) n^{3/2}
Where Pith is reading between the lines
- The leading coefficient may be determined by the maximum density of a C_4-free graph that can be made B_t-free by random deletion; improving known C_4-free constructions could tighten the lower bound.
- The same random-subgraph technique might extend to other Cartesian products K_2 □ H when H is a sparse graph whose extremal number is governed by C_4-free graphs.
- If the upper bound of 1/2 is sharp, there would exist a sequence of B_t-free graphs whose edge count reaches half the square root of t times the C_4-extremal density.
Load-bearing premise
A random subgraph of a maximum C_4-free graph on n vertices must contain no copy of B_t while retaining a positive fraction of the edges with high probability.
What would settle it
A C_4-free graph on n vertices whose largest B_t-free subgraph has more than (1/2) √t n^{3/2} edges for arbitrarily large t would falsify the claimed upper limit on the limsup.
Figures
read the original abstract
Let $C_k$ denote the cycle of length $k$, $S_t$ be a star with $t$ edges. And let $B_t$ be the graph consisting of $t$ copies of $C_4$ sharing one fixed edge. Equivalently, $B_t=K_2 \mathbin{\square} S_t$, which is the Cartesian product of a star with $t$ edges and an edge. Recently, Gao, Janzer, Liu and Xu [\textit{Israel J. Math. 269(2025)}] proved that the Tur\'an number of $K_2\mathbin{\square} C_{2l}$ is $\Theta(n^{\frac{3}{2}})$ for every $l\ge 4$. In this paper, we obtain upper and lower estimates for the Tur\'an number of $B_t$ in both the general and bipartite settings for every $t\geq 2$. For the lower bound, we use random construction based on the extremal structure of $C_4$. These results imply that $\frac{1}{2\sqrt{2}}\leq \lim_{t\to \infty} \frac{\mathrm{ex}(n,B_t)}{\sqrt{t}}\leq \frac{1}{2}$, and $\frac{1}{4}\leq \lim_{t\to \infty} \frac{\mathrm{ex}_{bip}(n,B_t)}{\sqrt{t}}\leq \frac{1}{2\sqrt{2}}.$ In the case of $B_2$, we obtain sharper estimates. We show that the Tur\'an number of $B_2$ is approximately between $(0.518+o(1))n^{\frac{3}{2}}$ and $(0.603+o(1))n^{\frac{3}{2}}$. And in the bipartite setting, it is approximately between $(0.385+o(1))n^{\frac{3}{2}}$ and $(0.468+o(1))n^{\frac{3}{2}}$. Moreover, in the bipartite setting, we give a more general result, which shows that for every tree $T$ with $t$ edges, the bipartite Tur\'an number of $K_2\mathbin{\square}T$ is at most $\frac{\sqrt{t}}{2\sqrt{2}}(1+o(1))n^{\frac{3}{2}}$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Turán number ex(n, B_t) where B_t = K_2 □ S_t consists of t copies of C_4 sharing a common edge. It establishes upper and lower bounds on ex(n, B_t) and the bipartite variant ex_bip(n, B_t) for t ≥ 2, yielding the asymptotic sandwich 1/(2√2) ≤ lim_{t→∞} ex(n, B_t)/√t ≤ 1/2 and 1/4 ≤ lim_{t→∞} ex_bip(n, B_t)/√t ≤ 1/(2√2). Sharper explicit constants are given for B_2: (0.518 + o(1))n^{3/2} ≤ ex(n, B_2) ≤ (0.603 + o(1))n^{3/2} and (0.385 + o(1))n^{3/2} ≤ ex_bip(n, B_2) ≤ (0.468 + o(1))n^{3/2}. A general upper bound ex_bip(n, K_2 □ T) ≤ (√t / (2√2))(1 + o(1))n^{3/2} is proved for any tree T with t edges. The lower bounds rely on random subgraphs of C_4-extremal graphs; the upper bounds use combinatorial counting and deletion arguments.
Significance. If the claimed constants hold, the work supplies the first asymptotic determination of the leading coefficient for this family of Cartesian products and extends the recent Θ(n^{3/2}) result of Gao–Janzer–Liu–Xu for K_2 □ C_{2l}. The general tree upper bound is a clean structural statement that may apply to other degenerate extremal problems. The explicit numerical constants for B_2 are concrete and falsifiable, strengthening the paper’s contribution beyond pure existence results.
major comments (2)
- [Lower bounds section (proof of Theorem 1.1 / 1.3)] Lower-bound construction for liminf ex(n, B_t)/√t ≥ 1/(2√2): the random subgraph of an extremal C_4-free graph on n vertices is claimed to retain (1/(2√2) + o(1))√t n^{3/2} edges after removal of all B_t copies. The manuscript must explicitly verify that the expected number of B_t copies is o(√t n^{3/2}) or that a local-lemma / alteration argument removes only o(√t n^{3/2}) edges; otherwise the leading coefficient drops below 1/(2√2) and the claimed limit fails. The same verification is required for the bipartite lower bound of 1/4.
- [Upper bounds section (proof of Theorem 1.2)] Upper bound for ex(n, B_t) ≤ (1/2 + o(1))√t n^{3/2}: the double-counting or deletion argument used to bound the number of B_t copies must be checked for hidden t-dependent factors. If the constant 1/2 is obtained only after absorbing terms that grow with t, the claimed limsup may be strictly smaller than 1/2.
minor comments (2)
- [Introduction] Notation: the symbol B_t is introduced both as t copies of C_4 sharing an edge and as K_2 □ S_t; a single sentence equating the two definitions would prevent any ambiguity.
- [B_2 section] The numerical constants 0.518, 0.603, 0.385, 0.468 for B_2 are stated without indicating whether they arise from explicit optimization or from solving a small linear program; adding one sentence on their provenance would improve reproducibility.
Simulated Author's Rebuttal
We thank the referee for the careful reading of our manuscript and for the constructive major comments. We address each point below and indicate the revisions we will make to strengthen the presentation.
read point-by-point responses
-
Referee: [Lower bounds section (proof of Theorem 1.1 / 1.3)] Lower-bound construction for liminf ex(n, B_t)/√t ≥ 1/(2√2): the random subgraph of an extremal C_4-free graph on n vertices is claimed to retain (1/(2√2) + o(1))√t n^{3/2} edges after removal of all B_t copies. The manuscript must explicitly verify that the expected number of B_t copies is o(√t n^{3/2}) or that a local-lemma / alteration argument removes only o(√t n^{3/2}) edges; otherwise the leading coefficient drops below 1/(2√2) and the claimed limit fails. The same verification is required for the bipartite lower bound of 1/4.
Authors: We appreciate this observation. The lower-bound construction in Section 3 takes a random subgraph of a C_4-extremal graph with edge density chosen so that the expected number of edges is asymptotically (1/(2√2))√t n^{3/2}. We have now inserted an explicit calculation of the expected number of B_t copies: because the host graph is C_4-free, each potential B_t is determined by a small number of paths of length 3, and the retention probability p satisfies p^5 = o(1/√t) uniformly in the relevant range. Consequently the expectation is o(√t n^{3/2}). A simple deletion step that removes one edge from each surviving copy therefore deletes only o(√t n^{3/2}) edges in total. The same explicit expectation bound and deletion argument will be added for the bipartite construction. These additions confirm that the leading coefficient is preserved. revision: yes
-
Referee: [Upper bounds section (proof of Theorem 1.2)] Upper bound for ex(n, B_t) ≤ (1/2 + o(1))√t n^{3/2}: the double-counting or deletion argument used to bound the number of B_t copies must be checked for hidden t-dependent factors. If the constant 1/2 is obtained only after absorbing terms that grow with t, the claimed limsup may be strictly smaller than 1/2.
Authors: We have re-checked the counting argument in Section 4. The number of B_t copies is bounded by summing, over all edges e, the number of ways to choose t length-3 paths that share the two vertices of e but are otherwise edge-disjoint. This yields at most O(m^2 / n) · (m/n)^t or an analogous expression whose t-powers are controlled by the choice of deletion threshold. Solving the resulting inequality for m produces m ≤ (1/2)√t n^{3/2} + o(√t n^{3/2}), where the o(1) term tends to zero as n → ∞ independently of t (the t-factors appear only as multiplicative constants absorbed into the leading 1/2). We will add a short paragraph that tracks the constants explicitly and states that the o(1) is uniform in t, thereby confirming that the limsup is indeed 1/2. revision: partial
Circularity Check
No significant circularity; bounds derived from external C4 results and standard probabilistic methods
full rationale
The derivation chain relies on the known extremal function ex(n,C4) (external to this paper) for the lower-bound random construction, combined with standard first-moment or deletion arguments to avoid B_t copies. Upper bounds follow from double-counting or Zarankiewicz-type estimates without parameter fitting to the target ex(n,B_t). The cited Theta(n^{3/2}) result for K2□C_{2l} is from independent authors (Gao et al.). No step reduces a claimed prediction to a fitted input by construction, no self-citation is load-bearing for the central limits, and no ansatz or uniqueness theorem is smuggled from prior work by these authors. The sharper B2 estimates and general tree upper bound are obtained directly from the same external base without circular reduction.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Known asymptotic for ex(n, C_4) = Θ(n^{3/2})
Reference graph
Works this paper leans on
-
[1]
Noga Alon, Michael Krivelevich, and Benny Sudakov,Turán numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput.12(2003), 477– 494, Special issue on Ramsey theory
work page 2003
- [2]
-
[3]
Domagoj Bradač, Oliver Janzer, Benny Sudakov, and István Tomon,The Turán num- ber of the grid, Bulletin of the London Mathematical Society55(2023), no. 1, 194–204
work page 2023
-
[4]
Brown,On graphs that do not contain a Thomsen graph, Canad
William G. Brown,On graphs that do not contain a Thomsen graph, Canad. Math. Bull.9(1966), 281–285
work page 1966
-
[5]
Paul Erdős and Tibor Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar.10(1959), 337–356
work page 1959
-
[6]
Sós,On a problem of graph theory, Studia Sci
Paul Erdős, Alfred Rényi, and Vera T. Sós,On a problem of graph theory, Studia Sci. Math. Hungar.1(1966), 215–235
work page 1966
-
[7]
Paul Erdős and Miklós Simonovits,A limit theorem in graph theory, Studia Sci. Math. Hungar.1(1966), 51–57
work page 1966
-
[8]
Paul Erdős and Arthur Stone,On the structure of linear graphs, Bull. Amer. Math. Soc.52(1946), 1087–1091
work page 1946
-
[9]
Genghua Fan and Lingli Sun,The Erdős–Sós conjecture for spiders, Discrete Math. 307(2007), 3055–3062
work page 2007
-
[10]
Zoltán Füredi and Miklós Simonovits,The history of degenerate (bipartite) extremal graph problems, Erdős Centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Mathematical Society, Budapest, 2013, pp. 169–264
work page 2013
-
[11]
Jun Gao, Oliver Janzer, Hong Liu, and Zixiang Xu,Extremal number of graphs from geometric shapes, Israel J. Math.269(2025), 761–799
work page 2025
-
[12]
Philip Hall,On representatives of subsets, J. Lond. Math. Soc.10(1935), 26–31
work page 1935
-
[13]
Sós, and Pál Turán,On a problem of K
Tamás Kővári, Vera T. Sós, and Pál Turán,On a problem of K. Zarankiewicz, Colloq. Math.3(1954), 50–57
work page 1954
-
[14]
Willem Mantel,Problem 28, Wiskundige Opgaven10(1907), 60–61
work page 1907
-
[15]
Michael Mörs,A new result on the problem of Zarankiewicz, Journal of Combinatorial Theory, Series A31(1981), no. 2, 126–130
work page 1981
-
[16]
István Reiman,Über ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar. 9(1958), 269–279
work page 1958
-
[17]
Benny Sudakov and István Tomon,Turán number of bipartite graphs with noKt,t, Proc. Amer. Math. Soc.148(2020), 2811–2818
work page 2020
-
[18]
Pál Turán,On an extremal problem in graph theory, Mat. Fiz. Lapok48(1941), 436– 452, (in Hungarian)
work page 1941
-
[19]
Mariusz Woźniak,On the Erdős–Sós conjecture, J. Graph Theory21(1996), 229–234. 23
work page 1996
-
[20]
Long-Tu Yuan and Xiao-Dong Zhang,Extremal graphs for even linear forests in bi- partite graphs, Discuss. Math. Graph Theory44(2024), 5–16. 24
work page 2024
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.