\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 {\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$. \item 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$$ \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. \end{enumerate} \item 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$. \item 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} \item 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} \end{enumerate} \end{document}