\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{5}{Week 3}

Attempt the problems that seem interesting!  Easier exercises are marked with $(-)$ signs; harder ones are marked by $(*)$.  Open questions are denoted by writing $(**)$, as they are presumably quite hard.  Oh!  Also, typos build character: if you find any (not that there ever could be such things in my problem sets,) correct them to the most reasonable thing you can think of and proceed from there!

Also also!  I have too many typos in my notes.  If you find any, let me know!  I will offer rewards!  (Rewards to be defined soon.  Rewards will typically not be granted for grammatical or spelling errors, as frustrating/embarrassing as they are.)

\begin{enumerate}
\item  Suppose that $G$ is a graph, and $L_G$ is its Laplacian matrix.  Suppose we take $G$ and orient each of its edges, and look at the resulting directed \textbf{incidence}\footnote{The directed \textbf{incidence} matrix of a graph $G$ is the matrix with rows indexed by vertices, columns indexed by edges, $-1$'s wherever the column for edge $(i,j)$ intersects the row for vertex $i$, $1$'s wherever $(i,j)$ intersects $j$, and 0's elsewhere.} matrix $N_G$ of $G$.  Show that $N_GN_G^T = L_G.$
\item Using this, prove the claim we made in class today, that the Laplacian $L_G$ of any graph $G$ is positive-semidefinite\footnote{A matrix $A$ is called \textbf{positive-semidefinite} iff $\mathbf{x}^T (A\mathbf{x}) \geq 0$, for any vector $\mathbf{x}$.}.
\item $(-)$ Prove the second claim we made in class today: that any eigenvalue of a positive-definite matrix is $\geq 0$.
\item $(-)$  Finishing our proof of the Matrix-Tree theorem, part 1/2: show that 
\begin{align*}
\frac{\partial}{\partial x} \left( \det(xI - L) \right) \Big|_{x=0} = (-1)^{n-1} \cdot \mu_2\cdot \ldots \cdot \mu_n.
\end{align*}
\item Finishing our proof of the Matrix-Tree theorem, part 2/2: show that 
\begin{align*}
\frac{\partial}{\partial x} \left( \det(xI - L) \right) = \sum_{x=1}^n \det( tI - L^{\{x\}}),
\end{align*}
and thus that when we plug in zero to the above equation, we get $(-1)^{n-1} \cdot \sum_{x=1}^n l_{x,x}$.
\item Find a graph for which $\chi(G)$ is not equal to $\left\lceil 1 - \frac{\lambda_{\textrm{max}}}{\lambda_{\textrm{min}}} \right\rceil$ (i.e. that the bounds we discovered in class aren't always tight.)  How far away can you get $G$ from this bound?  
\item Use the Matrix-Tree theorem to prove that there are $n^{n-2}$ labeled trees on $n$ vertices.
\end{enumerate}


\end{document}