Bipartite graph with $2 \times 10^{6}$ vertices, I need help with removing edges from the graph.

Question

Let G be a bipartite graph. The number of vertices are equal to $2 \times 10^{6}$. Every node is of degree 10. We remove every edge with Probability $2^{-0,1}$.

Show that the number of nodes after removing will be in the interval:

$[10^6-10^4, 10^6+10^4]$

I would appreciate any hints.

Answer 1

Let $X$ be the number of isolated vertices. Let $p=2^{-0.1}$.

By linearity of expectation, the expected (average) number of isolated vertices will be $$E(X)=(2 \times 10^6) \times p^{10}=10^6.$$

We can compute the variance $\mathrm{Var}(X)=E(X^2)-E(X)^2$.

To compute $E(X^2)$, note that $X^2$ is the random variable giving the number of ordered pairs $(u,v)$ of isolated vertices.

• There are $2 \times 10^6$ pairs $(u,u)$, each with probability $p^{10}$ of being isolated.

  • Contribution to $E(X^2)$ from these vertex pairs: $10^6$.

• There are $2 \times 2 \times \binom{10^6}{2}$ pairs $(u,v)$ with $u$ and $v$ being distinct vertices in the same part, each pair having probability $p^{20}$ of both vertices being isolated.

  • Contribution to $E(X^2)$ from these vertex pairs: $5 \times (10^{11}-10^5)$.

• There are $\tfrac{1}{2} \times 10 \times 2 \times 10^6=10^7$ edges, and hence $2 \times 10^7$ pairs $(u,v)$ where $u$ and $v$ are adjacent, each having probability $p^{19}$ of both vertices being isolated.

  • Contribution to $E(X^2)$ from these vertex pairs: between $\leq 5.36 \times 10^6$.

• There are $(10^6)^2-10^7=10^{12}-10^7$ non-edges and hence $2 \times (10^{12}-10^7)$ pairs $(u,v)$ where $u$ and $v$ are in different parts and are not adjacent, each having probability $p^{20}$ of both vertices being isolated.

  • Contribution to $E(X^2)$ from these vertex pairs: $5 \times (10^{11}-10^6)$.

So, together we have $E(X^2) \leq 10^{12}+0.86 \times 10^6$. Hence we have $$\mathrm{Var}(X) \leq 0.86 \times 10^6$$ and standard deviation $$\mathrm{Sd}(X)=\sqrt{\mathrm{Var}(X)} \leq 928.$$

This is probably where the $\pm 10^4$ in the question comes from.

---

I've checked that this matches with experimental results. I generated the graph on vertex set $\{u_i:i \in \mathbb{Z}_{10^6}\} \cup \{v_i:i \in \mathbb{Z}_{10^6}\}$ where $u_i$ is adjacent to $v_{i+k}$ for all $k \in \{0,1,\ldots,9\}$. After deleting edges independently with probability $p$, the number of isolated vertices were found:

{998740, 999797, 998139, 999007, 1000621, 1000994,1000465, 998233, 1000051, 998468, 999920, 1000037, 1000561, 999358, 999182, 999840, 998562, 1000521, 1000541}

which has sample mean $999634$ and sample standard deviation $\approx 902$, consistent with the theoretical results.