# Proving relationship between cuts in graph

Suppose we sample uniformly at random (without replacement) a set $S$ of edges from an undirected and unweighted graph $G = (V,E)$, creating a new graph $G'=(V',S)$ of only sampled nodes and edges. Let $(A,B)$ be the max cut in G with size equal to $|(A×B)∩E|$, and let $(A',B')$ be another generic cut with size $|(A'×B')∩E|$. Let $|(A'×B')∩S|$ be the size of $(A',B')$ in $G'$. Show that the probability that $|(A'×B')∩S|·\frac{|E|}{|S|}$ is greater than: $$|(A'×B')∩E| + ε·|(A×B) ∩ E|$$ is small. Consider the following Chernoff bounds for the proof: $$Pr\biggl[\sum_{i=1}^{|S|} X_i>(1+ε)|S|\mu\biggr] < exp\biggl(-\frac{\epsilon^2|S|\mu}{3}\biggr)$$ $$Pr\biggl[\sum_{i=1}^{|S|} X_i<(1-ε)|S|\mu\biggr] < exp\biggl(-\frac{\epsilon^2|S|\mu}{2}\biggr)$$

where $\mu$ is the expected value of the set of |S| of random variables.

Now, I am quite confused on this. I computed the expected value of the size of $(A',B')$ in $G'$ as: $$\mu=E\bigl[|(A'×B')∩S|\bigr] = \frac{|(A'×B')∩E|}{|E|} |S|$$ Then I could apply the first Chernoff bound to show that: $$Pr\biggl[|(A'×B')∩S|>(1+ε)|S|\mu\biggr] < exp\biggl(-\frac{\epsilon^2|S|\mu}{3}\biggr)$$ However I don't really know $\mu$ since I don't know the size $|(A'×B')∩E|$. Any suggestion?

The Chernoff bound does not apply here since $S$ is sampled without replacement and thus the $X_i$'s are not independent. Let $X = |(A' \times B') \cap S|$. It is easy to see that $X$ follows the hypergeometric distribution. That is, $$\Pr(X = k) = \frac{\binom{|(A'\times B') \cap E|}{k}\cdot\binom{|E| - |(A'\times B')\cap E|}{|S| - k}}{\binom{|E|}{|S|}}$$ Therefore, $$\mathbb{E}[X] = \frac{|(A'\times B') \cap E|}{|E|}\cdot |S|$$ By the paper by Skala, $$\Pr(X \geq \mathbb{E}[X] + |S|\cdot t) \leq e^{-2t^2|S|}$$ from which by letting $t = \epsilon\cdot \frac{|(A\times B)\cap E|}{|E|}$, we attain \begin{align} &\Pr\left(|(A' \times B') \cap S| \geq \frac{|(A'\times B')\cap E|}{|E|}\cdot |S| + t|S|\right) \leq e^{-2t^2|S|} \\ \Rightarrow\ &\Pr\left(|(A' \times B') \cap S| \cdot \frac{|E|}{|S|}\geq {|(A'\times B')\cap E|} + t|E|\right) \leq e^{-2t^2|S|} \\ \Rightarrow\ &\Pr\left(|(A' \times B') \cap S| \cdot \frac{|E|}{|S|}\geq {|(A'\times B')\cap E|} + \epsilon\cdot|(A \times B)\cap E|\right) \leq e^{-2\left(\epsilon\cdot\frac{|(A\times B)\cap E|}{|E|}\right)^2|S|} \end{align} Note that $\frac{|(A\times B) \cap E|}{|E|} \geq \frac{1}{2}$ since the max cut of a graph has at least $|E| / 2$ edges. Hence, the RHS of the last inequality can be upper bounded by $e^{-\epsilon^2|S|/2}$.
• @GianlucaJohnMassimiani For notational convenience, let $C' = A' \times B'$ and $C = A \times B$. We have \begin{align}&\Pr\left(|C' \cap S| \cdot \frac{|E|}{|S|} \geq |C' \cap E| + \epsilon \cdot |C \cap E|\right) \\ =\ & \Pr\left(|C' \cap S| \cdot \frac{|E|}{|S|} \geq |C' \cap E| + \epsilon \cdot \frac{|C \cap E|}{|C' \cap E|} \cdot |C' \cap E|\right) \\ \leq\ &\mathsf{exp}\left(-\frac{\epsilon^2\cdot \left(\frac{|C \cap E|}{|C' \cap E|}\right)^2\cdot |S| \cdot \frac{|C' \cap E|}{|E|}\cdot |S|}{3}\right)\end{align} – PSPACEhard Jan 13 '18 at 3:57
• @GianlucaJohnMassimiani Then notice that $$\left(\frac{|C \cap E|}{|C' \cap E|}\right)^2 \cdot \frac{|C' \cap E|}{|E|} = \frac{|C \cap E|}{|C' \cap E|} \cdot \frac{|C \cap E|}{|E|} \geq 1 \cdot \frac{1}{2}$$ – PSPACEhard Jan 13 '18 at 4:01
• @GianlucaJohnMassimiani You are right. I did wrong. The last $|S|$ is not required. – PSPACEhard Jan 14 '18 at 3:44