\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,url}
\usepackage{bbm}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Professor Amin Saberi (saberi@stanford.edu) }
{\\ \bssten HW\#3 --  Due 3/6/12}
\vspace{5pt}

\begin{enumerate}

\item Given a graph $G=(V, E)$ and a set of vertices $S \subseteq V$, denote by $f(S)$ the number edges with one endpoint
in $S$ and the other in $V \setminus S$. Use the probabilistic method to show that there exists an $S$ such that $f(S) \geq |E|/2$. In other words, prove there exists a cut in the graph which contains at least half of the edges. 


\textbf{Solution.} Simply flip a fair coin for each node to decide if it is in $S$. Then trivially the expected number of edges cut by $S$ is $|E|/2$: consider an indicator variable for each edge, the sum of the indicator variables will have have expectation $|E|/2$ since each indicator variable has expectation $1/2$ (each edge is included with probability half, since its two ends will be in the same side half the time).
Which means that the probability that this algorithm outputs a cut of that size is nonzero. Thus by the probabilistic method such a cut exists.

\item An independent set in a graph is a set of vertices with no edges
connecting them. Let $G$ be a graph with $nd/2$ edges $(d > 1)$, and consider the following
probabilistic experiment for finding an independent set in $G$: delete each vertex of $G$
(and all its incident edges) independently with probability $1 - 1/d$.
\begin{enumerate}
\item Compute the expected number of vertices and edges that remain after the deletion
process. Now imagine deleting one endpoints of each remaining edge.

\textbf{Solution.} Each node survives with probability $1/d$. Thus the expected number
of nodes is $n/d$. Each edge survives with probability $1/d^2$ (both its ends must survive independently).
Thus the expected number of edges is $nd/2 \times 1/d^2 = n/2d$.

\item From this, infer that there is an independent set with at least $n/2d$ vertices in any
graph with $n$ vertices with $nd/2$ edges.

\textbf{Solution.} After applying this sampling, we create an independent set as follows: for each edge in the resulting graph, delete one of the endpoints. After doing this for each edge, none of the remaining vertices are connected by any edges, i.e. form an independent set. If $G'=(V',E')$ is the graph we obtain after sampling, we expect the size of the independent set to be
$$E[\text{size of independent set}] = E[|V'| - |E'|] = n/d - n/2d = n/2d$$
Since there will be at least one outcome with a value equal to (or greater than) the
expectation, by the probabilistic method there must be an independent set of size $\geq n/2d$.

\end{enumerate}

\item Let $G = (V,E)$ be a bipartite graph on $n$ vertices with a list $S(v)$ of at least $1+ \log_2 n $ colors associated with each
vertex $v \in V$.  Prove that there is a proper coloring of $G$ assigning to each vertex of $v$ a color from its list $S(v)$.

\textbf{Solution.} Consider the union of all colors $S = \cup_v S(v)$. Then for each color $c\in S$, flip a fair coin, if heads, use $c$ to
color all nodes $u$ on the left side which have $c\in S(u)$, else use it on the right. Never use color $c$ again, 
and never consider the colored nodes again.

If the above algorithm colors every node, it will have done so correctly since nodes on opposing sides of the partition
never get the same color. It remains to show that the algorithm will with nonzero probability color all the nodes.

Let $X$ be the number of nodes that don't receive a color. Let $X_i$ be the indicator variable
that node $i$ does not get assigned a color. That means all the colors in $S(i)$ must have been assigned
to the other side of the partition. Thus $E[X_i] = P[X_i] \leq (1/2)^{\log n +1} = 1/2n$.
So we have $$E[X] = \sum_{i=1}^n E[X_i] \leq n (1/2n) = 1/2 < 1$$

Thus we expect less than 1 node to be left uncolored. Since $X$ only takes integer values, 
by definition of expectation this means
$\Pr[X = 0] > 0$. Thus the algorithm has some nonzero probability of outputting a valid coloring
and thus one exists.


\item Let $G=(V,E)$ be a $c$-edge connected graph. In other words, assume that the size of minimum cut in $G$ is at least $c$. Construct a graph $G'(V, E')$ by sampling each edge of $G$ with probability $p$ independently at random. Suppose $c > \log n$, and $\epsilon$ is such that $ \frac{\log(n)}{c \epsilon^2} \leq 1$. Show that as long as $p \geq \frac{\log(n)}{c \epsilon^2}$, with high probability the size of every cut in $G'$ is within $p(1\pm \epsilon)$ of the cut in the original graph $G$.

