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

Vladislav Taranchuk

arxiv: 2606.02855 · v1 · pith:LFAH2FNCnew · submitted 2026-06-01 · 🧮 math.CO

K_(2, t+1)-free graphs containing an optimal number of K_(t, t)'s

Vladislav Taranchuk This is my paper

Pith reviewed 2026-06-28 13:27 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C35

keywords generalized Turán numberextremal graph theoryK_{t,t} copiesK_{2,t+1}-free graphsfinite field constructionsbipartite extremal problems

0 comments

The pith

When t is a prime power and n equals t to an odd power, the maximum number of K_{t,t} copies in a K_{2,t+1}-free graph on n vertices is asymptotically n squared over 2t times (t-1).

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

The paper determines the precise leading coefficient in the generalized Turán number ex(n, K_{t,t}, K_{2,t+1}) for the case when t is a prime power and n takes the form t to the power 2e minus 1. It does this by exhibiting an explicit construction of a K_{2,t+1}-free graph that contains (1 plus lower order terms) times n squared over 2t(t-1) copies of K_{t,t}. Earlier results had shown only that the quantity is on the order of n squared for all t at least 3, so the new work pins down the constant factor in these special cases. A sympathetic reader would see this as progress toward understanding the exact density of one bipartite subgraph inside another under a forbidden-subgraph constraint.

Core claim

When t is a prime power and n = t^{2e-1}, the generalized Turán number ex(n, K_{t,t}, K_{2,t+1}) equals (1 + o(1)) n² / (2t(t-1)). The paper establishes this equality by means of an explicit construction that produces a K_{2,t+1}-free graph on exactly those n vertices containing the stated number of K_{t,t} copies.

What carries the argument

Explicit algebraic construction, based on finite-field or geometric objects available when t is a prime power, that produces a K_{2,t+1}-free graph on n = t^{2e-1} vertices with asymptotically n²/(2t(t-1)) copies of K_{t,t}.

If this is right

The construction supplies a matching lower bound to the known O(n²) upper bound, fixing the leading coefficient for these parameters.
The same algebraic method yields the extremal function exactly up to the o(n²) term when n is a suitable power of a prime-power t.
The result applies only for t that are prime powers and only for n of the specific form t^{2e-1}.

Where Pith is reading between the lines

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

The same constant factor may hold for all large n even when t is not a prime power, if other constructions can be found.
The approach suggests that the ratio 1/(2t(t-1)) is the natural density limit for K_{t,t} inside K_{2,t+1}-free graphs more generally.
Similar explicit constructions could be tested for other pairs of forbidden bipartite graphs to obtain exact asymptotics.

Load-bearing premise

Suitable finite-field or geometric objects exist that yield the required K_{2,t+1}-free graph precisely when t is a prime power.

What would settle it

Exhibiting even one K_{2,t+1}-free graph on n = t^{2e-1} vertices that contains more than (1 + ε) n² / (2t(t-1)) copies of K_{t,t} for some fixed ε > 0 would show the claimed maximum is too low.

read the original abstract

The generalized Tur\'{a}n number $ex(n, K_{t, t}, K_{2, t+1})$ is the maximum number of copies of $K_{t, t}$ that a $K_{2, t+1}$-free graph on $n$ vertices can contain. Recently, Pohoata, Tidor, and Yu established that $ex(n, K_{t, t}, K_{2, t+1}) = \Theta_t(n^2)$ for all integers $t \geq 3$. In this short note, we use an explicit construction to establish that when $t$ is a prime power and $n = t^{2e - 1}$, then $$ ex(n, K_{t, t}, K_{2, t+1}) = (1 + o(1))\frac{n^2}{2t(t-1)}. $$

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.

Desk Editor's Note private letter to a colleague

This note pins down the leading constant in a special case of the generalized Turán problem using an algebraic construction for prime-power t.

read the letter

This note takes the Θ(n²) upper bound from Pohoata-Tidor-Yu and matches it with a lower bound of (1+o(1)) n² / (2t(t-1)) for n = t^{2e-1} when t is a prime power. The author does this via an explicit construction, most likely based on finite-field geometries or similar algebraic objects that exist only for those t.

The paper does well by supplying the precise constant rather than just the order. Prior work stopped at Θ_t(n²), so this fills in the leading term for an infinite arithmetic progression of n. That is a concrete step forward for anyone tracking these refined extremal numbers.

The main soft spot is the verification of the K_{t,t} count inside the construction. The result stands or falls on whether the edge definition and incidence counting actually produce the claimed number while keeping the graph K_{2,t+1}-free; a small slip in the double-counting would break the constant. The o(1) term as e grows is also tied to the same argument. The limitation to prime-power t is expected and not presented as a flaw.

The citation pattern is clean and direct. No circularity or parameter fitting appears.

This is for people working on generalized Turán problems in extremal graph theory. A reader who already knows the Pohoata-Tidor-Yu paper will get immediate value from the construction details. It deserves a serious referee because the claim is specific, falsifiable, and improves the prior result when the counting holds.

Referee Report

1 major / 1 minor

Summary. The manuscript uses an explicit algebraic construction (available when t is a prime power) to prove that ex(n, K_{t,t}, K_{2,t+1}) = (1 + o(1)) n² / (2t(t-1)) for n = t^{2e-1}, thereby matching the upper bound of Pohoata-Tidor-Yu and establishing the precise leading constant for this infinite family of n.

Significance. If the construction and its K_{t,t}-count are correct, the result supplies the first explicit lower bound achieving the optimal constant in this generalized Turán problem, complementing the known Θ_t(n^{2}) upper bound and adding to the collection of algebraic constructions for Zarankiewicz-type extremal functions.

