# Finding a High Bound on Probability of Random Set

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.

-

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.

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

-