Past exam of the mathematics course of the University of Cambridge / 2024 / ia / Paper 2 / 12F / iii

Table of contents
- Solution iii

Solution

With

p = c lo g n / n

, the inequality

1 - p \leq e^{- p}

gives

E (N) = n (1 - p)^{n - 1} \leq n e^{- p (n - 1)} = n^{1 - c (n - 1) / n} ⟶ 0

when

c > 1

. The Markov inequality now gives

P (N > 0) \leq E (N) ⟶ 0.

Consequently the upper side of the isolated-vertex threshold in the Erdős-Rényi model is

P (N = 0) ⟶ 1 .

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version