The Expectation and Variance of the number of $k$ size sets containing exactly $m$ edges in $G(n, p)$
Solution 1:
Calculating $\sum_{i \neq j} EX_i X_j$ requires estimating the probability that a pair of distinct $k$-sets in $V(G)$ both contain exactly $m$ edges. So, let $S_i, S_j \subseteq V(G)$ be distinct sets of size $k$. To calculate the probability that $S_i$ and $S_j$ each contain exactly $m$ edges, we need two pieces of information:
- How large is $S_i \cap S_j$?
- How many edges does $S_i \cap S_j$ contain?
First, let $t = |S_i \cap S_j|$. Our assumption on $S_i$ and $S_j$ means that $0 \leq t \leq k - 1$. Second, let $a$ be the number of edges that $S_i \cap S_j$ contains. (Observe that if $S_i$ and $S_j$ each contain exactly $m$ edges, then $S_i \setminus S_j$ and $S_j \setminus S_i$ must each contain exactly $m - a$ edges.) It is not hard to show that $$\operatorname{max}\biggl(0, m - \binom{k-t}{2}\biggr) \leq a \leq \operatorname{min}\biggl(m, \binom{t}{2}\biggr).$$ To make the summation below less ugly, let $a_{\ell}(m, k, t) = \operatorname{max}\bigl(0, m - \binom{k-t}{2}\bigr)$ and let $a_u(m, t) = \operatorname{min}\bigl(m, \binom{t}{2}\bigr)$.
Then, because there are a total of $2\binom{k}{2} - \binom{t}{2}$ potential edges between vertices of $S_i \cup S_j$, we have $$\sum_{i \neq j} EX_i X_j = \sum_{t=0}^{k-1}\sum_{a = a_{\ell}(m, k, t)}^{a_u(m, t)} \binom{\binom{k-t}{2}}{m-a}^2\binom{\binom{t}{2}}{a} p^{2m - a} (1-p)^{2\binom{k}{2} - \binom{t}{2} - 2m + a}.$$
The asymptotic value of the variance will of course depend on $p$, $m$, and $k$.