 |
 |
24 of 32 |  |
 |
 |
MIT
Comparison
l
Erdos-Renyi
»
threshold of p=(ln n)/n
for complete graphs
»
above threshold, connectivity is pn (1+o(1))
l
In complete graphs, c = n-1
»
often disconnected when p = (ln ©
)/n
»
connected w.h.p. when p > 9(ln c
)/n
»
at higher p, connectivity is Q(pn)
l
Results generalize, but weaker
»
In fact, results generalize to matroids