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

Markov's inequality states that for $Y\ge 0$ and $t>0$, $\mathbb{P}(Y\ge t)\le \mathbb{E}Y/t$. It follows by taking expectations in $Y\ge t{1}_{\{Y\ge t\}}$.

If $X$ has finite mean $\mu$ and variance ${\sigma }^2$, apply Markov to $(X-\mu {)}^2$ to obtain Chebyshev's inequality:For the first moment method, assume ${\mu }_n=\mathbb{E}{X}_n\to 0$. Nonnegative integer values give $\{X_n>0\}=\{X_n\ge 1\}$, soFor a standard second moment method, suppose ${\mu }_n>0$ eventually, the second moments are finite, and $\mathbb{E}{X}_n^2/{\mu }_n^2\to 1$. Equivalently, $\mathrm{Var}(X_n)/{\mu }_n^2\to 0$. The zero event is contained in $\{|X_n-{\mu }_n|\ge {\mu }_n\}$, soHence $\boxed{\mathbb{P}(X_n>0)\to 1}$. The second-moment condition controls the fluctuations relative to the mean; a large mean alone is insufficient.

Let $X$ count the four-vertex sets spanning all four of their possible triples. For each such set $S$, write $I_S$ for its indicator. Independence of the four hyperedges givesIf $np\to 0$, then $\mu \le (np{)}^4/24\to 0$, and the first moment method shows that the probability of a four-clique tends to zero.

For the other direction, consider two distinct four-sets. If they meet in at most two vertices, they have no possible triple in common, so their indicators are independent. If they meet in three vertices, they share exactly one triple, so $\mathbb{E}(I_S{I}_T)=p^7$ and their covariance is at most $p^7$. There are $O(n^5)$ ordered pairs of this latter type. The diagonal variances sum to at most $\mu$, henceFor large $n$, $\mu$ is a constant multiple of $n^4{p}^4$, and consequentlyIf $np\to \infty$, the first term tends to zero, and so does the second since $n^{3}p=n^2(np)\to \infty$. The second moment method proves that a four-clique exists with probability tending to one. Therefore a threshold function isThe shared-triple overlap, rather than overlaps in one or two vertices, is the only off-diagonal dependence that affects this computation.

This is the four-clique threshold in a binomial 3-uniform hypergraph.

The requested scale is $\boxed{k=\Theta (\sqrt{\log n})}$. To see its first-moment origin, the number $X_k$ of $k$-cliques has expectationFor $k$ on the proposed scale, taking base-two logarithms givesThe leading terms balance at $k\approx \sqrt{6{\log }_{2}n}$. In particular, for any fixed $c>\sqrt{6}$, taking $k$ near $c\sqrt{{\log }_{2}n}$ makes the expectation tend to zero, so such cliques are absent with probability tending to one.

Thus the first-moment estimate places the largest-clique scale at a constant multiple of $\sqrt{\log n}$, as requested. A diverging expectation below that balance does not itself prove existence; a corresponding probabilistic lower-bound proof would require an additional argument and is not part of the requested first-moment estimate.