pith. sign in

arxiv: 2604.11366 · v1 · submitted 2026-04-13 · 🧮 math.CO

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

classification 🧮 math.CO MSC 05C35
keywords Turán numberCartesian productC_4-free graphsextremal graph theorybipartite Turán numberstar graphrandom constructionasymptotic bounds
0
0 comments X

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.

The paper establishes asymptotic upper and lower bounds on the Turán number of B_t, the graph formed by t copies of C_4 that all share one common edge. These bounds show that ex(n, B_t) grows as Θ(√t n^{3/2}), with the leading coefficient squeezed between 1/(2√2) ≈ 0.353 and 1/2 in the large-t limit; the bipartite version ex_bip(n, B_t) is squeezed between 1/4 and 1/(2√2). For the specific case t = 2 the authors give numerical constants roughly 0.518 to 0.603 in the general setting and 0.385 to 0.468 in the bipartite setting. They also prove a uniform upper bound for the bipartite Turán number of K_2 □ T when T is any tree with t edges. A reader would care because the results quantify how the extremal density scales with the number of attached C_4's and connect the problem to the well-studied theory of C_4-free graphs.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2604.11366 by Casey Tompkins, Cheng Chi, Ervin Gy\H{o}ri, Xiamiao Zhao, Xin Cheng, Yichen Wang.

Figure 1
Figure 1. Figure 1: The graph Bt = St □ K2. The graph can be viewed as t copies of C4 sharing a common edge. Mantel [14] determined the Turán number of K3. Turán [18] generalized this result by determining ex(n, Kp) for all n and p. Later, Erdős, Stone and Simonovits [7, 8] proved that ex(n, F) is asymptotically determined by the chromatic number χ(F) of F, when χ(F) ≥ 3. Specifically they proved ex(n, F) = 1 2  1 − 1 χ(F) −… view at source ↗
Figure 2
Figure 2. Figure 2: The red edge represents the edge shared by [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: For each vertex v ∈ N2(u), if w ∈ L ′ u\v and w /∈ N1(u), then we can find a B2 Claim 3.2. The graph Guv contains no two independent edges. Proof. Suppose that there are 2 independent edges u1v1 and u2v2 in Guv. Then, there are two copies of C4, uvu1v1 and uvu2v2, which share a common edge uv and form a B2, a contradiction. ■ By Claim 3.2, we can obtain that Guv is a star or a triangle. Let Lv\u = N(v) \ N… view at source ↗
Figure 4
Figure 4. Figure 4: For any two vertices v1, v2 ∈ N2(u), if L ′ u\v1 ∩ L ′ u\v2 ̸= ∅, then we can find a B2 Proof. Suppose that there is a vertex w ∈ L ′ u\v1 ∩ L ′ u\v2 . Let vertex y be the center of star Guv1 , and z be the center of star Guv2 . Suppose that y ̸= z. If v2 ̸= y and v1 ̸= z, then uv1yw and uv2zw form a B2 (see Figure 4a). If v2 = y and v1 ̸= z, then uv1yw and uwzx1 form a B2, where x1 ∈ L ′ u\v2 . If v2 ̸= y… view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. [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

2 responses · 0 unresolved

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
  1. 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

  2. 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

0 steps flagged

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

0 free parameters · 1 axioms · 0 invented entities

The paper relies on the known extremal number of C_4 for its random lower-bound construction and on standard probabilistic and counting lemmas; no new free parameters, axioms, or invented entities are introduced.

axioms (1)
  • standard math Known asymptotic for ex(n, C_4) = Θ(n^{3/2})
    Invoked to build the random lower-bound graphs for ex(n, B_t).

pith-pipeline@v0.9.0 · 5791 in / 1575 out tokens · 74341 ms · 2026-05-10T16:28:36.411102+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [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

  2. [2]

    2, 97–105

    John A Bondy and Miklós Simonovits,Cycles of even length in graphs, Journal of Combinatorial Theory, Series B16(1974), no. 2, 97–105. 22

  3. [3]

    1, 194–204

    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

  4. [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

  5. [5]

    Paul Erdős and Tibor Gallai,On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar.10(1959), 337–356

  6. [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

  7. [7]

    Paul Erdős and Miklós Simonovits,A limit theorem in graph theory, Studia Sci. Math. Hungar.1(1966), 51–57

  8. [8]

    Paul Erdős and Arthur Stone,On the structure of linear graphs, Bull. Amer. Math. Soc.52(1946), 1087–1091

  9. [9]

    307(2007), 3055–3062

    Genghua Fan and Lingli Sun,The Erdős–Sós conjecture for spiders, Discrete Math. 307(2007), 3055–3062

  10. [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

  11. [11]

    Math.269(2025), 761–799

    Jun Gao, Oliver Janzer, Hong Liu, and Zixiang Xu,Extremal number of graphs from geometric shapes, Israel J. Math.269(2025), 761–799

  12. [12]

    Philip Hall,On representatives of subsets, J. Lond. Math. Soc.10(1935), 26–31

  13. [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

  14. [14]

    Willem Mantel,Problem 28, Wiskundige Opgaven10(1907), 60–61

  15. [15]

    2, 126–130

    Michael Mörs,A new result on the problem of Zarankiewicz, Journal of Combinatorial Theory, Series A31(1981), no. 2, 126–130

  16. [16]

    Zarankiewicz, Acta Math

    István Reiman,Über ein Problem von K. Zarankiewicz, Acta Math. Acad. Sci. Hungar. 9(1958), 269–279

  17. [17]

    Benny Sudakov and István Tomon,Turán number of bipartite graphs with noKt,t, Proc. Amer. Math. Soc.148(2020), 2811–2818

  18. [18]

    Pál Turán,On an extremal problem in graph theory, Mat. Fiz. Lapok48(1941), 436– 452, (in Hungarian)

  19. [19]

    Graph Theory21(1996), 229–234

    Mariusz Woźniak,On the Erdős–Sós conjecture, J. Graph Theory21(1996), 229–234. 23

  20. [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