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?
-
2$\begingroup$ 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. $\endgroup$– chazisopJul 4, 2015 at 14:39
-
$\begingroup$ 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. $\endgroup$– chazisopJul 8, 2015 at 11:55
-
1$\begingroup$ 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. $\endgroup$– D.W. ♦Jul 20, 2015 at 2:35
-
1$\begingroup$ Anyway, what have you tried and where did you get stuck? Don't just dump a question from whereever in the textbox. $\endgroup$– RaphaelJul 20, 2015 at 6:28
-
1$\begingroup$ I think the question is definitely on-topic, but it shows no research effort. $\endgroup$– JuhoJul 20, 2015 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)$.