Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 11 / 1

Use the random alteration method. Take arbitrarily large $n$ divisible by $2k$, and sample a binomial random graph with edge probability $p=n^{-1+1/(2g)}$. Let $Z$ count cycles of lengths $3,\dots ,g-1$. For each length $\ell$, its expected count is at most $(np{)}^{\ell }/(2\ell )$, soThe sum is empty if $g=3$. By the Markov inequality, $Z\le n/2$ with probability tending to one.

Set $s=n/(2k)$. The expected number of independent $s$-vertex sets isbecause the negative exponent has order $n^{1+1/(2g)}$, dominating the term of order $n$. Thus with probability tending to one there is no independent set of size $s$.

Choose a realization having both properties. Delete one vertex from each of its short cycles, using at most $Z$ deletions. The induced remaining graph $H$ has at least $n/2$ vertices and girth at least $g$. Deletion cannot create a new independent set, so $\alpha (H)\le s-1$. Every colour class is independent, givingIn particular a graph of the required girth and chromatic number exists. This proves graphs of arbitrarily high girth and chromatic number rather than invoking that existence theorem.

Put $q=1-p=1/b$ and $L={\log }_{b}n$. For $s=\lceil 2L\rceil$, the expected number of independent $s$-sets isTaking logarithms gives $\log \mathbb{E}{X}_s\le -c_p\log n\log \log n$ for all sufficiently large $n$: the two quadratic-order terms cancel to within $O_p(\log n)$, leaving the negative term $-s\log s$. By the first moment method, with probability tending to one $\alpha (G)\le s-1<2L$. Hence

For the upper bound, an explicit greedy exposure rule suffices; the sharper factor two is not needed here. SetWhile at least $m_0$ vertices remain, construct a colour class by choosing a candidate, retaining its non-neighbours as candidates, and repeating for $r$ choices. Expose only edges incident to chosen vertices. They will all be removed with this colour class. By deferred edge exposure in greedy independent-set colouring, the remaining internal edges are still independent Bernoulli edges conditional on the history. This assertion depends on this particular rule; it is not true for an arbitrary adaptively selected remainder.

If $M_j$ candidates remain after $j$ choices, then conditionallyThe Chernoff bound gives, for $M_j\ge 1/\eta$,On the event that these lower bounds hold, a class started from $m\ge m_0$ hasIndeed $q^r\ge n^{-1}(\log n{)}^8$, while $(1-2/\log n{)}^r$ is bounded below by a positive constant depending on $p$. Thus each conditional failure probability is at most $\exp [-c_p(\log n{)}^4]$. A union bound over at most $nr$ candidate steps shows that all these classes can be formed with probability tending to one. Colour the final fewer than $m_0$ vertices individually. The number of colours is at mostTogether this provesThe failure estimates are summable in $n$. Thus they give both the usual asymptotically-almost-sure assertion and, on any common probability space carrying the sequence, eventual almost-sure validity by the first Borel-Cantelli lemma.