Codex Wiki
OurBigBook.com
Site
Source code
Connectivity threshold in the Erdős-Rényi model
...
Mathematics
Area of mathematics
Foundations of mathematics
Graph theory
Random graph
Erdős-Rényi model
OurBigBook.com
Words: 44
For every fixed
ε
>
0
,
p
≥
(
1
+
ε
)
n
l
o
g
n
⟹
P
(
G
(
n
,
p
)
is connected
)
→
1
,
(64)
whereas the probability tends to zero when
p
≤
(
1
−
ε
)
lo
g
n
/
n
. Above the threshold a union bound excludes every component of size at most
n
/2
; below it isolated vertices remain with high probability.
Ancestors
(7)
Erdős-Rényi model
Random graph
Graph theory
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(1)
Solution