pith. sign in

arxiv: 2606.09801 · v1 · pith:ZQCN7VDRnew · submitted 2026-06-08 · 🧮 math.CO · cs.DM

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

Oliver Janzer , Sean Longbrake , Liana Yepremyan This is my paper

Pith reviewed 2026-06-27 15:47 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords generalized Turán numberextremal graph theorycomplete bipartite graphsK_{s,t}-free graphsasymptotic growth ratesex(n,F,H)Spiro conjectures
0
0 comments X

The pith

ex(n, K_{a,b}, K_{s,t}) equals Theta(n^s) for s equal to 2 or 3 when s is less than a and t is large enough.

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

The paper shows that the largest number of K_{a,b} subgraphs inside an n-vertex K_{s,t}-free graph is on the order of n^s, provided s is 2 or 3, a exceeds s, and t is taken sufficiently large. The special case s=2 and a=b=3 resolves a question raised by Spiro. A second result establishes that every graph F containing at least one edge admits infinitely many real exponents r for which there exists some graph H making ex(n,F,H) exactly Theta(n^r). These statements together describe how the asymptotic growth of generalized Turán numbers can be pinned to specific polynomial degrees by suitable choice of the forbidden bipartite graph.

Core claim

We prove that if s∈{2,3}, s<a≤b and t is sufficiently large, then ex(n,K_{a,b},K_{s,t})=Θ(n^s). The s=2, a=b=3 case answers a question of Spiro. Proving another conjecture of Spiro, we show that for every graph F with at least one edge, there exist infinitely many real numbers r such that ex(n,F,H)=Θ(n^r) holds for some graph H.

What carries the argument

The generalized Turán number ex(n,F,H) that records the maximum number of copies of F inside an n-vertex H-free graph.

If this is right

  • The upper and lower bounds on the number of K_{a,b} copies match at order n^s once t exceeds a fixed threshold depending on s,a,b.
  • The extremal function ex(n,K_{a,b},K_{s,t}) is polynomial of exact degree s for the stated range of parameters.
  • For every fixed F with an edge there are infinitely many distinct real numbers r that arise as the growth exponent of ex(n,F,H) for suitable H.
  • The case a=b=3 and s=2 supplies a concrete instance where the growth is exactly quadratic.

Where Pith is reading between the lines

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

  • The result indicates that the possible polynomial degrees realized by generalized Turán numbers include every integer at least 2.
  • One could test whether the same Theta(n^s) statement continues to hold when s exceeds 3 provided t grows with s.
  • The existence of infinitely many r for each F suggests that the set of attainable growth rates is infinite for every fixed F.

Load-bearing premise

The parameter t must be taken sufficiently large.

What would settle it

An explicit family of K_{s,t}-free graphs on n vertices containing more than C n^s copies of K_{a,b} for arbitrarily large C, with t fixed but large, would falsify the claimed upper bound.

read the original abstract

For graphs $F$ and $H$, the generalized Tur\'an number $\mathrm{ex}(n,F,H)$ denotes the maximum number of copies of $F$ in an $H$-free graph on $n$ vertices. We prove that if $s\in \{2,3\}$, $s< a\leq b$ and $t$ is sufficiently large, then $\mathrm{ex}(n,K_{a,b},K_{s,t})=\Theta(n^s)$. The $s=2$, $a=b=3$ case of this result answers a question of Spiro. Proving another conjecture of Spiro, we show that for every graph $F$ with at least one edge, there exist infinitely many real numbers $r$ such that $\mathrm{ex}(n,F,H)=\Theta(n^r)$ holds for some graph $H$.

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 / 0 minor

Summary. The paper proves that if s ∈ {2,3}, s < a ≤ b and t is sufficiently large, then ex(n, K_{a,b}, K_{s,t}) = Θ(n^s), answering a question of Spiro in the case s=2 and a=b=3. It also proves that for every graph F with at least one edge there exist infinitely many real r such that ex(n,F,H)=Θ(n^r) for some graph H.

Significance. If the proofs are complete, the first result supplies the first asymptotic determination of ex(n,K_{a,b},K_{s,t}) for these parameters and the second result shows that the possible growth rates of generalized Turán numbers are dense in the reals, both of which are substantial advances in extremal graph theory.

major comments (1)
  1. [Abstract] Abstract (main theorem statement): the hypothesis that t is 'sufficiently large' is invoked to guarantee that the upper and lower bounds coincide at Θ(n^s), yet no explicit lower bound on t (or dependence on a,b,s) is supplied; without this the claimed asymptotic equality is conditional on an unquantified premise that is load-bearing for the result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed report and for highlighting this point about the abstract. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (main theorem statement): the hypothesis that t is 'sufficiently large' is invoked to guarantee that the upper and lower bounds coincide at Θ(n^s), yet no explicit lower bound on t (or dependence on a,b,s) is supplied; without this the claimed asymptotic equality is conditional on an unquantified premise that is load-bearing for the result.

    Authors: We agree that the abstract would be improved by making the dependence on t explicit. The proof of the upper bound (in Section 3) proceeds by assuming t exceeds a quantity that depends only on a, b, and s (arising from the application of the Kővári–Sós–Turán theorem and a counting argument that requires t large enough to dominate certain binomial coefficients). This quantity can be made fully explicit, though it is rather large. We will revise the abstract to state that the result holds whenever t exceeds an explicit function of a, b, and s, and we will record the precise lower bound in the revised version of the paper. revision: yes

Circularity Check

0 steps flagged

No circularity; independent proofs of external conjectures with standard technical conditions.

full rationale

