Expectation value of induced complete bipartite graphs in a random G(n,p) graph

Question

I am trying to calculate the expected number of induced complete bipartite graphs $K_{r,s}$ in a random graph $G(n,p)$.

I have calculated that the probability a given subset is a complete bigraph is $$P[X = 1] = p^{rs}(1-p)^{\frac{r(r-1) + s(s-1)}{2}}$$

and the expected number of bigraphs will just be the number of ways of arranging $r$ vertices in $n$ and $s$ vertices in $n-r$ for $r \neq s$ to give $$ \mathbf{E}[X] = \binom{n}{r}\binom{n-r}{s} p^{rs}(1-p)^{\frac{r(r-1)+s(s-1)}{2}} $$

Whereas for the case $r=s$ this is $$ \mathbf{E}[X] = \frac{1}{2}\binom{n}{r}\binom{n-r}{s} p^{rs}(1-p)^{\frac{r(r-1)+s(s-1)}{2}} $$ as I do no wish to distinguish between left and right bipartite graphs

However when I run some code to check this my observed number of subgraphs is different. For the case of $r=1$ and $s \neq 1$ the theory matches my simulation perfectly but for $r \neq 1$ and $s \neq 1$ the theory predicts far more bigraphs at large $n$ and too few for small $n$. https://i.stack.imgur.com/19nZi.jpg

So I am wondering where in my derivation I have missed something out that will only affect the number of bigraphs for when $r$ or $s$ is not one or it is an issue with my simulation.

I am simulating the theory by generating a random graph and then searching for the adjacency matrix of the given $K_{r,s}$ within the graph i.e. A complete bipartite graph has an adjacency matrix of the form $$\begin{pmatrix}0_{r,r} & 1_{r,s}\\\ 1_{s,r} & 0_{s,s}\end{pmatrix}$$

I generate the random graph as follows

G[n_, p_] := 
 Module[{A, M}, 
  A = Table[
    If[i < j, If[RandomReal[] < p, 1, 0], 0], {i, 1, n}, {j, 1, n}];
  M = A + Transpose[A];
  Return[AdjacencyGraph[M]];]

And my method for searching for a bigraph is two search for the first line in the adjacency matrix of a $K_{r,s}$ and then check it matches the full matrix, i.e for a $K_{2,3}$

$$\begin{pmatrix}0 & 0 &1&1&1\\\ 0&0&1&1&1 \\\ 1&1&0&0&0 \\\ 1&1&0&0&0 \\\ 1&1&0&0&0 \end{pmatrix}$$

I search for a string of $0,1,1,1$ in each row of the graph and save the positions of them ${p,q,r,s}$ and then check the other elements match a $K_{2,3}$, $(p,q) =1 $, $(q,r) = 0$ etc. I am aware that this can over count in this example as the first and second rows of the adjacency matrix are identical.

Answer 1

Let $X$ be the random variable representing the number of copies of $K_{r,s}$ in a random graph $G$ from $\mathcal{G}(n,p)$, the random graph of order n and edge probability p.

Given a set of $r+s$ vertices from $G$, let us find the probability that the graph induced by this set of vertices is a $K_{r,s}$ graph.

Consider a vertex from this set. In a $K_{r,s}$ graph, we need $r$ vertices to have degree $s$ and $s$ vertices to have degree $r$. The probability of a vertex having degree $s$ is $p^{s}(1-p)^{r-1}$. We want $r$ vertices to have degree $s$ and the probability of this is $(p^{s}(1-p)^{r-1})^{r}$. Similarly, the probability of $s$ vertices having degree $r$ is $(p^{r}(1-p)^{s-1})^{s}$.

Then the probability of both of these happening at the same time is $(p^{s}(1-p)^{r-1})^{r}(p^{r}(1-p)^{s-1})^{s}$. But notice how $r$ vertices having degree $s$ already enforces the condition that exactly $s$ vertices must have degree at least $r$. Also, having no edge from a vertex $a$ to a vertex $b$ already enforces that there is no vertex from $b$ to $a$. Hence, given a set of $r+s$ vertices, the probability of the induced graph being a $K_{r,s}$ graph is

$$ p^{rs}(1-p)^{\frac{r(r-1)+s(s-1)}2} $$

There are $\binom n{r+s}$ ways of picking $r+s$ vertices out of $n$ and $\binom {r+s}{r} = \binom {r+s}{s}$ ways of picking 2 groups of size $r$ and $s$ out of $r+s$ vertices. Hence, in total, we can pick $\binom {n}{r+s} \binom {r+s}{r}$ different couples of sets with one set of size $r$ and the other $s$.

Then the probability of having $x$ copies of $K_{r,s}$ in a graph $G$ from $\mathcal{G}(n,p)$, the space of random graphs of order $n$ and edge probability $p$ is $$ \mathbf{P}(X=x) = (p^{rs}(1-p)^{\frac{r(r-1)+s(s-1)}2})^{x}(1-p^{rs}(1-p)^{\frac{r(r-1)+s(s-1)}2})^{(\binom {n}{r+s} \binom {r+s}{r} - x)} $$

So, we can see that $$ X \sim Bin(\binom {n}{r+s} \binom {r+s}{r}, p^{rs}(1-p)^{\frac{r(r-1)+s(s-1)}2}) $$

Then $$ \mathbb{E}[X] = \binom {n}{r+s} \binom {r+s}{r} p^{rs}(1-p)^{\frac{r(r-1)+s(s-1)}2} $$