pith. sign in

arxiv: 2606.19217 · v1 · pith:FK6M5GJOnew · submitted 2026-06-17 · 🧮 math.CO

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

Jianfeng Hou , Caiyun Hu , Hezhi Wang This is my paper

Pith reviewed 2026-06-26 20:10 UTC · model grok-4.3

classification 🧮 math.CO
keywords extremal graph theorygeneralized Turán problemK_{3,t}-free graphsexplicit thresholdsfinite-field point setsbipartite extremal functionplane section bounds
0
0 comments X

The pith

For fixed 3 < a ≤ b, ex(n, K_{a,b}, K_{3,t}) equals Θ(n³) once t reaches 2 max{3, ⌈b/2⌉} + 1.

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

The paper establishes an explicit value of t, namely τ(b) = 2 max{3, ⌈b/2⌉} + 1, such that the maximum number of K_{a,b} copies in any n-vertex K_{3,t}-free graph is Θ(n³). This sharpens an earlier result that only guaranteed the cubic order for all sufficiently large t without specifying the cutoff. The argument rests on an explicit finite-field point set whose plane sections are analyzed directly for line and conic intersections to guarantee K_{3,t}-freeness while retaining many coplanar b-sets. A reader cares because the threshold is shown to be tight for every even b at least 6, pinning down exactly where the extremal function attains its cubic growth.

Core claim

The authors prove that for fixed 3 < a ≤ b and all t ≥ τ(b) := 2 max{3, ⌈b/2⌉} + 1, ex(n, K_{a,b}, K_{3,t}) = Θ(n³). In particular the bound is tight for even b ≥ 6. The main new ingredient is an explicit finite-field point set whose plane sections are controlled directly, rather than through a general bounded-complexity algebraic lemma, giving the required K_{3,t}-freeness while preserving many coplanar b-element subsets.

What carries the argument

Explicit finite-field point set whose plane sections have directly bounded line and conic intersections

If this is right

  • The threshold t = b + 1 is both necessary and sufficient when b is even and at least 6.
  • The cubic order ex(n, K_{a,b}, K_{3,t}) = Θ(n³) holds for every explicit t ≥ τ(b).
  • Direct line-and-conic section analysis on the point set suffices to obtain both freeness and the many coplanar b-sets.
  • The same construction works uniformly for all a between 4 and b.

Where Pith is reading between the lines

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

  • The direct-control technique may extend to other generalized Turán problems where algebraic point sets are used.
  • For small fixed b one could computationally enumerate small planes to check whether the intersection bounds are tight.
  • The same finite-field sets might yield explicit thresholds when the forbidden graph is K_{r,t} for r > 3.

Load-bearing premise

The explicit finite-field point set has plane sections whose intersection sizes stay bounded by a function of b that produces K_{3,t}-freeness for t at least τ(b).

What would settle it

A plane section in the finite-field construction that intersects in more points than the bound allows for some even b ≥ 6 and t = τ(b) would collapse the lower-bound construction.

read the original abstract

For graphs $F$ and $H$, let $\ex(n,F,H)$ denote the maximum number of copies of $F$ in an $n$-vertex $H$-free graph. Janzer, Longbrake and Yepremyan recently proved that, for fixed $3<a\le b$ and sufficiently large $t$, \[ \ex(n,K_{a,b},K_{3,t})=\Theta(n^3). \] We make their threshold explicit, showing that this conclusion holds for all $t\ge \tau(b):=2\max\{3,\lceil b/2\rceil\}+1.$ In particular, for every even $b\ge 6$, this matches the necessary threshold $t=b+1$. The main new ingredient is an explicit finite-field point set whose plane sections are controlled directly, rather than through a general bounded-complexity algebraic lemma. This direct line-and-conic section analysis gives the required \(K_{3,t}\)-freeness while preserving many coplanar \(b\)-element subsets.

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

0 major / 2 minor

Summary. The manuscript proves that for fixed 3 < a ≤ b, ex(n, K_{a,b}, K_{3,t}) = Θ(n³) holds for all t ≥ τ(b) := 2 max{3, ⌈b/2⌉} + 1. This makes the 'sufficiently large t' threshold from Janzer-Longbrake-Yepremyan explicit, and for even b ≥ 6 it matches the necessary lower-bound threshold t = b + 1. The proof introduces an explicit finite-field point set in which plane sections are controlled by a direct line-and-conic analysis (rather than a general algebraic lemma) to guarantee K_{3,t}-freeness while retaining sufficiently many coplanar b-sets.

Significance. If the construction succeeds, the result supplies the first explicit threshold in this generalized Turán problem and is tight for even b. The self-contained direct analysis of incidences in finite fields is a methodological strength that avoids black-box algebraic-geometry lemmas and may extend to related extremal problems.

