Erdős-Rényi Random Graphs

Erdős-Rényi Random Graphs

We denote by $G(n,p)$ the Erdős-Rényi random graph model. In this model, we have a set of $n$ vertices, and each pair of vertices is connected by an edge with probability $p$, independently of all other pairs. It is simple to see that the number of edges in a graph $G\sim G(n,p)$ follows a binomial distribution with parameters $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $p$, i.e., $E[\text{\# edges}]=\left(\genfrac{}{}{0ex}{}{n}{2}\right)p$.

Properties of Erdős-Rényi Random Graphs

Theorem

Let $G\sim G(n,1/2)$. Then, for every $v\in V(G)$, we have ${\delta }_v=\frac{n-1}{2}\pm \sqrt{(n-1)\ln n}$ with high probability, where ${\delta }_v$ is the degree of vertex $v$.

Proof

The degree ${\delta }_v$ of a vertex $v\in V(G)$ follows a binomial distribution over the all $n-1$ edges incident to $v$. Therefore

$$\mathbb{E}{\delta }_v=\frac{n-1}{2}.$$

By applying the Chernoff’s inequality: Additive form, we have

$$\mathrm{Pr}\left\{\left|{\delta }_v-\mathbb{E}{\delta }_v\right|\ge t\right\}=\mathrm{Pr}\left\{{\delta }_v\ge \mathbb{E}{\delta }_v+t\right\}+\mathrm{Pr}\left\{{\delta }_v\le \mathbb{E}{\delta }_v-t\right\}\le 2\exp \left(-\frac{2t^2}{n-1}\right).$$

Finally, choosing $t=\sqrt{(n-1)\ln n}$, we have

$$\mathrm{Pr}\left\{\left|{\delta }_v-\mathbb{E}{\delta }_v\right|\ge \sqrt{(n-1)\ln n}\right\}\le 2\exp \left(-2\ln n\right)=2n^{-2}.$$

Thus, with high probability, we have ${\delta }_v=\frac{n-1}{2}\pm \sqrt{(n-1)\ln n}$.

Corollary

As a consequence of this inequality, we have that the average degree of every vertex $v$ in a random graph $G\sim G(n,1/2)$ is $\frac{n-1}{2}\pm (1+o(1))\sqrt{n\log n}$ with high probability.