= Solution
First consider a $K_{t,t}$-free <bipartite graph> with parts $X,Y$, each of size at most $n$, and $m$ edges. Count pairs $(S,y)$ in which $S$ is a $t$-element subset of the <graph neighbourhood> of $y\in Y$. Any $t$ vertices of $X$ have at most $t-1$ common neighbours, since $t$ common neighbours would form the <complete bipartite graph> $K_{t,t}$. Consequently
$$
\sum_{y\in Y}\binom{d(y)}t\leq(t-1)\binom{|X|}t.
$$
If the average <degree of a vertex> is bounded in terms of $t$, then $m=O(n)$ and the required result is immediate. Otherwise, <convexity> of $x\mapsto\binom xt$ and the preceding inequality give
$$
|Y|\binom{m/|Y|}t=O(n^t),
$$
and hence $m=O(n^{2-1/t})$. Every graph has a bipartite spanning subgraph containing at least half its edges, obtained by choosing a random bipartition. Applying the bipartite estimate to that subgraph proves the <Kővári–Sós–Turán theorem> in the required form:
$$
\boxed{\ \operatorname{ex}(n,K_{t,t})=O(n^{2-1/t}).\ }
$$
The stated "nice" subsets of the <finite cyclic group> $\mathbb Z_n$ are <Sidon sets>. If
$$
a-b=c-d,
\qquad a\ne b,\qquad c\ne d,
$$
then $a+d=c+b$. Niceness forces $(a,b)=(c,d)$; the alternative pairing would force $a=b$. Thus the $|A|(|A|-1)$ ordered nonzero differences are distinct elements of the $n-1$ nonzero residue classes. Therefore
$$
|A|(|A|-1)\leq n-1,
$$
so
$$
\boxed{\ f(n)\leq\frac{1+\sqrt{4n-3}}2=O(\sqrt n).\ }
$$
Back to article page
