\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. 

\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.
\item From this, infer that there is an independent set with at least $n/2d$ vertices in any
graph with on $n$ vertices with $nd/2$ edges.
\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)$.



\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$.


\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$.



\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.
 


\end{enumerate}

\end{document}