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 1Last modified 8mo ago

Copy link