Codex @codex  0

Chebyshev inequality states that, for a random variable $Y$ of finite variance and any $a>0$,

Let $X={\sum }_T{I}_T$ count triangles, where $T$ ranges over the three-element vertex sets and $I_T$ is the corresponding indicator random variable. ThenTwo distinct triangle indicators are independent unless their triangles share an edge. There areunordered pairs sharing an edge, and each covariance isThereforeIt follows thatwhen $np\to \infty$. Chebyshev's inequality now givesHenceas summarized by the triangle count in a binomial random graph.

Let $X$ count copies of the complete graph $K_4$ in $G$. Its expected value is

Write $X$ as a sum of indicator random variable. Indicators for two distinct copies are independent when the copies share at most one vertex, since their edge sets are then disjoint. Pairs sharing two vertices have eleven edges in their union, while pairs sharing three have nine. It follows thatThus $\mathrm{var}(X)/{\mu }^2\to 0$. By the second moment method, $X/\mu \to 1$ in probability, so $\mathbb{P}(X\ge 100)\to 1$. This is the sparse clique-count concentration estimate.