Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 12 / 1

Write $K_s(t)$ for the balanced graph blow-up of a complete graph, with $s$ classes of size $t$; containment here is as a subgraph, not necessarily an induced subgraph. The logarithmic form of the Erdős-Stone theorem is: for fixed $r\ge 1$ and $0<ϵ<1/r$, there are $d=d(r,ϵ)>0$ and $n_0$ such thatThus the guaranteed balanced part size is at least $\lfloor d\log n\rfloor$, with $d$ independent of $n$. We prove the logarithmic Erdős-Stone theorem by a density-to-cliques step and a constructive dense clique family blow-up lemma.

First choose a fixed $m$ large enough that $t_r(m)/\left(\genfrac{}{}{0ex}{}{m}{2}\right)\le 1-1/r+ϵ/2$, where $t_r(m)$ is the edge count of the Turan graph. A uniformly chosen $m$-vertex subset has expected edge count at least $(1-1/r+ϵ)\left(\genfrac{}{}{0ex}{}{m}{2}\right)$. If its induced graph contains no $K_{r+1}$, the Turan theorem bounds that count by $t_r(m)$. Since the count is always at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$, the probability that the subset contains an $(r+1)$-clique is at least $ϵ/2$. Double counting the incidences between such subsets and their cliques gives, for $s=r+1$,for a fixed $\eta >0$ and all sufficiently large $n$. Here $(x{)}_s=x(x-1)\cdots (x-s+1)$. This is clique supersaturation by sampling.

We now prove the needed dense clique family blow-up lemma, with the following stronger induction invariant. Given any family $\mathcal{M}$ of at least $\eta n^s$ distinct $s$-cliques, there is a complete $s$-partite subgraph with each class of size $\lfloor a_s(\eta )\log n\rfloor$, containing that many pairwise vertex-disjoint transversal members of $\mathcal{M}$, each with one vertex in every class. Extra edges within its classes can be ignored. We may suppose $0<\eta <1/2$. For $s=1$, any $\eta n$ singletons suffice, and we may take $a_1(\eta )=1$ once $n$ is large.

For $s\ge 2$, put $\theta =\eta /2$. Repeatedly delete every member of the current family containing an $(s-1)$-clique whose number of extensions is at most $\theta n$. Each such face is processed at most once, and there are at most $n^{s-1}$ possible faces. At most $\theta n^s$ members are deleted. The remaining family $\mathcal{L}$ has size at least $(\eta /2)n^s$, and every face that remains has more than $\theta n$ extensions. Its family of $(s-1)$-faces has size at least $s|\mathcal{L}|/n\ge (\eta /2)n^{s-1}$, since each face is in at most $n$ members.

Apply the induction hypothesis to these faces. It gives a complete $(s-1)$-partite subgraph with $m=\lfloor a_{s-1}(\eta /2)\log n\rfloor$ vertices in each class and a matching $R_1,\dots ,R_m$ of transversal $(s-1)$-faces from the family. Form a bipartite graph whose left vertices are the $R_i$ and whose right vertices are the original $n$ vertices; join $R_i$ to $v$ when $R_i\cup \{v\}\in \mathcal{L}$. Every left degree exceeds $\theta n$.

The following common neighbourhood from bipartite density estimate is elementary. In a bipartite graph with class sizes $m,n$ and at least $\theta mn$ edges, averaging over left subsets $S$ of size $u$ and using convexity of the integer sequence $j\mapsto \left(\genfrac{}{}{0ex}{}{j}{u}\right)$ giveswhenever $1\le u\le \theta m/2$. The last inequality follows by comparing the $u$ factors in the two binomial coefficients; the integer convexity follows from the nondecreasing first differences $\left(\genfrac{}{}{0ex}{}{j}{u-1}\right)$.

ChooseFor large $n$, $m\ge \frac{1}{2}{a}_{s-1}(\eta /2)\log n$, so $u\le \theta m/4$. The estimate supplies $u$ selected faces with a common extension set of size at least $n(\theta /2{)}^u\ge \sqrt{n}$. This extension set is disjoint from the selected faces: a vertex in any one of them cannot extend that face. Their union has $u$ vertices in each of the old $s-1$ classes, with all required cross edges; choose $u$ distinct common extension vertices as a new class. Attaching one different extension vertex to each selected face also gives $u$ disjoint members of $\mathcal{L}$. This completes the induction, with positive constants independent of $n$. Apply it to the clique family above and take $d=a_{r+1}(\eta )$.

The logarithmic order cannot be increased in a uniform forcing result. Put $\rho =1-1/r+ϵ<1$, choose $p$ strictly between $\rho$ and one, and take a binomial random graph. Its edge density exceeds $\rho$ with probability tending to one, by the variance estimate for a sum of independent edge indicators. With $s=r+1$, the expected number of ordered embeddings of $K_s(t)$ is at mostFor $t=\lceil C\log n\rceil$ and $C>2/((s-1)\log (1/p))$, the logarithm of this bound is negative of order $(\log n{)}^2$. Markov's inequality therefore makes the probability of any such copy tend to zero. Both events hold simultaneously for some graphs of every sufficiently large order. There are graphs meeting the density hypothesis whose largest balanced blow-up has part size $O(\log n)$. This upper bound concerns what density can force; it is not an upper bound for every dense graph, since a complete graph has much larger blow-ups.

Finally, $H_k$ is the square of a cycle, for $k\ge 3$. Any three consecutive vertices form a triangle in a graph. In a proper three-colouring, once the first three colours are fixed, each subsequent vertex must repeat the colour three positions earlier. Closing the cycle is possible precisely when $3\mid k$. Conversely, repeating the three colours gives such a colouring whenever $3\mid k$. In that case $H_k$ embeds in $K_3(k/3)$, and the density $0.51\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ exceeds the bipartite Turan theorem threshold by a fixed amount, so the theorem forces $H_k$ eventually. If $3\nmid k$, the balanced Turan graphs $T_3(n)$ have density at least $2/3$ and contain no graph of chromatic number greater than three. They give a counterexample sequence. Exactly the cycle lengths $k\ge 3$ divisible by three have the required property.