OurBigBook.comSite Source code

Isolated-vertex threshold in the Erdős-Rényi model

For

p = c lo g n / n

, the number

N

of isolated vertices satisfies

P (N = 0) ⟶ {1, 0, c > 1, c < 1.

The upper side follows from the first-moment bound. On the lower side,

E N \to \infty

and

var (N) / (E N)^{2} \to 0

, so the second-moment method applies.

 Ancestors (8)

 Incoming links (1)

Solution