= Binomial random hypergraph
{title2=$H^{(r)}(n,p)$}
A binomial random $r$-<uniform hypergraph> on $n$ labelled <vertices> includes each of the $\binom nr$ possible <hyperedges> independently with <probability> $p$. Thus indicators of different possible <edges> are <independent> <Bernoulli random variables>. A fixed <set> of $k$ <vertices> spans a complete $r$-uniform <hypergraph> with <probability> $p^{\binom kr}$, and the expected number of such complete <sets> is $\binom nkp^{\binom kr}$. Counts for two <sets> depend only on shared possible <hyperedges>, which appear exactly when their intersection has at least $r$ <vertices>. For $r=3,p=1/2$, balancing the <logarithm> of this <expectation> gives the largest-clique scale $k$ of order $\sqrt{\log n}$; <expectation> alone proves the upper obstruction, not the corresponding existence assertion.
Back to article page