\textbf{Solution.}
To see how naive this random sampling performs, we will sample each edge with the same probability
$p$, and give weight $1/p$ to each edge in the sparse graph $H$. With these weights,
each edge $e \in E$ will have expected contribution exactly 1 to any cut, and thus the expected weight
of any cut in $H$ will match $G$. It remains to see how many samples we need to have
cut equivalence between $G$ and $H$ with high probability.

Consider a particular cut $S \subseteq V$. If it has $c$ edges crossing it in $G$, the expected weight of edges crossing it in the new graph $H$ is also $c$. Denote the total weight of edges between $S$ and $V-S$ by $f_G(S) = c$, we have the following
concentration result due to Chernoff:

$$P(|f_H(S) - c| \geq \epsilon c) \leq 2e^{-\epsilon^2 pc /2}$$

In particular, picking $p=2 \frac{t \log n}{\epsilon^2 c}$ (for $t$ set a little later) will make the RHS of the above
less than $2e^{-  t \log(n)}$. To bound the probability \textit{there exists} a bad cut, we
apply union bound using Karger's cut-counting theorem.
Karger's cut-counting says that the If $G$ has a min-cut of size $c$, 
then the number of cuts of value $\alpha c$ is at most $n^{2\alpha}$. Thus

$$P(\exists S \text{ s.t. } |f_H(S) - c| \geq \epsilon c) \leq \sum_{\alpha=1}^{n^2}  n^{2\alpha} 2e^{- \alpha \log(n) t}$$
$$=2 \sum_{\alpha=1}^{n^2}  e^{2\alpha \log(n) - \alpha \log(n) t} = 2 \sum_{\alpha=1}^{n^2}  e^{\alpha \log(n)(2 -  t)}$$
We pick $t=5$, continuing:
$$= 2 \sum_{\alpha=1}^{n^2}  e^{-3\alpha \log(n)} \leq 2 \sum_{\alpha=1}^{n^2}  \frac{1}{n^3} \leq \frac{2}{n}$$
Which goes to zero. Note that increasing $t$ by 1 increases by 1 the polynomial degree showing up in the denominator here.

\item Consider a random bipartite graph on two vertex sets $L,R$ of size
$n$ each, in which every vertex in $L$ independently picks $d$
uniformly independent random neighbors in $R$. Given $\epsilon >
1/d$, prove that with high probability, every set $S$ in $L$ of
size $\alpha n /d$ has at least $|S|(1-\epsilon)d$ neighbors in
$R$, where $\alpha$ depends only on $\epsilon$.

\textbf{Solution.} Consider a single subset of the left side $S \subset L$ of size $|S| = \alpha n /d$.
The nodes in $S$ each pick $d$ neighbors independent uniform randomly with replacement
from the $n$ nodes on the right side. 

Let $\Gamma(S)$ be the neighbors of $S$. Counting the number of ways the choices in neighbors will all come from
a small subset of the right hand side, we directly bound

$$\Pr[ |\Gamma(S)|  < \alpha (1-\epsilon) d |S| ]  < { n \choose (1-\epsilon) d |S|  } \frac{((1-\epsilon) d |S|)^{|S| d}}{n^{|S| d}} $$
$$ \leq \left(\frac{n}{(1-\epsilon) d |S|}\right)^{((1-\epsilon) d |S|)}  \frac{((1-\epsilon) d |S|)^{|S| d}}{n^{|S| d}} $$
$$ = \left(\frac{d}{\alpha (1-\epsilon)}\right)^{\alpha (1-\epsilon)} [\alpha(1-\epsilon)]^{\alpha n} $$
$$= [\alpha(1-\epsilon)]^{\alpha (n-1+\epsilon)} d^{\alpha(1-\epsilon)}$$

