3
$\begingroup$

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.

2 Answers 2

1

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.

  • 0
    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.2012-11-21
1

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.