Random graphs: The Erdös-Rényi model

When we talk about random graphs, we refer to graphs generated as an outcome of the following experiment. Let $n$ be the number of vertices. For each $\{i,j\} \in {[n] \choose 2}$, we toss an unbiased coin and if the coin turns up head, there is an edge connecting $\{i,j\}$. This is how we define the probability space based on a random experiment.

Another way to define this probability space is based on a direct definition. Let $\Gamma_n$ be the set of all possible graphs on $n$ vertices (note that some of them are isomorphic). As we discussed in the counting chapter, we have $|\Gamma_n| = 2^{{n \choose 2}}$. We can define a probability space where the sample space is $\Gamma_n$, and each atomic event has probability $2^{-{n \choose 2}}$.

Exercise 89

Consider the previous probability space $(\Omega, {\mathbb P})$. Let $A(i,j)$ denote the event that $i$ and $j$ are adjacent (for $i \neq j$). Notice that there are ${n \choose 2}$ such events. Prove that ${\mathbb P}[A(i,j)] = 1/2$. (Do not use the coin-tossing definition. Only use the definition based on $\Gamma_n$.)

Theorem (Informal)

Almost all graphs are not bipartite.

Proof:

For each $U \subseteq [n]:|U|\leq n/2$, we consider the event $E_U \subseteq \Gamma_n$ containing all graphs that are bipartite and the smaller side of the partition is $U$. Therefore, $E = \bigcup_{U \subseteq [n]:|U|\leq n/2} E_U$ is the event that the graph is bipartite. Note that a particular bipartite graph might belong to several different events $E_U$ as it can have many different possible bipartitions. However, here we will only see an upper bound of the probability (not its exact value).

We count the size of $E_U$. Since the edges are only between $U$ and $[n] \setminus U$, we know that there are at most $k (n-k)$ edges (where $k = |U|$). Each graph $G \in E_U$ must be a spanning subgraph of $K_{k,n-k}$, and there are only $2^{k(n-k)}$ such subgraphs. By using AM-GM, we have that $k(n-k) \leq n^2/4$ (do you see why?). Therefore,

${\mathbb P}[E_U] \leq \frac{2^{n^2/4}}{|\Gamma_n|} = 2^{n^2/4 - n(n-1)/2}= 2^{-n^2/4+n/2}$ Now, using the union bound, we have that

${\mathbb P}[E] = {\mathbb P}[\bigcup_U E_U] \leq \sum_U {\mathbb P}[E_U] \leq 2^n \cdot 2^{-n^2/4+n/2} = 2^{-n^2/4 +3n/2}$

The final remark is that this probability converges to $0$. (do you see why this shows that most graphs are not bipartite?)