Zarankiewicz Problem for K_{t,t}-Free Bipartite Graphs

Zarankiewicz Problem for K_{t,t}-Free Bipartite Graphs

Definitions and mathematical statement

For fixed $t\ge2$, let \[ z_t(n)=\max\{|E(G)|:G\text{ simple bipartite},\ |V(G)|=n, \ K_{t,t}\not\subseteq G\}. \] Here $K_{t,t}$ is the complete bipartite graph with $t$ vertices on each side, and the forbidden copy need not be induced. Determine the asymptotic order of $z_t(n)$ as $n\to\infty$ for every fixed $t$. The parameter $n$ is the total number of vertices, not the size of each part, and the bipartition sizes may vary in the maximization. Matching upper and lower orders are requested, not merely an improved upper exponent or a geometric special case.

Formulation and concept references: [S1].

Short English statement

For each fixed t, how many edges can an n-vertex bipartite graph have while avoiding a complete t-by-t bipartite subgraph?

Research attempt

Scope, source check, and plan.

This attempt was prepared by GPT-6 Astra Ultra on 27 September 2026. The catalogue counts total vertices, not vertices per part. The source [S1] surveys geometric restrictions as well as the unrestricted problem; a geometric incidence theorem is not automatically an unrestricted extremal construction. We prove the classical general upper bound, a deletion lower bound, and matching order for $t=2$, with all normalizations explicit. These arguments do not settle every fixed $t$.

Let the two vertex classes be $A,B$, with sizes $a,b$ and $a+b=n$. Write $e$ for the number of edges and $d(v)$ for the degree of $v\in B$. Parts may be empty, in which case $e=0$; the estimates below assume $b>0$. The forbidden graph is a subgraph, so additional edges elsewhere do not make a copy admissible.

Double counting common neighborhoods.

Every $t$-subset of $A$ has at most $t-1$ common neighbors in $B$. Counting pairs consisting of such a subset and one common neighbor gives \[ \sum_{v\in B}\binom{d(v)}t \le(t-1)\binom at. \tag{1} \] For integers $d\ge0$, \[ (d-t+1)_+^t\le t!\binom dt, \qquad x_+=\max\{x,0\}. \] For $d\ge t$, compare the $t$ factors of the falling factorial with $d-t+1$; for smaller $d$ both sides are zero. The function $(x-t+1)_+^t$ is convex, so Jensen and $1$ imply \[ b\left(\frac eb-t+1\right)_+^t \le t!\sum_{v\in B}\binom{d(v)}t \le(t-1)a^t. \] Taking roots, including the case $e/b\le t-1$, gives \[ e\le(t-1)^{1/t}a b^{1-1/t}+(t-1)b. \tag{2} \] In particular \[ z_t(n)=O_t(n^{2-1/t}). \tag{3} \] One may interchange the two parts to obtain a second bound. No assumption that an extremal graph has balanced parts is needed for $3$.

The exponent is not a bookkeeping artifact. If most degrees are of order $n^{1-1/t}$, the left side of $1$ can already be of order $n^t$, the scale of the available $t$-subsets. A matching construction must distribute common neighborhoods without repeatedly saturating the same $t$-subset.

A deletion construction for every fixed t.

Take parts of size $N=\lfloor n/2\rfloor$ and include each edge independently with probability \[ q=N^{-2/(t+1)}. \] Let $X$ be the number of edges and $Y$ the number of copies specified by choosing a $t$-subset in each part. Then \[ \mathbb EX=N^2q=N^{2t/(t+1)},\qquad \mathbb EY=\binom Nt^2q^{t^2} \le\frac{N^{2t/(t+1)}}{(t!)^2}. \tag{4} \] There is an outcome with $X-Y\ge\mathbb E(X-Y)$. Starting with that outcome, repeatedly delete one edge from a remaining $K_{t,t}$. Deletion cannot create a new copy, and at most $Y$ steps are needed, because each step destroys a previously present copy. The final graph has at least $X-Y$ edges and is $K_{t,t}$-free. Adding an isolated vertex if necessary gives exactly $n$ total vertices. Therefore \[ z_t(n)=\Omega_t(n^{2-2/(t+1)}). \tag{5} \] The argument is an existence proof based on expectation and alteration; it does not claim an efficient deterministic construction or a sharp constant. It also remains valid when forbidden copies overlap heavily.

Why the same random model cannot simply use the upper exponent.

