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

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?

• I tihnk your question is not research-level, since such matters are the first to be investigated in the Erdos-Renyi model, which is what you are describing. I found some lecture notes, and they use the defining property of an independent set: no edges between any of the vertices. Jul 4 '15 at 14:39
• If I recall both site policies correctly, you may re-post after a week if an answer was not given yourself, but you have to mention it is a cross-post and provide a link. I'll flag your question in case a moderator will move it automatically. Jul 8 '15 at 11:55
• Why is this a question about computer science? It sounds like a pure math question and thus not on-topic here. Also, what is a "stable set"? Please include a definition in your question. Finally, what have you tried? What research have you done? We expect you to do a significant amount of research before asking, and to show us in the question what you tried and what research you did.
– D.W.
Jul 20 '15 at 2:35
• Anyway, what have you tried and where did you get stuck? Don't just dump a question from whereever in the textbox.
– Raphael
Jul 20 '15 at 6:28
• I think the question is definitely on-topic, but it shows no research effort.
– Juho
Jul 20 '15 at 9:57

## 1 Answer

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)$.