Extremal graphs without exponentially-small bicliques

Abstract

The Turán problem asks for the largest number of edges in an $n$-vertex graph not containing a fixed forbidden subgraph $F$. We construct a new family of graphs not containing $K_{s,t}$, for $t=C^s$, with $\Omega (n^{2-1/s})$ edges matching the upper bound of Kövári, Sós and Turán.

20 pages