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$
    – chazisop
    Jul 4 '15 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$
    – chazisop
    Jul 8 '15 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 '15 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$
    – Raphael
    Jul 20 '15 at 6:28
  • 1
    $\begingroup$ I think the question is definitely on-topic, but it shows no research effort. $\endgroup$
    – Juho
    Jul 20 '15 at 9:57

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


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.