Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2010 / B / 4

For a nonnegative random variable $Y$ and $a>0$, Markov inequality statesFor a random variable $X$ of finite mean $\mu$ and variance ${\sigma }^2$, Chebyshev inequality states that for every $t>0$,To prove it, apply Markov inequality to the nonnegative variable $(X-\mu {)}^2$ at threshold $t^2$:

For an indicator $I_i$, $\mathrm{Var}(I_i)=P(A_i)(1-P(A_i))\le P(A_i)$. Covariances vanish for independent pairs. For dependent distinct pairs,Expanding the variance, with ordered pairs as in the definition of $\Delta$, givesFor sufficiently large $n$, ${\mu }_n>0$. By Chebyshev inequality,This is the second moment method: a vanishing relative variance makes a zero count unlikely.

A threshold function $p^{\ast }(n)$ has the following meaning: if $p/p^{\ast }\to 0$, the probability of a $K_5$ tends to zero; if $p/p^{\ast }\to \infty$, that probability tends to one. Behavior at a fixed constant multiple is not specified by this definition.

Let $X$ count the five-vertex subsets spanning $K_5$ in the Erdős-Rényi model $G(n,p)$. ThenIf $p\ll n^{-1/2}$, then $\mu \to 0$, so Markov inequality gives $P(X>0)\le \mu \to 0$.

Now let $p=n^{-1/2}w$ with $w\to \infty$. Then $\mu \sim w^{10}/120\to \infty$. Distinct copies have dependent indicators only if their vertex sets share at least two vertices. If they share $j\in \{2,3,4\}$ vertices, they share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges; there are $O(n^{10-j})$ ordered such pairs, and their joint probability is $p^{20-\left(\genfrac{}{}{0ex}{}{j}{2}\right)}$. ConsequentlyPart (b) gives $P(X=0)\to 0$. ThereforeThis is the five-vertex instance of the fixed-size clique appearance threshold.