major comments (1)

The lower bound is load-bearing on the asymptotic count of K_{t,t} copies inside the explicit construction. The manuscript must supply a complete, self-contained derivation of this count (including any incidence or double-counting arguments) that confirms the constant factor 1/(2t(t-1)); an error here would invalidate the claimed equality.

minor comments (1)

The introduction could briefly recall the definition of the generalized Turán number ex(n, H, F) for readers outside the immediate area.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for identifying the need for a fully self-contained derivation of the K_{t,t} count. We address the major comment below.

read point-by-point responses

Referee: The lower bound is load-bearing on the asymptotic count of K_{t,t} copies inside the explicit construction. The manuscript must supply a complete, self-contained derivation of this count (including any incidence or double-counting arguments) that confirms the constant factor 1/(2t(t-1)); an error here would invalidate the claimed equality.

Authors: We agree that the asymptotic count of K_{t,t} copies is central to establishing the matching lower bound and that a complete, self-contained derivation is required. The current short note sketches the counting argument via the incidence properties of the algebraic construction (a suitable incidence graph over a finite field of order t). To address the referee's concern, the revised manuscript will contain an expanded section that spells out all incidence relations, applies double counting to the number of common neighbors, and derives the precise leading constant 1/(2t(t-1)) without relying on external references. This addition will not alter the stated result but will make the verification fully rigorous and self-contained. revision: yes

Circularity Check

0 steps flagged

No circularity: lower bound obtained via explicit algebraic construction independent of fitted parameters or self-citations

full rationale

The paper derives the stated lower bound on ex(n, K_{t,t}, K_{2,t+1}) directly from an explicit construction of a K_{2,t+1}-free graph (available when t is a prime power) whose K_{t,t} count is computed from the geometry or finite-field incidences. The upper bound is imported from the external citation to Pohoata-Tidor-Yu and is not reproduced or fitted inside the note. No equation reduces a claimed prediction to a parameter fit, no self-citation supplies a uniqueness theorem or ansatz, and the construction is not renamed from a prior known pattern. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of an algebraic construction that simultaneously avoids K_{2,t+1} and achieves the stated density of K_{t,t}; this existence is asserted only for prime-power t and is not derived from more elementary axioms in the abstract.

axioms (1)

domain assumption Suitable finite geometries or vector spaces over finite fields exist and yield K_{2,t+1}-free graphs when t is a prime power.
Invoked implicitly by the phrase 'explicit construction' for the lower bound.

pith-pipeline@v0.9.1-grok · 5690 in / 1274 out tokens · 27639 ms · 2026-06-28T13:27:49.052068+00:00 · methodology

discussion (0)

Forward citations

Cited by 2 Pith papers

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

On the generalized Tur\'an number of complete bipartite graphs
math.CO 2026-06 unverdicted novelty 7.0

Proves ex(n, K_{a,b}, K_{s,t}) = Theta(n^s) for s in {2,3} with s < a <= b and t large, plus existence of infinitely many r with ex(n, F, H) = Theta(n^r) for any edge-containing F.
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

5 extracted references · 4 canonical work pages · cited by 2 Pith papers · 1 internal anchor

[1]

Alon and C

N. Alon and C. Shikhelman. Many T copies in H-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016.doi:10.1016/j.jctb.2016.03.004

work page doi:10.1016/j.jctb.2016.03.004 2016
[2]

Gerbner and C

D. Gerbner and C. Palmer. Survey of generalized Tur´ an problems – counting subgraphs, 2025.arXiv:2506.03418,doi:10.48550/arXiv.2506.03418

work page doi:10.48550/arxiv.2506.03418 2025
[3]

Lazebnik and D

F. Lazebnik and D. Mubayi. New lower bounds for Ramsey numbers of graphs and hypergraphs.Advances in Applied Mathematics, 28(3–4):544–559, 2002.doi:10.1006/ aama.2001.0794

arXiv 2002
[4]

Lazebnik and Y

F. Lazebnik and Y. Wang. Some families of graphs, hypergraphs and digraphs defined by triangular systems of polynomial equations.The Electronic Journal of Combinatorics, (DS28), 2026.arXiv:2503.07915,doi:10.37236/14054

work page doi:10.37236/14054 2026
[5]

$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, 2026. arXiv:2605.25905,doi:10.48550/arXiv.2605.25905. 6

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2605.25905 2026

[1] [1]

Alon and C

N. Alon and C. Shikhelman. Many T copies in H-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016.doi:10.1016/j.jctb.2016.03.004

work page doi:10.1016/j.jctb.2016.03.004 2016

[2] [2]

Gerbner and C

D. Gerbner and C. Palmer. Survey of generalized Tur´ an problems – counting subgraphs, 2025.arXiv:2506.03418,doi:10.48550/arXiv.2506.03418

work page doi:10.48550/arxiv.2506.03418 2025

[3] [3]

Lazebnik and D

F. Lazebnik and D. Mubayi. New lower bounds for Ramsey numbers of graphs and hypergraphs.Advances in Applied Mathematics, 28(3–4):544–559, 2002.doi:10.1006/ aama.2001.0794

arXiv 2002

[4] [4]

Lazebnik and Y

F. Lazebnik and Y. Wang. Some families of graphs, hypergraphs and digraphs defined by triangular systems of polynomial equations.The Electronic Journal of Combinatorics, (DS28), 2026.arXiv:2503.07915,doi:10.37236/14054

work page doi:10.37236/14054 2026

[5] [5]

$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, 2026. arXiv:2605.25905,doi:10.48550/arXiv.2605.25905. 6

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2605.25905 2026