From fd5452fbb038ed78b01eedfad68357f171479d1d Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Wed, 5 Nov 2014 13:35:10 -0500 Subject: [ps5] Fix latex mistake --- ps5/main.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'ps5/main.tex') diff --git a/ps5/main.tex b/ps5/main.tex index 662ffa1..b04f24e 100644 --- a/ps5/main.tex +++ b/ps5/main.tex @@ -313,7 +313,7 @@ concludes the proof of the question. \paragraph{(e)} Using Markov's inequality, let $X$ be the number of monochromatic edges after applying the previous rounding scheme. We have: \begin{displaymath} - \Pr\left[X\geq \frac{n}{4}\left] \leq \frac{n/6}{n/4} = \frac{2}{3} + \Pr\left[X\geq \frac{n}{4}\right] \leq \frac{n/6}{n/4} = \frac{2}{3} \end{displaymath} Hence, by repeating the previous rounding scheme $O(\log n)$ times, we know that at least once we will have less that $\frac{n}{4}$ monochromatic edges -- cgit v1.2.3-70-g09d2