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?

, ,
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?

###### 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 : http://cs.stackexchange.com/questions/44542

3200 people like this

#### Post a Comment

Let us know your responses and feedback