Random graphs, revisited

Recall the Erdös-Rényi model of random graphs where we define the uniform probability space $(\Gamma_n, {\mathbb P})$.

Exercise 103

In Exercise 89, we defined the events $A(i,j)$. Prove that all these events are independent.

Exercise 104

Consider the sample space $(\Gamma_n, {\mathbb P})$. What is the probability that vertices $1$ and $2$ have the same degree? Present your answer in closed form (no sums and no dots-dots-dots). Hint: Vandermonde's identity (Example 26) might be useful for your calculations.

Given undirected graph $G$, the diameter of $G$ is defined as the maximum, over all pairs of vertices $s,t$ of the distance $d_G(s,t)$. When the diameter is small, we know that there is a short path that connects every pair of vertices.

Exercise 105

Verify the following statements:

• Complete graph $K_n$ has diameter one.
• Path $P_n$ has diameter $n-1$ which is the distance between the two ends of the path.
• Cycle $C_n$ has diameter $n/2$ for even $n$ and $(n-1)/2$ for odd $n$.

Theorem 40

Almost all graphs have diameter two.

Proof:

What is the probability that the graph has diameter one? This only happens when the graph is a complete graph (do you see why?), so this probability is $2^{-{n \choose 2}}$. Denote this event (that the graph has diameter one) by $E_1$. Next, what is the probability that the graph has diameter greater than two? Denote such event by $E_{>2}$. We know that ${\mathbb P}[G \text{ has diamter two}] = 1-{\mathbb P}[E_1] - {\mathbb P}[E_{>2}]$. Since ${\mathbb P}[E_1] \rightarrow 0$, we only need to show that ${\mathbb P}[E_{>2}] \rightarrow 0$.

We rephrase the English statement of $E_{>2}$:

$E_{>2}:$ There exists $u,v \in [n], u\neq v$ such that, $\{u,v\}$ is not an edge and for all $w \not\in \{u,v\}$, $w$ is not a common neighbor of $u$ and $v$.

Do you see why $E_{>2}$ is equivalent to the above description? Now, let $F(u,v,w)$ be the event that $w$ is not a common neighbor of $u$ and $v$. We can write $E_{>2}$ as

$E_{>2} = \bigcup_{u\neq v} \left( \overline{A(u,v)} \cap \bigcap_{w} F(u,v,w) \right)$

Now, the probability ${\mathbb P}[F(u,v,w)] = 1- {\mathbb P}[w \text{ is common neighbor}] = 1- (1/2)(1/2)= 3/4$. Moreover, for fixed $u,v$, the events $\{F(u,v,w)\}_{w}$ and $\overline{A(u,v)}$ are independent, so we have that ${\mathbb P}[\overline{A(u,v)} \cap \bigcap_{w} F(u,v,w) ] = 1/2\cdot(3/4)^{n-2} \le (3/4)^{n-1}$. Finally, by the union bound over all choices of $u,v$, we have that

${\mathbb P}[E_{>2}] \leq {n \choose 2} \cdot (3/4)^{n-1}$

This term goes to zero with increasing $n$.

Exercise 106

Prove that almost all graphs contain a triangle. Hint: One might consider an event whose probability is simple to compute, which contains the event of not containing a triangle.