Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

first time user here. English not my native language so I apologize in advance. Taking a final in a few weeks for a graph theory class and one of the sample problems is exactly the same as the $k$-edge problem.

We need prove that if each vertex selected with probability $\frac{1}{2}$, that the probability that except that we must find that the probability of the set being an independent set is $\geq (\frac{2}{3})^k$ (instead of $\frac{1}{2^k}$, like original problem).

Here is what I am trying: I am looking into calculating the number of independent sets for each possible number of vertices $i$, for $i=0$ to $i=n$. Once I calculate the probability of there being an independent set for the number of vertices $n$, I can take the expectation and union bound.

share|cite|improve this question

I was the one who asked the original question that you linked to. Just for fun I tried to see if I could prove a better bound. I was able to prove a bound even better than that. Here's a hint: you can use indicator variables and the second moment method.

share|cite|improve this answer
What bound did you get with this method ? – saposcat Nov 21 '12 at 19:49
I got a worse bound than yours, I got $\frac{2^k}{3^k}$. I think I may have found an issue of it though, where I made an incorrect assumption that stems from how I didn't realize that sets of 0 or 1 vertices still count as independent set. – Ranjit S. Nov 21 '12 at 22:33

You can adapt the answer of mjkxxxx to the mathstackexchange problem that you mentioned :

From each edge, you can choose one vertex. You get a collection of $K$ vertices with $K\leqslant k$ (because one same vertex can be choosen for different edges), say $v_1, \dots, v_K$. Each choosen vertex $v_i$ is linked by an edge to $k_i$ different vertices, with $k_i\geqslant 1$, and $\sum_{i=1}^{K} k_i=k $ (if the graph is simple).

Now, if , for any vertex $v_i$, either you don't select $v_i$, either you don't select any of the vertices linked to $v_i$, then you will get an independant set. The probability of this event is greater than (and not equal, because some vertices can be linked to several $v_i$'s) : $$ \prod_{i=1}^K \left(\frac12 +\frac12 (\frac12 )^{k_i}\right)$$ Then, using the convexity of the function $x\mapsto \log\left(\frac12 +(\frac12 )^{x+1} \right)$ and Jensen's inequality, the probability is greater than $$ \exp\left(K \log\left(\frac12 +(\frac12 )^{(\frac1K\sum k_i)+1} \right) \right) = \left(\frac12 +(\frac12 )^{\frac{k}{K}+1} \right)^K $$

Then posing $x=k/K$, the above formula can be written $$ \left(\left(\frac12 + (\frac12 )^{x+1} \right)^{\frac1x}\right)^k $$ and the function $x\mapsto \left(\frac12 + (\frac12 )^{x+1} \right)^{\frac1x}$ is increasing from $\frac34$ when $x=1$ to $1$ when $x\rightarrow\infty$.

We conclude that the probability of picking an independent set is greater than $\left(\frac34\right)^k$.

Remark 1 : This bound is optimal. When the graph is the union of couples of vertices linked by an edge, all the $k_i$' are equal to $1$, all the inequalities become equalities and the probability of picking an independent set is exactly $(3/4)^k$.

Remark 2 : If your graph was not simple, the probabilty would be greater than $(3/4)^{k'}$ where $k'$ is the number of useful edges.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.