Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a graph with $k$ edges, if we pick every vertex randomly and independently with a probability of $\frac{1}{2}$, prove that the probability that this set of randomly chosen vertices is an independent set is greater than $\frac{1}{2^k}$.

The approach I am using involves considering all possible selections of vertices, and bounding the probability that those selections have an independent set.

Thanks so much!

share|improve this question
    
What do you mean by independent set ? –  saposcat Nov 20 '12 at 19:09
    
@saposcat An independent set in a graph is a subcollection of the vertices such that the induced subgraph has no edges. –  Austin Mohr Nov 20 '12 at 19:23
add comment

2 Answers

Choose an arbitrary node from each of the $k$ edges, thereby forming a set of $K \le k$ nodes. If none of these nodes is selected, the set of selected nodes is independent, because it is missing at least one node from each edge. The probability that none of the chosen nodes is selected is exactly $2^{-K} \ge 2^{-k}$.

share|improve this answer
    
You can't "choose an arbitrary node from each of the $k$ edges". Choosing vertices from different edges is not independent of each other; two or more edges can share a vertex. –  EuYu Nov 20 '12 at 21:12
    
@EuYu: That's why $K\le k$. The idea is that nodes might be chosen more than once, so less than $k$ nodes might be chosen. –  joriki Nov 20 '12 at 21:21
    
@joriki I see. Thank you for clarifying that. –  EuYu Nov 20 '12 at 21:27
add comment

Well, strictly speaking, this is only true for $k > 0$. For $k=0$ we have a graph with no edges, and the probability of picking an independent set is equal to $1=\frac{1}{2^0}$.

As for your approach, I didn't really understand what it is. If you consider any given selection of vertices, it is either independent or not. It is not a matter of probability, because the graph is not random. The graph is fixed, the selection is random.

Here is a possible way to approach this. For any fixed selection of vertices, the probability of picking this exact selection is $\frac{1}{2^n}$, where $n$ is the number of vertices in the graph. Here I use the assumption that we pick different vertices independently from each other. It is probably implied.

Now, from this observation we can see that the probability of picking an independent set of vertices is simply $$ p = \frac{m}{2^n}, $$ where $m$ the total number of different independent sets of vertices.

So, it comes down to proving that $m>2^{n-k}$. It isn't hard. Here is a hint that might help with that: you can use the fact that a graph with $n$ vertices and $k$ edges has at least $n-k$ connected components.

share|improve this answer
add comment

Your Answer

 
discard

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.