Extremal bipartite graphs and Zarankiewicz bounds

Suppose the host contains no $K_{2,t}$ with its two vertices on the left and its t vertices on the right, where $t\ge2$ is fixed. Any pair of distinct left vertices then has at most t minus one common neighbors on the right. Count triples consisting of a left pair and a right vertex adjacent to both. Summing over right vertices gives a binomial coefficient of each right degree; summing over left pairs gives the forbidden-pattern upper bound.

The same triples are counted exactly once in both descriptions, so the inequality needs no randomness or regularity assumption. Degrees are measured only across the declared bipartition, and repeated vertices are not allowed in the pair. A four-cycle is precisely a $K_{2,2}$ in a bipartite graph. Thus a four-cycle-free bipartite graph has at most one common right neighbor for each left pair, a particularly transparent starting case.

Cauchy–Schwarz gives the sum of squared right degrees at least e squared divided by n. Expand each degree's binomial coefficient as half its square minus half its value. Combining with the preceding count yields a quadratic inequality for e. Solving it gives an explicit finite bound; a simpler expression follows by bounding its positive root above. When the two sides have comparable size, the leading term has order n to the three halves rather than n squared.

The general Kővári–Sós–Turán method counts s-element left subsets inside right neighborhoods. If each such subset has at most t minus one common neighbors, convexity yields an upper bound of order $m n^{1-1/s}+n$ for fixed s and t. In the balanced case this becomes order $n^{2-1/s}$. This is an upper bound, not a claim that a matching construction exists for every pair of forbidden part sizes. Sharp constants and exponents can require additional algebraic constructions or remain separate questions.

Incidence graphs connect point vertices to line vertices when a point lies on a line. If two distinct points determine at most one of the chosen lines, the graph has no four-cycle. A finite projective plane of order q gives q squared plus q plus one points and equally many lines, each of degree q plus one. Its edge count is therefore comparable to the three-halves power of a part size. This construction exists for prime-power q; no existence assertion for arbitrary integer q is needed.

There are two related extremal settings. A Zarankiewicz number concerns a bipartite host with specified side sizes and oriented forbidden parts. The ordinary extremal number ex(N,H) concerns any simple graph on N vertices. One can relate their orders of growth through bipartition arguments, but their finite definitions and constants differ. An average density calculation cannot replace the common-neighbor restriction: a graph with the same number of edges may concentrate many of them on a small complete bipartite block.