= Four-clique threshold in a binomial 3-uniform hypergraph
{title2=$p^*(n)=n^{-1}$}
A complete three-<uniform hypergraph> on four <vertices> has four <edges>. In the <binomial random hypergraph> $H^{(3)}(n,p)$, its count $X$ has <mean> $\mu=\binom n4p^4$. If $np\to0$, the <first moment method> gives $\mathbb P(X>0)\to0$. Two distinct four-sets have <independent> <clique> indicators unless they share three <vertices>; in that case their combined <edge set> has seven triples. There are $O(n^5)$ such ordered pairs, so $\operatorname{Var}(X)\leq\mu+O(n^5p^7)$. Consequently $\operatorname{Var}(X)/\mu^2=O((np)^{-4}+(n^3p)^{-1})\to0$ if $np\to\infty$. The <second moment method> then gives $\mathbb P(X>0)\to1$. These two implications establish the <threshold function>.
Back to article page
