Berkeley Notes
Home
Resources
Search…
Introduction
EE120
EE123
EECS126
Introduction to Probability
Random Variables and their Distributions
Concentration
Information Theory
Random Processes
Random Graphs
Statistical Inference
Estimation
EECS127
EE128
EECS225A
EE222
Powered By
GitBook
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)
G
(
n
,
p
)
is an undirected graph on
n
≥
1
n \geq 1
n
≥
1
vertices where each edge exists independently with probability
p
p
p
.
With random graphs, we often ask what happens to particular properties as
n
→
∞
n\to\infty
n
→
∞
and
p
p
p
scales with some relationship to
n
n
n
. In particular, we want that property to hold with high probability (i.e, as
n
→
∞
n\to\infty
n
→
∞
, the probabilty that
G
(
n
,
p
)
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
t
n
t_n
t
n
where if
p
≫
t
n
p \gg t_n
p
≫
t
n
, then
G
(
n
,
p
)
G(n, p)
G
(
n
,
p
)
has
p
p
p
with high probability and does not have
p
p
p
with high probability if
t
n
≪
G
(
n
,
p
)
t_n \ll G(n,p)
t
n
≪
G
(
n
,
p
)
.
One example of a threshold is the connectivity threshold.
Theorem 43 (Erdos-Renyi Connectivity Theorem)
Fix
λ
>
0
\lambda > 0
λ
>
0
and let
p
n
=
λ
log
n
n
p_n = \lambda \frac{\log n}{n}
p
n
=
λ
n
l
o
g
n
. If
λ
>
1
\lambda > 1
λ
>
1
, then
P
(
G
(
n
,
p
n
)
is connected
)
P(G(n,p_n)\text{ is connected})
P
(
G
(
n
,
p
n
)
is connected
)
with probability approaching 1, and if
λ
<
1
\lambda < 1
λ
<
1
, then
P
(
G
(
n
,
p
n
)
is disconnected
)
P(G(n,p_n)\text{ is disconnected})
P
(
G
(
n
,
p
n
)
is disconnected
)
with probability approaching 1
Previous
Random Processes
Next
Statistical Inference
Last modified
8mo ago
Copy link