Berkeley Notes
Search…
⌃K

# 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