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

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.