Links

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)G(n, p)
is an undirected graph on
n1n \geq 1
vertices where each edge exists independently with probability
pp
.
With random graphs, we often ask what happens to particular properties as
nn\to\infty
and
pp
scales with some relationship to
nn
. In particular, we want that property to hold with high probability (i.e, as
nn\to\infty
, the probabilty that
G(n,p)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
tnt_n
where if
ptnp \gg t_n
, then
G(n,p)G(n, p)
has
pp
with high probability and does not have
pp
with high probability if
tnG(n,p)t_n \ll G(n,p)
.
One example of a threshold is the connectivity threshold.

Theorem 43 (Erdos-Renyi Connectivity Theorem)

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