# Prove the expected size of the independence set got by a random algorithm is at least 1/d of the maximum size

I am doing an exercise related to maximizing Independent Set, I have $$G = (V = \{v_1, . . . , v_n\}, E)$$ as an undirected graph. This graph as $$n!$$ possible orderings for the vertices $$V$$.

If we pick any such orderings uniformly at random i.e. let $$\sigma = (\sigma_1, . . . , \sigma_n)$$ be such random ordering then consider :

Begin with $$S = \emptyset$$.

Then, at each step for $$i = 1$$ to $$n$$, if for all $$u \in S$$, $$(u, v_{\sigma_i}) \notin E$$, add $$v_{\sigma_i}$$ to $$S$$.

Suppose we denote by $$d$$ the maximum degree of a vertex in $$V$$. We need to prove that the proposed algorithm achieves an independent set with expected value of at least $$1/d$$ fraction of the optimal solution.

My Proposed incomplete solution:

We denote OPT solution as $$S^*$$ and $$|S^*| = OPT$$ the size of the max independent set.
Let $$S$$ be the solution and $$|S|$$ is its size. We can write $$X_i = 1$$ if $$v_{\sigma_i}$$ vertex is added to $$S$$ and $$0$$ if not. Let $$X$$ be the number of vertices added to $$S$$.

Consider any vertex $$v \in V$$. If $$v$$ is not added to the independent set $$S$$, it must be because one of its neighbors was added to the independent set $$S$$ before it. The probability that $$v$$ is added to the independent set $$S$$ is at most $$1/(d+1)$$, it’s an upper bound. We calculate the expected value of the algorithm: we denote $$u$$ as an arbitrary vertex of $$V$$ and $$N(v)$$ the neighbors of $$v$$.

$$\mathbb{E}[X] = \mathbb{E}[X_1] + ... + \mathbb{E}[X_n]$$

\begin{align} \mathbb{E}[X_i] & = Pr[v_{\sigma_i} \text{ is added to }S | u \notin N(v_{\sigma_i})] \times Pr[u \notin N(v_{\sigma_i})]\\ & \qquad + Pr[v_{\sigma_i}\text{ is added to }S | u \in N(v_{\sigma_i})] \times Pr[u \in N(v_{\sigma_i})]\\ & = 1\times Pr[u \notin N(v_{\sigma_i})] + 0 \times Pr[u \in N(v_{\sigma_i})]\\ & = Pr[u \notin N(v_{\sigma_i})] \\ & = 1 - Pr[u \in N(v_{\sigma_i})] \end{align} since the maximum degree of a vertex is $$d$$, we have $$Pr[u \notin N(v_{\sigma_i})] \leqslant$$ (something? I'm not sure what) for all $$i$$ from $$1$$ to $$n$$.

Here I got stuck on how to proceed further. If there are mistakes in this I would be happy if you identify and correct.

Let $$Y_v$$ be the random variable that indicates whether vertex $$v$$ is added to the independence set. The probability that $$v$$ appears before all vertices that are incident to $$v$$ in a random ordering is $$\frac1{\deg(v)+1}$$, since all orderings are equally likely and all $$\deg(v)+1$$ vertices involved are symmetric to one another. On this situation $$v$$ will be added to the independence set. ($$v$$ can be added as well on other situations since none of its neighbors might have been added when $$v$$ appears after some of its neighbors.) We have $$E[Y_v]\ge\frac1{\deg(v)+1}\ge\frac1{d+1}.$$
So the expected value of $$Y$$, which is the size of the independence set returned by the given random algorithm is $$E[Y]=\sum_vE[Y_v]\ge\frac{|V|}{d+1}.$$
On the other hand, we will see that the size of the maximum independence set is at most $$\frac {d|V|}{d+1}$$. We can assume $$G$$ is connected since it is enough to prove for each connected component. We assume $$d\ge1$$; otherwise $$d=0$$, the situation is trivial while the proposition is ill-defined with $$\frac1d$$.
Let $$M$$ be a maximum independence set. Since each vertex in $$M$$ is incident to a vertex not in $$M$$ (otherwise that vertex is an isolated vertex, meaning $$G$$ is not connected), we have $$|M| \le|\text{vertices that are incident to }V\setminus M |.$$ Since each vertex is incident to at most $$d$$ vertices, we have $$|\text{vertices that are incident to }V\setminus M|\le d|V\setminus M|.$$ Since $$|V\setminus M|=|V|-|M|$$, we get $$|M|\le d(|V|-|M|)$$, i.e., $$|M|\le \frac {d|V|}{d+1}.$$
So $$\frac{E[Y]}{|M|}\ge\frac{\frac{|V|}{d+1}}{\frac {d|V|}{d+1}}\ge\frac1d,$$ which is what we are asked to prove.