Suppose instead $q=N^{-1/t}$, the density suggested by $3$. Then $\mathbb EX=N^{2-1/t}$ but $\mathbb EY$ has order $N^t$ for fixed $t$. For every $t\ge2$, the crude one-edge-per-copy deletion budget is then larger than the available number of edges. This does not prove that no better probabilistic construction exists; it proves that this particular expectation-minus-copies estimate cannot certify it. Counting only the expected degree and ignoring the common-neighbor constraint would miss the central obstacle.

A matching construction for t=2.

Let $\mathbb F_q$ be a finite field. On one side put its $q^2$ affine points $(x,y)$; on the other put its $q^2$ nonvertical lines $\ell_{m,c}: y=mx+c$. Join a point to a line precisely when it lies on the line. Every line contains $q$ points, so \[ n_q=2q^2,\qquad e_q=q^3. \tag{6} \] Two distinct points lie on at most one such line. If their first coordinates differ, solving for $m,c$ determines the line uniquely; if their first coordinates agree, no nonvertical line contains both. A $K_{2,2}$ would be two points on two distinct common lines, which is impossible. Thus this graph is $K_{2,2}$-free.

Fields exist at every order $q=2^j$. For all sufficiently large $n$, choose the largest such $q$ with $2q^2\le n$. Then $q>\tfrac12\sqrt{n/2}$. Add isolated vertices to the graph in $6$, obtaining \[ z_2(n)\ge q^3\ge c n^{3/2} \] for an absolute $c>0$. Combining with $3$ proves \[ z_2(n)=\Theta(n^{3/2}). \tag{7} \] The only algebraic input is existence of finite fields of prime-power order; the incidence and forbidden-subgraph checks are explicit. For reproducible small computations the accompanying script uses prime fields, avoiding the need for a finite-field package.

A sharper small-parameter check.

When $t=2$, $1$ becomes $\sum_{v\in B}d(v)(d(v)-1)\le a(a-1)$. Cauchy--Schwarz gives $\sum d(v)^2\ge e^2/b$, hence \[ e^2/b-e\le a(a-1). \tag{8} \] For the affine construction $a=b=q^2$, $e=q^3$, the left side is $q^4-q^3$ and the right side is $q^4-q^2$; the inequality has the correct scale and direction. Equality is not asserted for the nonvertical-line model, which omits one parallel class of lines.

For $a=b=3$, direct enumeration of the $2^9$ bipartite adjacency matrices finds maximum six edges without $K_{2,2}$, attained by the six-cycle. Formula $8$ allows at most six edges as well: if $e\ge7$, then $e^2/3-e>6$. This finite check verifies both the homogeneous counting convention and a boundary case of the upper bound.

What the partial bounds leave open.

Combining the proved estimates yields \[ c_t n^{2-2/(t+1)}\le z_t(n)\le C_t n^{2-1/t}. \tag{9} \] The exponent gap is $2/(t+1)-1/t=(t-1)/(t(t+1))>0$. The geometric construction closes it at $t=2$ by special algebraic structure, not by optimizing the deletion probability. Other known algebraic constructions and special values discussed in [S1] go beyond $5$; $9$ is not described as the strongest current pair of bounds. In particular, failure of this attempt for a parameter is not a claim that no stronger theorem is known for that parameter.

The exact general condition is that every $t$ points on one side have at most $t-1$ common neighbors. Pairwise intersection control alone is usually too strong to reach the higher-$t$ density, while average intersection control is too weak to rule out one forbidden copy. This gives a concrete design target for a prospective construction.

Verification.

The local script enumerates all graphs on two three-vertex parts, checks $1$ directly on the forbidden-free members, and constructs the affine incidence graphs over several small prime fields. It counts their vertices, edges, and pairwise common neighborhoods exactly. The real-power expectations in $4$ are justified symbolically, not inferred from random experiments. Neither those checks nor $7$ settle the entire family of fixed parameters.

Final status.

UNRESOLVED. The complete partial results are $3$, $5$, and the matching order $7$. The first missing step for the general target is a matching-order lower construction or a genuinely sharper upper bound at the unresolved parameters. Specific next moves are an algebraic incidence model controlling all $t$-fold intersections, a deletion method exploiting overlapping copies rather than counting them independently, or a structural refinement of $1$ for dense graphs. The catalogue's total-vertex convention has been retained throughout.

Sources

• S1 Smorodinsky, A survey of Zarankiewicz problems in geometry $2024$. https://arxiv.org/html/2410.03702. Formulation source.