Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / A / 4

The extremal number $\mathrm{ex}(n;H)$ is the maximum number of edges in a simple graph on $n$ vertices containing no subgraph isomorphic to $H$. For a fixed graph with $\chi (H)=r\ge 2$, the Erdős-Stone theorem givesEquivalently, the ratio to $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ tends to $1-1/(r-1)$. The bipartite case has limiting density zero.

An even cycle is bipartite and has chromatic number two. An odd cycle has chromatic number three. The extremal-density theorem therefore givesFor odd cycles the complete balanced bipartite graph also exhibits the matching asymptotic lower density one half.

For nonempty disjoint vertex sets define $d(X,Y)=e(X,Y)/(|X||Y|)$. The pair is $ϵ$-uniform, also called regular, if whenever $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$ have sizes at least $ϵ|X|$ and $ϵ|Y|$,Thus reasonably large relative subsets retain almost the same edge density.

Let $S$ be the vertices of $X$ with fewer than $d|Y|/2$ neighbours in $Y$. If $|S|>ϵn$, it is a permissible subset in the regularity test, and averaging those degrees gives $d(S,Y)<d/2$. But $d(X,Y)\ge d$, socontradicting regularity. Therefore there are at most $ϵn$ such vertices. The same argument in fact rules out $|S|\ge ϵn$ when that threshold is integral and nonzero.

Retain $0<ϵ<d/2$ from the preceding part. In $X_1$, at most $ϵn$ vertices have too few neighbours in $X_2$, and at most $ϵn$ have too few in $X_3$. Since $d\le 1$, $2ϵ<1$, so some $x\in X_1$ is good for both. Put $Y_2=N(x)\cap X_2$ and $Y_3=N(x)\cap X_3$. Their sizes are at least $dn/2>ϵn$. Regularity of $(X_2,X_3)$ therefore givesThere is an edge joining a vertex of $Y_2$ to a vertex of $Y_3$. Its two endpoints and $x$ form a triangle. The nonempty equal classes ensure this counting argument also covers small integer sizes.