pith. sign in

arxiv: 2607.01680 · v1 · pith:X6HVUY2Fnew · submitted 2026-07-02 · 🧮 math.CO

On the generalized Tur\'{a}n number of the complete bipartite graph K_(3,b+1)

Jing Wang , Zixuan Yang , Junpeng Zhou This is my paper

Pith reviewed 2026-07-03 11:18 UTC · model grok-4.3

classification 🧮 math.CO
keywords generalized Turán numberextremal graph theorycomplete bipartite graphK_{3,b+1}finite geometryorthogonal polaritypolynomial splitting lemma
0
0 comments X

The pith

For fixed b at least 5 and 3 less than a at most b, ex(n, K_{a,b}, K_{3,b+1}) equals Theta of n cubed.

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

The paper proves that the generalized Turán number ex(n, K_{a,b}, K_{3,b+1}) is Theta of n to the third power when b is at least 5 and a sits between 4 and b. It completes the picture by handling the case of odd b, where earlier results had already settled even b. A sympathetic reader cares because this pins down the growth rate of the maximum number of K_{a,b} subgraphs that can appear in a graph avoiding K_{3,b+1}. The result shows the extremal order stays cubic once the forbidden subgraph reaches K_{3,b+1}.

Core claim

The authors prove that ex(n,K_{a,b},K_{3,b+1})=Θ_{a,b}(n^3) for all fixed integers b≥5 and 3<a≤b. Their construction uses a finite-field point set in PG(5,q) together with an orthogonal polarity. The key new ingredient is the polynomial splitting lemma due to Andrade, Bary-Soroker, and Rudnick, which produces many planes whose intersections with the point set and their polar planes both have size b. This gives a K_{3,b+1}-free incidence graph while preserving Ω_{a,b}(n^3) copies of K_{a,b}.

What carries the argument

Finite-field point set in PG(5,q) with orthogonal polarity, where the polynomial splitting lemma generates planes intersecting both the set and its polar in exactly b points.

If this is right

  • The threshold t equals b+1 now suffices for the Theta(n^3) conclusion in all cases b at least 5.
  • This matches the necessary threshold already known for even b.
  • The incidence graph remains K_{3,b+1}-free while retaining the cubic lower bound on K_{a,b} copies.
  • The same geometric setup works uniformly for both even and odd b once the splitting lemma is applied.

Where Pith is reading between the lines

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

  • The geometric construction may extend to other forbidden bipartite graphs whose size exceeds b+1.
  • Tighter constants in the Theta notation could be obtained by optimizing the choice of q or the point set density.
  • Similar polarity-based arguments might settle analogous generalized Turán problems in higher-dimensional projective spaces.

Load-bearing premise

The polynomial splitting lemma produces sufficiently many planes whose intersections with the chosen point set and its polar plane both have size exactly b, for the parameters needed when b is odd.

What would settle it

A direct count or construction showing that, for some odd b at least 5, the number of planes with the required intersection size b falls below the density needed to reach Omega(n^3) copies of K_{a,b} in the resulting incidence graph.

read the original abstract

