\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\#1 --  Due Thursday 01/26/12}
\vspace{5pt}

\begin{enumerate}
\item (10 points){\bf (Lovasz, Pelikan, and Vesztergombi 7.3.9)} Prove that at least
one of $G$ and $\overline{G}$ is connected. Here, $\overline{G}$ is a
graph on the vertices of $G$ such that two vertices
are adjacent in $\overline{G}$ if and only if they are not adjacent in $G$.


\vspace{10pt}
{\Large Solution:} 

Let $G$ be a disconnected graph in which case we can decompose it into $k$ connected 
components $C_1, C_2, \dots, C_k$. We want to show that $\overline{G}$ is connected 
i.e. there is a path between any $u$ and $v$ in  $\overline{G}$. In the case that $u$ 
and $v$ are in different components we know that there exist an edge (a path of length 
one) between them in $\overline{G}$. In the case that $u$ and $v$ are in the same 
component, say $C_i$, we can construct a path of two edges between them in $\overline{G}$
as follows. Pick any vertex $w$ from some other component $C_j$ for $j \neq i$ and 
note that edges $\{u,w\}$ and $\{w, v\}$ are in $\overline{G}$. Thus $u,w,v$ is a 
path in $\overline{G}$ and hence $\overline{G}$ is connected. 

\item (10 points)A vertex in $G$ is \textit{central} if its greatest distance from any other vertex is as small as possible.
This distance is the \textit{radius} of $G$. 

\begin{enumerate} 

\item Prove that for every graph $G$

$$ \text{rad } G \leq \text{diam } G \leq 2 \text{ rad } G$$
\vspace{10pt}
{\Large Solution:} 
Since the diameter is the longest shortest path in the graph, and the radius is just a particular shortest path, we have $\text{rad } G \leq \text{diam } G$. Now, since we can always reach any vertex $t$ by going to the center first, then going to $t$, incurring a cost of at most twice the radius, we have $ \text{diam } G \leq 2 \text{ rad } G$.

\item Prove that a graph $G$ of radius at most $k$ and maximum degree at most $d \ge 3$ has fewer than
$\frac{d}{d-2} (d-1)^k$ vertices.

\vspace{10pt}
{\Large Solution:} 
Let $z$ be a central vertex in $G$, and let $D_i$ denote the set of vertices of $G$ at distance $i$ from $z$. Then
$\cup_{i=0}^k D_i$ is all the vertices in the graph. Clearly, $|D_0| = 1$ and $|D_1| \leq d$. 
For $i \geq 1$ we have $|D_{i+1}| \leq (d-1)|D_i|$, because every vertex in $D_{i+1}$ is a neighbor
of a vertex in $D_i$ (why?), and each vertex in $D_i$ has at most $d-1$ neighbors in $D_{i+1}$ (since it
has another neighbor in $D_{i-1}$). Thus $D_{i+1} \leq d(d-1)^i$ for all $i<k$ by induction, giving

$$|G| \leq 1+ d \sum_{i=0}^{k-1} (d-1)^i = 1 + \frac{d}{d-2}((d-1)^k-1) < \frac{d}{d-2} (d-1)^k$$


\end{enumerate}


\item (10 points) In class we proved Cayley's theorem which states that the number of labeled trees
on $n$ vertices is is given by $n^{n-2}$. What is the number of labeled binary trees on
$n$ vertices?

For this problem you may use the following definition of a binary tree. A binary tree is a tree in which every
vertex has degree either $1$ or $3$.

\vspace{10pt}
{\Large Solution:} 

First note that for such a graph $n$ is even. This is true since the sum of the
degrees of any graph is twice the number of edges, an even number. Thus, since all 
degrees are odd the must be an even number of vertices.

Consider a Prufer code generated by one of these trees. We know that the code is
of length $n-2$ and a vertex may appear in it; its degree minus one times. Since
all vertices have degree either one or three we conclude that the code will contain
only degree three vertices each appearing exactly twice in the code. Thus the number
of degree three vertices is $(n-2)/2$ and the number of ways to choose them from the
$n$ available vertices is $\binom{n}{\frac{n-2}{2}}$.

The remaining problem is to count the number of ways we can arrange the degree
three vertices within the Prufer code. Note that if all entries of the code
were distinct the answer would be $(n-2)!$, the number of ways to permute $(n-2)$
items. However, each item appears exactly twice in the code so for each such pair we 
would enumerate the same code twice. Since the number of pairs is $(n-2)/2$ the final 
formula is 
\[ \binom{n}{\frac{n-2}{2}} \frac{(n-2)!}{2^{\frac{n-2}{2}}} ~ .\]



