Random Graphs

A random graph is one which is generated through some amount of randomness.

Definition 76

An Erdos-Renyi random graph $G(n, p)$ is an undirected graph on $n \geq 1$ vertices where each edge exists independently with probability $p$.

With random graphs, we often ask what happens to particular properties as $n\to\infty$ and $p$ scales with some relationship to $n$. In particular, we want that property to hold with high probability (i.e, as $n\to\infty$, the probabilty that $G(n,p)$ has the property approaches 1).

Theorem 42

Every monotone graph property (adding more edges doesn't delete the property) has a sharp threshold $t_n$ where if $p \gg t_n$, then $G(n, p)$ has $p$ with high probability and does not have $p$ with high probability if $t_n \ll G(n,p)$.

One example of a threshold is the connectivity threshold.

Theorem 43 (Erdos-Renyi Connectivity Theorem)

Fix $\lambda > 0$ and let $p_n = \lambda \frac{\log n}{n}$. If $\lambda > 1$, then $P(G(n,p_n)\text{ is connected})$ with probability approaching 1, and if $\lambda < 1$, then $P(G(n,p_n)\text{ is disconnected})$with probability approaching 1