%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the "author" and "collaborators" fields as
% appropriate. Write your solutions where indicated.
%

\def\inclsolns{0}
\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{comment}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{amsmath,amssymb,amsthm}

\input{macros}

\theoremstyle{definition}

\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi

\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother


\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}

\begin{document}


\begin{center}
{\Large CS 599B: Math for TCS, Spring 2022}

\bigskip

{\Large Homework 3}

\smallskip

Due: 10:00PM, Friday April 29, 2022 on Gradescope.

\end{center}

\ifnum\inclsolns=1
	\makeatletter
	\noindent Name: \@author \\
	Collaborators: \@collaborators
	\makeatother
\else
\fi

\paragraph{Instructions.}
Solutions must be typeset, with \LaTeX\ strongly preferred. You are encouraged to collaborate on the homework problems with each other in small groups (2-4 people). Collaboration may include brainstorming or exploring possible solutions together on a whiteboard, but should not include one person telling the others how to solve a problem. You must also write up the solutions independently (in your own words) and acknowledge your collaborators at the beginning of the first page.

You may freely use without proof any results proved in class, in Mark's lecture notes posted on the class webpage, or in the main body of the texts assigned as reading. Note that this excludes results that appear in the texts as problems and exercises. You may, of course, use such results but you have to prove them first.

\begin{problem}[Diameter vs. second eigenvalue] \hfill
	\begin{enumerate}[a)]
		\item Let $G$ be any connected, undirected, unweighted graph with diameter $r$. Show that for every $f \perp \one$,
		\[\min_{f \ne 0, f \perp \one} \frac{\langle f, Lf\rangle}{\langle f, f\rangle} \ge \Omega(1/rn)\]
		and conclude that $\lambda_2(G) \ge \Omega(1/rn)$.
		\begin{solution}
		\end{solution}
		
		\item Let $G$ be a $\gamma$-spectral expander for $\gamma \ge 1/2$. Show that $G$ has diameter at most $O(\log n)$.
		\begin{solution}
		\end{solution}
	\end{enumerate}
\end{problem}


\begin{problem}[Tightness of convergence rate]
	Let $G$ be a $d$-regular undirected graph with lazy walk matrix $\widetilde{W}$ having second eigenvalue $\omega_2 \ge 1/2$. In class, we showed that lazy walks on such graphs mix quickly. In this problem, you will show that the mixing time upper bound we proved is tight up to logarithmic factors.
	
	Show that for $\eps > 0$, there exists a vertex $s$ such that if $p_t$ is the length-$t$ lazy random walk starting at vertex $s$, then
	\[TV(p_t , \pi) \ge \eps\]
	unless $t \ge \Omega(\log(1/\eps) / (1-\omega_2))$.
\end{problem}


\begin{problem}[Random walks and effective resistances]
	Let $G$ be a connected, undirected, unweighted graph. Think of $G$ as a resistor network where every edge present in the graph has resistance $1$. Let $m = |E|$ be the number of edges in $G$. For vertices $a$ and $b$, define the \emph{hitting time} $H_{a, b}$ from $a$ to $b$ to be the expected number of steps a random walk starting at $a$ needs to take before reaching $b$. Note that $H_{b, b} = 0$.
	\begin{enumerate}[(a)]
		\item Show that for every $a \ne b$, we have $H_{a, b} = \sum_{u \sim a} \frac{1}{\deg(a)} (1 + H_{u, b})$.
		\item Consider an external current defined by $i_{\text{ext}}(u) = \deg(u)$ for every $u \in V \setminus \{b\}$ and $i_{\text{ext}}(b) = \deg(b) - 2m$. You can think of this as injecting $\deg(u)$ units of current into every vertex and having all of the current flowing out of vertex $b$. Let $v_b(a)$ denote the voltage induced at $a$ when $i_{\text{ext}}$ is applied, defining $v_b(b) = 0$. Show that for every $a \ne b$, we have $v_b(a) = \sum_{u \sim a} \frac{1}{\deg(a)}(1 + v_b(u))$.
		\item Show that for every $a, b$, we have $H_{a, b} = v_b(a)$. Hint: Argue that the linear system satisfied by both functions has a unique solution.
		\item Show that for every $a, b$, we have
		\[H_{a, b} + H_{b, a} = 2mR_{\text{eff}}(a, b).\]
	\end{enumerate}
\end{problem}


\end{document}