minor comments (2)
  1. §1: the definition of the point set P and the precise bound on |P ∩ π| for planes π should be stated as a numbered claim before the K_{3,t}-freeness argument begins, to make the load-bearing step easier to locate.
  2. The finite-field analysis assumes char(F) > b or similar; a short sentence clarifying the characteristic restriction (if any) would prevent reader uncertainty when b is even.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. The assessment correctly captures the main contribution: an explicit threshold τ(b) that matches the lower bound for even b ≥ 6, achieved via a direct finite-field construction whose plane sections are analyzed explicitly rather than via general algebraic lemmas.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation establishes the explicit threshold τ(b) via a new finite-field point set whose plane sections are bounded by direct line-and-conic counting in the manuscript itself; this counting is presented as self-contained and does not reduce by definition or fitting to the target ex(n,K_{a,b},K_{3,t}) quantity. The prior asymptotic Θ(n³) result is cited from independent authors (Janzer-Longbrake-Yepremyan) and is not load-bearing for the explicit t-threshold. No self-citation chain, ansatz smuggling, or renaming of known results appears in the central construction step.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence and incidence properties of a specific finite-field point set whose plane sections are bounded; these properties are not derived from prior literature but constructed directly in the paper.

axioms (1)
  • standard math Standard facts about finite fields and algebraic curves over them (e.g., number of points on lines and conics).
    Invoked to control intersections in the explicit point set.

pith-pipeline@v0.9.1-grok · 5721 in / 1312 out tokens · 13035 ms · 2026-06-26T20:10:17.277919+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 · 2 linked inside Pith

  1. [1]

    N. Alon, M. Krivelevich, and B. Sudakov. Turán numbers of bipartite graphs and related Ramsey-type questions.Combinatorics, Probability and Computing, 12:477–494, 2003

    2003

  2. [2]

    N. Alon, L. Rónyai, and T. Szabó. Norm-graphs: variations and applications.Journal of Combinatorial Theory, Series B, 76:280–290, 1999

    1999

  3. [3]

    Alon and C

    N. Alon and C. Shikhelman. ManyTcopies inH-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016

    2016

  4. [4]

    W. G. Brown. On graphs that do not contain a thomsen graph.Canadian Mathematical Bulletin, 9:281–285, 1966

    1966

  5. [5]

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

    2015

  6. [6]

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

    2039

  7. [7]

    Dvir and S

    Z. Dvir and S. Lovett. Subspace evasive sets. InSTOC’12–Proceedings of the 2012 ACM Symposium on Theory of Computing, pages 351–358, New York, 2012. ACM

    2012

  8. [8]

    Erdős, A

    P. Erdős, A. Rényi, and V. T. Sós. On a problem of graph theory.Studia Scientiarum Mathematicarum Hungarica, 1:215–235, 1966

    1966

  9. [9]

    Z. Füredi. New asymptotics for bipartite Turán numbers.Journal of Combinatorial Theory, Series A, 75:141–144, 1996

    1996

  10. [10]

    D. Gerbner. Generalized Turán problems forK2,t.Electronic Journal of Combinatorics, 30:Paper No. 1.34, 2023

    2023

  11. [11]

    Gerbner and C

    D. Gerbner and C. Palmer. Survey of generalized Turán problems–counting subgraphs. Electronic Journal of Combinatorics, Dynamic Surveys, page DS27, 2026

    2026

  12. [12]

    Gerbner and B

    D. Gerbner and B. Patkós. Generalized Turán problems for complete bipartite graphs. Graphs and Combinatorics, 38:Paper No. 164, 2022

    2022

  13. [13]

    Győri, J

    E. Győri, J. Pach, and M. Simonovits. On the maximal number of certain subgraphs in Kr-free graphs.Graphs and Combinatorics, 7:31–37, 1991

    1991

  14. [14]

    Janzer, S

    O. Janzer, S. Longbrake, and L. Yepremyan. On the generalized Turán number of complete bipartite graphs, 2026. arXiv:2606.09801. 17

    Pith/arXiv arXiv 2026

  15. [15]

    Kollár, L

    J. Kollár, L. Rónyai, and T. Szabó. Norm-graphs and bipartite Turán numbers.Com- binatorica, 16:399–406, 1996

    1996

  16. [16]

    Kővári, V

    T. Kővári, V. T. Sós, and P. Turán. On a problem of k. zarankiewicz.Colloquium Mathematicum, 3:50–57, 1954

    1954

  17. [17]

    Pohoata, J

    C. Pohoata, J. Tidor, and H.-H. H. Yu.K2,t+1-free graphs with many copies ofKt,t,

  18. [18]

    Pudlák and V

    P. Pudlák and V. Rödl. Pseudorandom sets and explicit constructions of ramsey graphs. InComplexity of Computations and Proofs, volume 13 ofQuad. Mat., pages 327–346. Dept. Math., Seconda Univ. Napoli, Caserta, 2004

    2004

  19. [19]

    Sudakov and I

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

    2024

  20. [20]

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

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

    Pith/arXiv arXiv 2026