Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2007 / B / 6

For a variable $Z$ of finite variance and $t>0$, Chebyshev's inequality isOn that event, $(Z-EZ{)}^2\ge t^2$. Thus $t^{2}P(|Z-EZ|\ge t)\le E[(Z-EZ{)}^2]$, proving the assertion. Equivalently apply Markov's inequality to the squared deviation.

Assume $EX>0$, as required by the denominators. Since each indicator has variance at most its expectation, and independent event pairs have zero covariance,The sum uses ordered pairs, matching the covariance expansion. Chebyshev's inequality now givesIf $EX=0$, $X=0$ almost surely and the divided expression is not the useful form of the bound.

Let $X$ count the four-vertex sets spanning a clique. Its expectation is $\mu =\left(\genfrac{}{}{0ex}{}{n}{4}\right)p^6$. If $p\ll n^{-2/3}$, then $\mu \to 0$ and Markov's inequality gives $P(X>0)\to 0$.

Now suppose $p\gg n^{-2/3}$. Then $\mu \to \infty$. Two distinct clique indicators are independent unless their vertex sets share at least two vertices. An overlap of two vertices gives $O(n^6)$ ordered pairs requiring eleven distinct edges; an overlap of three gives $O(n^5)$ pairs requiring nine edges. ConsequentlyThe preceding second-moment bound therefore gives $P(X=0)\to 0$. Thusis a threshold for the appearance of a four-clique. Sharing just one vertex creates no dependence because the two edge sets are disjoint.

Realize the random graph process by giving every edge an independent uniform arrival time. For a fixed four-set $S$, only its six internal edges and its $4(n-4)$ outgoing edges affect whether it is an isolated clique. It is an isolated clique at some time exactly when all six internal edges arrive before every outgoing edge.

The relative ordering of these $4n-10$ edges is uniform. The chance that the first six are exactly the six internal edges is ${\left(\genfrac{}{}{0ex}{}{4n-10}{6}\right)}^{-1}$. A union bound over the possible vertex sets givesEdges entirely outside $S$ are irrelevant. Counting the whole arrival-order event avoids an invalid union over continuously many times.

This is an example of isolated clique appearance in a uniform random graph process.