1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Would you mind clarifying the first question a little bit? For example, what is $m(N)$? Also, adding a little bit of background will be helpful, like why you'd like to solve this or what have you tried etc. $\endgroup$ – Suman Chakraborty Mar 22 at 11:06
  • $\begingroup$ @SumanChakraborty sorry, there was a typo error. I rectified it. The random graph is part of my course so I am studying this. We were instructed to follow the mentioned books. And there are a lot of numerical involved like the one I am trying to solve which we need to find out by ourselves. $\endgroup$ – Delta Mar 22 at 11:34
  • $\begingroup$ @SumanChakraborty But I am not able to grasp the various ideas involved in RG. Like as I mentioned I do not know why certain lemmas or prove are solved in a particular way. IDK if there is a gap that needed to be filled or I have to read more. $\endgroup$ – Delta Mar 22 at 11:37
  • 2
    $\begingroup$ My favorite reference is Introduction to Random Graphs by Frieze and Karonski, which can be found on Alan Frieze's website. It's worth checking out to see if it clicks for you. Alon and Spencer's Probabilistic Method also has some material on random graphs in between other things that you'll certainly find useful. $\endgroup$ – Misha Lavrov Mar 22 at 12:33
  • $\begingroup$ @MishaLavrov I agree. These two books are also very nice!! $\endgroup$ – Suman Chakraborty Mar 22 at 12:39
3
$\begingroup$

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 :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.