\item (20 points) Finish the proof of the matrix-tree theorem started in the lecture. An oriented incidence matrix $B$ of a directed  graph $G(V,E)$ is a matrix with $n = |V|$ rows and $m = |E|$ columns with entry $B_{ve}$ equal to $1$ if edge $e$ enters vertex $v$ and $-1$ if it leaves vertex $v$. For an undirected graph, we will use an arbitrary orientation of the edges. Let $M = B B^T$. Note, that $M$ (or Laplacian) is independent of the orientation of the edges.

\begin{enumerate}

\item Prove that $rank(M) = n - w$ where $w$ is the number of connected components of $G$. 

\item   Show that for
any $i \in \{1,\dots,n\}$, \[\det M_{ii} = \sum_N (\det N)^2,\]
where $M_{ii} = M\backslash \{i^{th}$ row and column\}, and $N$ runs over
all $(n - 1) \times (n - 1)$ submatrices of $B\backslash\{i^{th}$ row\}.
Note that each submatrix $N$ corresponds to a choice of $n-1$ edges of $G$.

\item Show that
\[\det N =
\left\{
\begin{array}{rl}
\pm 1 & \mbox{if edges form a tree} \\
    0 & \mbox{otherwise}
\end{array}
\right.\]

This implies that $t(G) = \det M_{ii}$, where $t(G)$ is the number of spanning
trees of $G$. In this definition of a tree, we treat a directed edge as an
undirected one.

\item Show that for the complete graph on $n$ vertices $K_n$,
\[\det M_{ii} = n^{n-2}.\]  Conclude that this implies Cayley theorem.

\end{enumerate}

\vspace{10pt}
{\Large Solution:} 

\begin{enumerate}

\item Consider a single component, and consider a vector of length $n$ that has 1s where the nodes of the component are, and zeros elsewhere. This vector will be in the nullspace of $M$ (why?). Call this vector $v_i$ for the $i$'th component. It is easy to check all the $v_i$ are mutually orthogonal. Thus the null space has dimension at least $w$.
It remains to show that any other vector in the nullspace of $M$ is a linear combination of the $v_i$'s. Note that if $Mx = 0$, then $x^T M x = 0$. For the Laplacian of a graph, we also know 
$$x^T M x = \sum_{(i,i) \in E} (x_i-x_j)^2$$
For the above sum to be zero, all entries in the sum must vanish. Thus for any nonzero $x_i$, all other $x_j$ in the same component as $i$ must have the same value.

Thus any vector that satisfies $M x=0$ and thus $x^T M x=0$, must be a linear combination of the indicator vectors for the components. Thus there are no more than $w$ independent vectors in the nullspace of $M$, so the rank of $M$ is exactly $n-w$.

To see why $x^T M x$ decomposes as a sum over the edges of the graph, see this lecture\footnote{\url{http://www.cs.yale.edu/homes/spielman/561/lect02-09.pdf}}, which
also lists many other interesting properties of the Laplacian.


\item Given an $r \times q$ matrix $C$ and an $q \times r$ matrix $D$, the Cauchy-Binet 
formula states that $det(CD) = \sum_S det(C_S) det(D_S)$ where the sum is over all 
possible size $r$ subsets $S$ of $\{1,2,\dots,q\}$. Note that $M_{ii} = B_i B^T_i$ and  apply 
the Cauchy-Binet formula with $r = n - 1$, $q = m$, $C = B_i$ and $D = B^T_i$. The 
identity $det(A) = det(A^T)$ then yields the final result. A proof of the Cauchy-Binet 
formula can be found at the following link. 
\\ \url{http://www.lacim.uqam.ca/~lauve/courses/su2005-550/BS3.pdf}


\item Given $N$ consider the subgraph of $G$ induced by the choice of edges specified
by $N$. Assume that this subgraph contains a cycle. Furthermore, for now, assume this
cycle is directed. Index the vertices of the cycle with set $I = \{i_1, i_2, \dots, i_k\}$.
Define a $n-1$ vector $c$ with ones at indices of $I$ and zeros elsewhere. Notice
that $u = Nc = 0$. This is true since any $j^{th}$ entry of $u$ is the sum of $+1$
and $-1$ indicating a cycle edge entering vertex $j$ and leaving it respectively.
This implies that the columns of $N$ are linearly dependent and thus $det(N) = 0$.

For a cycle that is not directed note that we can set the entries in the vector
$c$ from $\{-1,1\}$ and reverse the sign of any column and in doing so flip the 
direction of any edge in the cycle. Also, note that the removed row does not
ruin the result since the corresponding entry is never in $u = Nc$.

Now assume we have a tree. First use the following procedure to create a sequence 
$i_1, i_2, \dots, i_{n-1}$. Pick any leaf $i_1$ and remove it along with an incident
edge $e_{i_1}$. Then a leaf $i_2$ with incident edge $e_{i_2}$, etc... . At each step
we still have a tree but with one less vertex. Continue the procedure until all 
edges of the tree have been enumerated. Now construct a permutation matrix $P$ to
to rearrange the rows and columns of $N$ in the same order as they were removed i.e.
send vertex $i_k$ to row $k$ and edge $e_{i_k}$ to column $k$. Note that $PNP$ is 
lower triangular since $i_k \notin e_{i_r}$ for $k < r$ (otherwise $i_k$ would not be a 
leaf at $k^{th}$ step). Furthermore all entries on diagonal are $\pm 1$ and so 
$det(N) = det(PNP) = \pm 1$.

Lastly, recall that a tree always has at least two leaves and so we can avoid
picking the vertex corresponding to the removed row during this procedure.

\item Since $det(M_{ii})$ is the number of spanning trees the total number of trees 
on $n$ vertices will be given by the complete graph $K_n$ since any possible set of 
edges may be selected.

Consider the diagonal entry of $M_{ii}$. A diagonal entry is the degree of vertex $j$ 
which is $n-1$ for a complete graph. An off-diagonal entry is a dot product between 
rows corresponding to distinct vertices. Since we have a complete graph, we have an 
edge between them and so the dot product is $-1 \cdot 1 = -1$. 

We can then write $M_{ii}$ in form  $n I - ee^T$ where $e$ is a vector
of all ones.  The determinant can be computed using the ShermanÐMorrison formula
as follows.
\[det(M_{ii}) = (1 - \frac{e^T I e}{n}) det(n I) = (1 - \frac{n-1}{n}) n^{n-1} = n^{n-2}.\]

\end{enumerate}

\item 
(20 points)
In this exercise, we will prove Polya's Theorem using the the connections between  random walks on a graph and electric currents in a
corresponding network of resistors.


{\noindent \bf Polya's Theorem.} Simple random walk on a $d$-dimensional
lattice is recurrent for $d=1,2$ and transient for $d>2$.


Let $G$ denote the lattice graph. Let $G(r)$ be the subgraph of $G$
induced by the nodes with distance at most  $r$ from the origin. Denote by $\partial
G(r)$ the set of nodes that are exactly $r$ units away from the
origin. Let $p{(r)}$ be the probability that a random walk on
$G{(r)}$ starting at the origin reaches $\partial G(r)$ before
returning to origin and let $p=\lim_{r\rightarrow \infty}p(r)$ be the
probability for the infinite graph. An infinite walk is recurrent
if and only if the limit is 0.

To determine $p$ electrically, we simply ground all the nodes of
$\partial G(r)$, maintain the origin at one volt, and measure the
current flowing into the circuit. We will have
$$p(r)=\frac{i(r)}{2d}=\frac{1}{2dR_{\mbox{eff}}(r)}$$
where $d$ is the dimension and $R_{\mbox{eff}}(r)$ is the effective resistance
from the origin to $\partial G(r)$.

Let $R_{\mbox{eff}}=\lim_{r\rightarrow \infty}R_{\mbox{eff}}(r)$. Then $p=0$ iff
$R_{\mbox{eff}}$ is infinite.

By using the above connection, prove Polya's theorem for one
dimension.

\begin{enumerate}
\item[(a)] Show that simple random walk on $d$-dimensional lattice is
recurrent for $d=1$.
\end{enumerate}

For $d=2$, we need to use a shorting technique: decreasing the resistance on any edge to zero is equivalent to merging
the vertices at the endpoints. From the point of view electrical circuits
this is equivalent to adding a short circuit between the two ends of the resistor. 



\begin{enumerate}
\item[(b)] Show that simple random walk on $d$-dimensional lattice is
recurrent for $d=2$.
\end{enumerate}


 
To get an upper bound for higher dimensions, we need to use a cutting technique to cut the
grid into trees.  Increasing the resistance to infinity on any edge is equivalent to
removing this edge.  This operation will not decrease the
effective resistance between voltage and ground.

For $d=3$ note that all vertices on each plane $x + y + z = 2^k-1$ have
the same potential. We can remove enough wires from the $\mathbbm{Z}^3$ grid
to create a tree with $3^k$ vertices on each of the above planes. Compute the effective resistance of an infinite binary tree and then
embed it into a 3-dimensional grid to prove the following:

\begin{enumerate}
\item[(c)] Show that simple random walk on $d$-dimensional lattice is
transient for $d=3$.
\end{enumerate}

\vspace{10pt}
{\Large Solution: } 

First, let $d = 1$. Note that $\partial G(r) = \{-r,r\}$. Consider changing the 
given network over $G(r)$ by connecting the vertices of $G(r) = \{-r,r\}$ by 
a wire of zero resistance. The resulting network is equivalent to a cycle 
$0,1,\dots,r,-r+1,-r+2,\dots,-1,0$ with vertex $0$ at voltage $1$ and vertex $r$ at 
ground. The resistors along each path from $0$ to $r$ can be added in series to get
two resistors in parallel, each with resistance of $r$.  Adding these in parallel
yields $r \cdot r/(r + r) = r/2$. We now have
\[ p(r) = \frac{1}{2 d R_{eff}} = \frac{1}{r} \]
which is zero as $r \to \infty$ i.e. the walk is recurrent for $d = 1$.


Similarly to the $d=1$ case, for $d = 2$, merge all the vertices of
$\partial G(r)$ into one vertex at ground. From the point of view of the
electrical network this is equivalent to replacing all wires on
connecting vertices of $\partial G(r)$ with ones of resistance zero
(i.e. a superconductor). Note that while this changes the effective
resistance of $G(r)$, the resulting effective resistance must be smaller
(it is easy see this more formally in any electrical network by applying
resistance in series and parallel rules). 

The new electrical network is a path from the origin vertex $0$ at
voltage $1$ to vertex $r$ at ground such that between each pair of
vertices $(k,k+1)$ there are $|\partial G(k+1)|$ edges. Note that
$|\partial G(k)| = 4(2(k+1)) - 4 = 8k + 4$, the number of vertices on
the boundary of each square with side $2k$. Each has unit resistance and
may be added in parallel so that the effective resistance between
vertices $k$ and $k+1$ is $1/(8k+4)$. The resistors along the
path from the origin up to $r$ are added in series yielding 
\[ p(r) = \frac{1}{2d R_{eff}} \leq 
\left( \sum_{k=0}^{r-1} \frac{1}{2k+1} \right)^{-1} \]
and so $p(r) \to 0$ as $r \to \infty$ since the sum diverges.

Note, that in the $d=1$ and $d = 2$ cases there are not enough paths
from the origin to the boundary to create enough resistors in parallel
so that the effective resistance is a converging sum as $r \to \infty$.
For $d=3$ we want to show that $\lim_{r \to \infty} p(r)$ is bounded
away from zero and thus need to place an upper bound on the effective
resistance and show that it converges in the limit.
Note replacing any number of resistors with resistances of infinite
value increases the effective resistance between the origin and the
boundary. This is equivalent to removing some of the wires as air is
assumed to have infinite resistance. 

Each vertex in $G(r)$ has coordinates $(x,y,z) \in \mathbbm{Z}^3$. We will
remove vertices and edges until a subgraph of $G(r)$ with a larger effective
resistance remains.  Define $e_x = (1,0,0)$, $e_y = (0,1,0)$ and $e_z =
(0,0,1)$. For $p_n$ on plane $x + y + z = 2^n -1$ with $n \in
\mathbbm{N}$ we keep the path $p_n + \alpha e_x$ for $\alpha =
1,2,3,\dots,2^n$ so that the effective resistance along the path is
$2^n$. Similarly, keep paths $p_n + \alpha e_y$ and $p_n + \alpha e_z$.
Note that the vertices $p_n + 2^n e_x$, $p_n +2^n e_y$ and $p_n + 2^n
e_z$ are on the plane $x + y + z = 2^{n+1} -1$. We repeat this procedure
starting at the origin $p_0 = (0,0,0)$ tripling the number of vertices
at each successive plane $x + y + z = 2^n-1$ and until we hit the boundary
$\partial G(r)$. We may extend the boundary up to the next plane $x + y
+ z = 2r$ increasing the resistances of each path to $r$ with each path
leading to ground.

Note that due to symmetry the voltage potential at each plane $x + y + z = 2^n-1$
is constant
and we have a circuit which looks like a trinary tree with a resistance on each
edge leading to the level with $3^n$ vertices is $2^{n-1}$. The effective resistance
between the levels of the tree (between the planes $x + y + z = 2^n-1$) is then
$2^{n-1}/3^n$ and the effective resistance of the resulting circuit is 
\[ R_{eff} = 2^0 \frac{1}{3} + 2 \frac{1}{3^2} + 2^2 \frac{1}{3^3} + \cdots  
= \frac{1}{3} \sum_{k=0}^{\log(2r+1)} \left( \frac{2}{3} \right)^k
\to 1 \]
Therefore,
\[ \lim_{r \to \infty} p(r) \geq \lim_{r \to \infty} \frac{1}{2 d R_{eff}} \geq \frac{1}{6} \]
and so the walk is transient for $d = 3$. Note that we can similarly bound
$p(r)$ for $d > 3$ by removing all edges in those dimension to reduce to the
$d=3$ case.



\end{enumerate}

\end{document}