The paper establishes asymptotic results on generalized Turán numbers ex(n, K_{a,b}, K_{s,t}) under the condition that t is sufficiently large, answering a question of Spiro and proving a conjecture of Spiro on the existence of r for which ex(n,F,H)=Θ(n^r) for some H. No load-bearing steps reduce by definition, fitted parameters, or self-citation chains to the inputs; the derivations are presented as independent proofs. The 'sufficiently large t' premise is a conventional hypothesis to ensure matching upper and lower bounds and does not constitute circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definition of the generalized Turán number ex(n,F,H) and basic facts about graphs and subgraphs; no free parameters, new entities, or ad-hoc axioms appear in the abstract.

axioms (1)
  • standard math Standard definitions and basic properties of graphs, subgraphs, and asymptotic notation in extremal graph theory.
    The paper invokes the established meaning of ex(n,F,H) and the Theta notation without re-deriving them.

pith-pipeline@v0.9.1-grok · 5675 in / 1512 out tokens · 22938 ms · 2026-06-27T15:47:11.987710+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Explicit thresholds in a generalized Tur\'an problem for \(K_{3,t}\)-free graphs

    math.CO 2026-06 unverdicted novelty 6.0

    For 3 < a ≤ b fixed, ex(n, K_{a,b}, K_{3,t}) = Θ(n³) holds for every t ≥ 2 max{3, ⌈b/2⌉} + 1, with the bound tight for even b ≥ 6.

Reference graph

Works this paper leans on

30 extracted references · 2 linked inside Pith · cited by 1 Pith paper

  1. [1]

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

    1999

  2. [2]

    Alon and C

    N. Alon and C. Shikhelman. Many T copies in H-free graphs.Journal of Combina- torial Theory, Series B, 121:146–172, 2016

    2016

  3. [3]

    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

    arXiv 1908

  4. [4]

    B. Bukh. Random algebraic construction of extremal graphs.Bulletin of the London Mathematical Society, 47(6):939–945, 2015

    2015

  5. [5]

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

    2039

  6. [6]

    Bukh and D

    B. Bukh and D. Conlon. Rational exponents in extremal graph theory.Journal of the European Mathematical Society, 20(7):1747–1757, 2018

    2018

  7. [7]

    D. Conlon. Graphs with few paths of prescribed length between any two vertices. Bulletin of the London Mathematical Society, 51(6):1015–1021, 2019

    2019

  8. [8]

    Conlon and O

    D. Conlon and O. Janzer. Rational exponents near two.Advances in Combinatorics, 2022

    2022

  9. [9]

    Conlon, O

    D. Conlon, O. Janzer, and J. Lee. On the extremal number of subdivisions.Combi- natorica, 41:465–494, 2021

    2021

  10. [10]

    English and S

    S. English and S. Spiro. Rational exponents for general graphs.arXiv preprint arXiv:2506.19061, 2025

    arXiv 2025

  11. [11]

    P. Erd˝ os. On the number of complete subgraphs contained in certain graphs.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl, 7(3):459–464, 1962

    1962

  12. [12]

    P. Erd˝ os. On the combinatorial problems which I would most like to see solved. Combinatorica, 1(1):25–42, 1981

    1981

  13. [13]

    Gerbner, A

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

    2019

  14. [14]

    Gerbner and B

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

    2022

  15. [15]

    Hartshorne.Algebraic geometry

    R. Hartshorne.Algebraic geometry. Springer Science & Business Media, 1977

    1977

  16. [16]

    O. Janzer. The extremal number of the subdivisions of the complete bipartite graph. SIAM J. Discrete Math., 34:241–250, 2020

    2020

  17. [17]

    Jiang, J

    T. Jiang, J. Ma, and L. Yepremyan. On Tur´ an exponents of bipartite graphs.Com- binatorics, Probability and Computing, 31(2):333–344, 2022

    2022

  18. [18]

    Jiang and Y

    T. Jiang and Y. Qiu. Tur´ an numbers of bipartite subdivisions.SIAM J. Discrete Math, 34:556–570, 2020. 16

    2020

  19. [19]

    Jiang and Y

    T. Jiang and Y. Qiu. Many Tur´ an exponents via subdivisions.Combin. Probab. Comput., 32:134–150, 2023

    2023

  20. [20]

    D. Y. Kang, J. Kim, and H. Liu. On the rational Tur´ an exponents conjecture. Journal of Combinatorial Theory, Series B, 148:149–172, 2021

    2021

  21. [21]

    Koll´ ar, L

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

    1996

  22. [22]

    K˝ ov´ ari, V

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

    1954

  23. [23]

    J. Ma, X. Yuan, and M. Zhang. Some extremal results on complete degenerate hypergraphs.Journal of Combinatorial Theory, Series A, 154:598–609, 2018

    2018

  24. [24]

    Milojevi´ c, I

    A. Milojevi´ c, I. Tomon, and B. Sudakov. Incidence bounds via extremal graph theory. arXiv preprint arXiv:2401.06670, 2024

    arXiv 2024

  25. [25]

    Pohoata, J

    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

    Pith/arXiv arXiv 2026

  26. [26]

    S. Roman. The maximum number ofq-cliques in a graph with nop-clique.Discrete Mathematics, 14(4):365–371, 1976

    1976

  27. [27]

    S. Spiro. Generalized Tur´ an problems for trees and more. Talk at the Atlanta Lecture Series, 2025

    2025

  28. [28]

    Sudakov and I

    B. Sudakov and I. Tomon. Evasive sets, covering by subspaces, and point-hyperplane incidences.Discrete Comput. Geom., 72:1333–1347, 2024

    2024

  29. [29]

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

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

    Pith/arXiv arXiv 2026

  30. [30]

    A. A. Zykov. On some properties of linear complexes.Matematicheskii sbornik, 66(2):163–188, 1949. 17

    1949