Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 17I (Graph Theory)

WriteLet $G$ be an $H$-free graph on $n$ vertices with $\mathrm{ex}(n,H)$ edges, and choose a uniformly random set of $m<n$ vertices. Its induced subgraph is still $H$-free, and each edge survives with probability $\left(\genfrac{}{}{0ex}{}{m}{2}\right)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Henceso $d_m(H)\ge d_n(H)$. Thus the normalized extremal number is nonincreasing and bounded below by zero, proving that

The Erdős-Stone theorem states that if the chromatic number of $H$ is $r+1\ge 2$, thenIf $H$ is a bipartite graph with at least one edge, its chromatic number is two, so $r=1$ and therefore

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}$. ConsequentlyIf 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 \left(\genfrac{}{}{0ex}{}{x}{t}\right)$ and the preceding inequality giveand 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:

The stated "nice" subsets of the finite cyclic group ${\mathbb{Z}}_n$ are Sidon sets. Ifthen $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. Thereforeso