Monotone Properties of Random Graphs

Question

I am learning about the monotone properties of random graphs. I came across this question which I am unable to prove. Let $s = s(N) ∈ \{0, 1, . . . , N\}$ where ${s(N) → ∞}$ and ${N − s(N) → ∞ }$ as ${N → ∞}$. Let $ξ ∼ Bin(N, s/N)$. Prove that $P(ξ = s) → 0$ as $N → ∞$. Is it true for constant 's'? I want to know how to approach this type of numerical (I do have a bit of understanding of probability and measure theory but I am very new to random graph). Any help is appreciated.

Moreover, can anyone please suggest some reference or literature for the Random graph? I am following Random Graphs - Svante, Łuczak, Rucinski and Random Graphs by Béla Bollobásbook (which is generally instructed to follow) but I am finding it a bit advance for my level. What I am looking for is something that shows how probability methods are used in Random graphs and have vast examples for the same (since I am not able to get the intuition of solving various random graphs related numerical even though I can understand various solved lemmas).

Thanks in advance.

Answer 1

You want to evaluate $$ P(\xi=s)={N \choose s}\left(\frac{s}{N}\right)^{s}\left(1-\frac{s}{N}\right)^{N-s} $$

Now you know $$ {N \choose s} \leq \left(\frac{eN}{s}\right)^s, $$ and $$ \left(1-\frac{s}{N}\right)^{N-s} = \exp\left( (N-s) \ln{\left(1-\frac{s}{N}\right)}\right) \leq \exp\left( -(N-s) \frac{s}{N}\right), $$ last inequality follows from $\ln(1-x) \leq -x$ for $x\in (0,1)$. Note that you will be done if $(N-s) \frac{s}{N}\to \infty$ as $N\to \infty$. Now there can be two cases:

1. $s/N \to 0$. Then $(1-\frac{s}{N}) {s}\to \infty$ since $s\to \infty$.
2. $s/N \not\to 0$. Then $(N-s) \frac{s}{N}\to \infty$ since $N-s \to \infty$.

For the second part of your question. Generally, the two books that you referred to staple texts in this field. Another excellent reference is the book by Remco van der Hofstad, RANDOM GRAPHS AND COMPLEX NETWORKS Volume I (it is available on his webpage). You may read the past few chapters to review the basic materials. Hope this helps you to grasp the material better. Happy reading :)