For graphs $F$ and $H$, let $\mathrm{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Very recently, Janzer, Longbrake, and Yepremyan proved that for $3<a\leq b$ and sufficiently large $t$, \begin{equation*} \mathrm{ex}(n,K_{a,b},K_{3,t})=\Theta_{a,b,t}(n^3). \end{equation*} Later, Hou, Hu, and Wang made this threshold explicit by showing that the conclusion holds for all $t\geq 2\max\{3,\lceil b/2\rceil\}+1$. In particular, for every even $b\geq 6$, this matches the necessary threshold $t=b+1$. In this paper, we resolve the remaining case where $b$ is odd. More precisely, we prove that for all fixed integers $b\geq 5$ and $3<a\leq b$, \begin{equation*} \mathrm{ex}(n,K_{a,b},K_{3,b+1})=\Theta_{a,b}(n^3). \end{equation*} Our construction uses a finite-field point set in $\mathrm{PG}(5,q)$ together with an orthogonal polarity. The key new ingredient is the polynomial splitting lemma due to Andrade, Bary-Soroker, and Rudnick, which produces many planes whose intersections with the point set and their polar planes both have size $b$. This gives a $K_{3,b+1}$-free incidence graph while preserving $\Omega_{a,b}(n^3)$ copies of $K_{a,b}$.

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

1 major / 1 minor

Summary. The manuscript proves that for all fixed integers b≥5 and 3<a≤b, ex(n,K_{a,b},K_{3,b+1})=Θ_{a,b}(n^3). The upper bound is inherited from prior work on the threshold t; the new contribution is a matching lower bound obtained from an explicit incidence graph on a point set S in PG(5,q) equipped with an orthogonal polarity, where the Andrade–Bary-Soroker–Rudnick polynomial splitting lemma is invoked to produce sufficiently many planes whose intersections with both S and the polar plane have size exactly b.

Significance. If the construction succeeds, the result completes the determination of the precise threshold t=b+1 for which the generalized Turán number ex(n,K_{a,b},K_{3,t}) becomes cubic in n, thereby closing the remaining odd-b case left open by the even-b results of Hou–Hu–Wang. The explicit algebraic construction supplies a concrete, parameter-free lower bound that matches the known upper bound.

major comments (1)
  1. [Lower-bound construction] Lower-bound construction (the section applying the polarity graph): the claim that the splitting lemma produces Ω(q^3) planes P with |P ∩ S|=b and |P^⊥ ∩ S|=b exactly, for odd b≥5 and the chosen point set S, is load-bearing for the Ω(n^3) count of K_{a,b} copies. The manuscript must verify that the degree of the splitting polynomial and the field-size parameter q align so that the produced planes avoid creating a K_{3,b+1} while still yielding the required number of exact-size-b intersections; otherwise the lower bound collapses to o(n^3).
minor comments (1)
  1. [Abstract] The abstract states the result for b odd but does not explicitly recall the matching upper-bound reference (Hou–Hu–Wang) that is used for the Θ statement; adding one sentence would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the focused comment on the lower-bound construction. We address the concern directly below.

read point-by-point responses

  1. Referee: [Lower-bound construction] Lower-bound construction (the section applying the polarity graph): the claim that the splitting lemma produces Ω(q^3) planes P with |P ∩ S|=b and |P^⊥ ∩ S|=b exactly, for odd b≥5 and the chosen point set S, is load-bearing for the Ω(n^3) count of K_{a,b} copies. The manuscript must verify that the degree of the splitting polynomial and the field-size parameter q align so that the produced planes avoid creating a K_{3,b+1} while still yielding the required number of exact-size-b intersections; otherwise the lower bound collapses to o(n^3).

    Authors: We agree that explicit verification of the parameter alignment is necessary for rigor. The point set S consists of the absolute points of a fixed orthogonal polarity in PG(5,q) and therefore has cardinality Θ(q^3). The Andrade–Bary-Soroker–Rudnick lemma is applied to a polynomial whose degree is bounded by a constant depending only on the fixed parameter b (at most 2b in the relevant formulation). Because b is fixed, there exists Q_0 = Q_0(b) such that for all prime powers q > Q_0 the degree condition q > deg holds, and the lemma supplies Ω(q^3) planes P satisfying |P ∩ S| = b and |P^⊥ ∩ S| = b exactly. The incidence graph is defined so that a copy of K_{3,b+1} would require a plane whose intersection with S has size at least b+1; the exact-size-b guarantee therefore ensures the graph remains K_{3,b+1}-free. Each such plane contributes a positive number (depending only on a and b) of K_{a,b} copies, yielding the claimed Ω(n^3) lower bound once n = Θ(q^3). In the revised manuscript we will insert a short dedicated paragraph in the construction section that records the degree bound, the threshold Q_0(b), and the resulting asymptotic count. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit construction via external lemma

full rationale

The paper proves the Θ(n³) bound for odd b by an explicit finite-geometry construction in PG(5,q) together with an orthogonal polarity. The key technical step invokes the Andrade–Bary-Soroker–Rudnick polynomial splitting lemma, which is cited from independent authors and is not derived or fitted inside the present work. No equation or claim reduces by definition to its own inputs, no parameter is fitted on a subset and then renamed a prediction, and no load-bearing uniqueness theorem is imported via self-citation. The derivation therefore remains independent of the target statement.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on standard facts from finite projective geometry (PG(5,q) and orthogonal polarities) and one external lemma; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Properties of the orthogonal polarity on PG(5,q) produce a well-defined incidence graph that is K_{3,b+1}-free when intersections are controlled.
    Invoked in the construction paragraph of the abstract.
  • domain assumption The polynomial splitting lemma applies to the chosen point set and produces the required number of planes with intersection size b.
    Cited as the key new ingredient for the odd-b case.

pith-pipeline@v0.9.1-grok · 5851 in / 1393 out tokens · 23971 ms · 2026-07-03T11:18:54.377327+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

19 extracted references · 5 canonical work pages · 4 internal anchors

  1. [1]

    N. Alon, L. R´ onyai, and T. Szab´ o, Norm-graphs: variations and applications,Journal of Combinatorial Theory, Series B,76(2)(1999), 280–290

    1999

  2. [2]

    Alon and C

    N. Alon and C. Shikhelman, ManyTcopies inH-free graphs,J. Combin. Theory Ser. B,121(2016), 146–172

    2016

  3. [3]

    J. C. Andrade, L. Bary-Soroker, and Z. Rudnick, Shifted convolution and the Titch- marsh divisor problem overF q[t],Philosophical Transactions of the Royal Society A, 373(2015), 20140308

    2015

  4. [4]

    Bayer, T

    T. Bayer, T. M´ esz´ aros, L. R´ onyai, and T. Szab´ o, Exploring projective norm graphs, arXiv preprint arXiv:1908.05190, 2019. 14

    work page arXiv 1908

  5. [5]

    Bollob´ as, Extremal Graph Theory,Courier Corporation, 2004

    B. Bollob´ as, Extremal Graph Theory,Courier Corporation, 2004

    2004

  6. [6]

    Bukh, Extremal graphs without exponentially small bicliques,Duke Mathematical Journal,173(11)(2024), 2039–2062

    B. Bukh, Extremal graphs without exponentially small bicliques,Duke Mathematical Journal,173(11)(2024), 2039–2062

    2024

  7. [7]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits, A limit theorem in graph theory,Studia Scientiarum Mathematicarum Hungaricae,1(1966), 51–57

    1966

  8. [8]

    Erd˝ os and A

    P. Erd˝ os and A. H. Stone, On the structure of linear graphs,Bulletin of the American Mathematical Society,52(1946), 1087–1091

    1946

  9. [9]

    Gerbner, A

    D. Gerbner, A. Methuku, and M. Vizer, Generalized Tur´ an problems for disjoint copies of graphs,Discrete Mathematics,342(11)(2019), 3130–3141

    2019

  10. [10]

    Gerbner and C

    D. Gerbner and C. Palmer, Survey of generalized Tur´ an problems—counting sub- graphs,Electronic Journal of Combinatorics, Dynamic Surveys (2026), #DS27

    2026

  11. [11]

    Gerbner and B

    D. Gerbner and B. Patk´ os, Generalized Tur´ an problems for complete bipartite graphs, Graphs and Combinatorics,38(5)(2022), 164

    2022

  12. [12]

    J. Hou, C. Hu, and H. Wang, Explicit thresholds in a generalized Tur´ an problem for K3,t-free graphs, arXiv preprint arXiv:2606.19217, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  13. [13]

    On the generalized Tur\'an number of complete bipartite graphs

    O. Janzer, S. Longbrake, and L. Yepremyan, On the generalized Tur´ an number of complete bipartite graphs, arXiv preprint arXiv:2606.09801, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  14. [14]

    Koll´ ar, L

    J. Koll´ ar, L. R´ onyai, and T. Szab´ o, Norm-graphs and bipartite Tur´ an numbers,Com- binatorica,16(1996), 399–406

    1996

  15. [15]

    K˝ ov´ ari, V

    T. K˝ ov´ ari, V. T. S´ os, and P. Tur´ an, On a problem of K. Zarankiewicz,Colloquium Mathematicum,3(1954), 50–57

    1954

  16. [16]

    J. Ma, Y. Yuan, and X. Zhang, Some extremal results on complete degenerate hyper- graphs,Journal of Combinatorial Theory, Series A,154(2018), 598–609

    2018

  17. [17]

    $K_{2,t+1}$-free graphs with many copies of $K_{t,t}$

    C. Pohoata, J. Tidor, and H.-H. H. Yu,K 2,t+1-free graphs with many copies ofK t,t, arXiv preprint arXiv:2605.25905, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  18. [18]

    $K_{2, t+1}$-free graphs containing an optimal number of $K_{t, t}$'s

    V. Taranchuk,K 2,t+1-free graphs containing an optimal number ofK t,t’s, arXiv preprint arXiv:2606.02855, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  19. [19]

    Tur´ an, Egy gr´ afelm´ eleti sz´ els˝ o´ ert´ ekfeladatr´ ol,Matematikai ´ es Fizikai Lapok,48 (1941), 436–452

    P. Tur´ an, Egy gr´ afelm´ eleti sz´ els˝ o´ ert´ ekfeladatr´ ol,Matematikai ´ es Fizikai Lapok,48 (1941), 436–452. 15

    1941