Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 3

Markov inequality says that a nonnegative random variable $Y$ satisfiesChebyshev inequality says that a random variable with finite variance satisfies

Let $X$ count triangles in $G(n,p)$. The triangle count in a binomial random graph calculation givesSince $p\gg n^{-1}$,For sufficiently large $n$, $\mu >200$, and Chebyshev inequality gives

For a monotone graph property $P=(P_n)$, a function $p^{\ast }(n)$ is a threshold function for a monotone graph property whenand

Write $f_n(q)=\mathbb{P}(G(n,q)\in P_n)$. This is increasing in $q$ by monotone coupling of binomial random graphs, and $f_n(p)=1/10$ by hypothesis.

First let $q/p\to 0$. Choose $k=\lfloor p/(2q)\rfloor$, so $k\to \infty$. The union of $k$ independent copies of $G(n,q)$ has distribution $G(n,q^{\prime })$, whereIf any layer has $P_n$, their union has $P_n$, and henceIt follows that $f_n(q)\le 1-(9/10{)}^{1/k}\to 0$.

Now let $q/p\to \infty$. Choose $k=\lfloor q/(2p)\rfloor$, again tending to infinity. The union of $k$ independent $G(n,p)$ graphs has parameterMonotonicity and independence giveThus $p(n)$ is a threshold function.

Use sprinkling of a binomial random graph to write $G(n,p)=G_1\cup G_2$, where the rounds are independent,and $C$ is chosen large enough that $1-p=(1-p_1)(1-p_2)$. By the given theorem, $G_1$ has a Hamilton cycle $v_1{v}_2\cdots v_n{v}_1$ with high probability.

Condition on such a cycle. For each $3\le \ell \le n-1$, every chord $v_i{v}_{i+\ell -1}$ closes one of the two paths around the Hamilton cycle into a cycle of length $\ell$. There are at least $n/2$ distinct candidate chords, so the probability that $G_2$ supplies none is at mostA union bound over the fewer than $n$ lengths shows that all these cycles occur simultaneously with high probability when $c>4$. The Hamilton cycle itself supplies length $n$, so $G$ is pancyclic.