Thus by union bound
$$\Pr[\exists S \text{ s.t. } |\Gamma(S)|  < \alpha (1-\epsilon) d |S| ]  < {n \choose |S|}  [\alpha(1-\epsilon)]^{\alpha (n-1+\epsilon)} d^{\alpha(1-\epsilon)}$$
$$\leq \left(\frac{n}{|S|}\right)^{|S|}  [\alpha(1-\epsilon)]^{\alpha (n-1+\epsilon)} d^{\alpha(1-\epsilon)} $$
$$ = \left(\frac{n}{\alpha n/d}\right)^{(\alpha n/d)}  [\alpha(1-\epsilon)]^{\alpha (n-1+\epsilon)} d^{\alpha(1-\epsilon)}$$
$$ = \left(\frac{d}{\alpha}\right)^{(\alpha n/d)}  [\alpha(1-\epsilon)]^{\alpha (n-1+\epsilon)} d^{\alpha(1-\epsilon)}$$

Thus we if choose $\alpha  = \frac{\epsilon^{\epsilon d} + 1}{2 \epsilon d \exp(\frac{\epsilon d + 1}{\epsilon d - 1})}$
will make the last expression less than 1 and diminish as
$n$ grows, continuing:
$$ \leq \left( \frac{1}{2} \right)^{\alpha n /d}$$


\item Let $G = (V,E)$ and denote the Laplacian of $G$ as $L_G$, as seen in homework 1.
We can consider our graph $G$ as an electrical network of nodes (vertices) and
wires (edges), where each wire has resistivity of one Ohm. The effective resistance
between vertices $i$ and $j$, denoted by $R^G(i, j)$ is the voltage difference between
$i$ and $j$ that would result if we sent one unit of external current between the
two vertices.

Prove that  $$R^G(i, j) = (\chi_i - \chi_j)^T L_G^+ (\chi_i - \chi_j)$$
where $\chi_i$ is vector of all zeros except for a 1 in position $i$, and $L_G^+$
is the Moore-Penrose pseudoinverse of the Laplacian.


\textbf{Solution.}
Let $G$ be an undirected graph and $B$ its corresponding $m \times n$ incidence matrix.
First, arbitrarily orient each edge of $E$, then define the $(e,v)$ entry of $B$ as $1$ if $v$ is the head of $e$,
and $-1$ if $v$ is the tail. All other entries are zero. Then it is easy to see that $L_G = B^T B$. We denote
the rows of $B$ as $b_e$. Note that $b_e^T = \chi_v-\chi_u$.

Now we define some electrical flow notation. For a vector $i_{\text{ext}}(u)$ of currents injected at the vertices, let
$i(e)$ be the currents induced in the edges (in the direction of orientation) and $v(u)$ the potentials
induced at the vertices. By KirchoffÕs current law, the sum of the currents entering a vertex is
equal to the amount injected at the vertex: $$B^T i = i_{\text{ext}}$$
By Ohm's law, the current flow in an edge is equal to the potential difference
across its ends times its conductance:
$$i = B v$$
Combining these two facts
$$i_{\text{ext}}(u) = B^T Bv = Lv$$

Now since $i_{\text{ext}} \perp 1$, and by the projection property of the pseudoinverse, we have 
$$v = L^+ i_{\text{ext}}$$

Recall that the effective resistance between two vertices $u$ and $v$ is defined as the potential
difference induced between them when a unit current is injected at one and extracted at the other.
We will derive an algebraic expression for the effective resistance in terms of $L^+$.
To inject and extract a unit current across the endpoints of an edge $e = (u, v)$, we set $i_{\text{ext}} = b_e^T = (\chi_v - \chi_u)$, which is clearly orthogonal to 1. The potentials induced by $i_{\text{ext}}$ at the vertices are given by $v = L^+ b^T_e$; to measure the potential difference across $e = (u, v)$, we simply multiply by $b_e$ on the left:
$$v(v) - v(u) = (\chi_v -\chi_u) = (\chi_v - \chi_u)^T L^+b_e^T$$
It follows that the effective resistance across $e=(u,v)$ is given by $b_e L^+ b_e^T$.

\end{enumerate}

\end{document}