Probability of subset of a graph being stable Let $G=(V,E)$ be a graph with $|E|=m$. Let $S\subseteq V$ such that $\Pr(v\in S)=\frac{1}{2}$ for all $v\in V$ and the events are independent for all $v \in V$. Show $\Pr(S \text{ is stable})\geq \left( \frac{3}{4}\right)^{m}$. A set is called stable if it has no edges between any of its vertices.
$\Pr(S  \text{ is stable}) =1-\Pr(E_S \neq \emptyset)=1-\Pr(\exists v_1,v_2\in S:\{v_1,v_2\}\in E)=1-\Pr(\text{choosing }v_1,v_2)=1-\frac{1}{4}\cdot N$
Where $N$ is the number of possible choices for $v_1,v_2$.
The probability of an independent set is minimized when $G$ is a complete Graph. A complete graph with $n$ vertices has $\frac{n(n-1)}{2}$edges. Suppose $G$ is complete and has $m$ edges, then possible number of vertices:
$$\frac{1+\sqrt{1+8m}}{2},\quad \frac{1-\sqrt{1+8m}}{2}.$$
Not sure how to continue
 A: Your goal is to prove that
$$
   \Pr\left[\bigwedge_{vw \in E} \{v,w\}\not\subseteq S\right] \ge \prod_{vw \in E} \Pr[\{v,w\} \not\subseteq S]
$$
since $\Pr[\{v,w\} \not\subseteq S]$ is just $\frac34$ so the right-hand side simplifies to $(\frac34)^m$. (The $\bigwedge$ in the left-hand side denotes the logical AND of all the statements $\{v,w\} \not\subseteq S$ over $vw \in E$: that is, no edge has both endpoints in $S$, making $S$ a stable set.)
One way to do so is with some variant of the FKG inequality. Each event $\{v,w\} \not\subseteq S$ is a decreasing property of $S$: if it is true for $S$, it's true for all subsets of $S$. Decreasing events are positively correlated with each other: the probability that they hold simultaneously is at least as large as it would be if they were independent. This gives us the inequality above.
(Regarding which correlation inequality to use - of the ones mentioned in the Wikipedia article, the Harris inequality seems the most appropriate, and the example given there is very similar. If you have Alon and Spencer's Probabilistic Method as a reference, then Kleitman's Lemma (Proposition 6.3.1 in Chapter 6) is the simplest result there that gives us what we want.)
