World's most popular travel blog for travel bloggers.

How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?

, , No Comments
Problem Detail: 

Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at least $2\lceil \log n\rceil$ is sub-constant?

Asked By : user0906
Answered By : Yuval Filmus

The probability that a specific set of size $k$ is a stable set is $2^{-\binom{k}{2}}$. Hence the probability that some set of size $k \leq n/2$ is stable is at most $$ \binom{n}{k} 2^{-\binom{k}{2}} \leq 2\left(\frac{en}{k}\right)^k 2^{-k^2/2}. $$ When $k = c\log n$ (logarithm to the base 2), this upper bound is $$ 2\left(\frac{en}{C\log n}\right)^{C\log n} 2^{-C^2\log^2 n/2}= \frac{2^{(C-C^2/2)\log^2n}}{\Omega(\log n)^{\Omega(\log n)}} = o(2^{(C-C^2/2)\log^2n}). $$ For $C \geq 2$, this is $o(1)$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback