\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{4}{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 In lecture, we gave a lower bound on the chromatic number in terms of eigenvalues.  Follow these three steps to get a far simpler proof that there is also an upper bound in terms of the eigenvalues:
\begin{enumerate}
\item Let $G$ be a graph.  Prove that if $\lambda_{\textrm{max}}$ is the largest eigenvalue of $A_G$, then $\delta(G) \leq \lambda \leq \Delta(G)$.
\item Let $G$ be a graph and $H$ be any induced subgraph of $G$.  Prove that
\begin{align*}
\lambda_{\textrm{min}}(G) \leq \lambda_{\textrm{min}}(H) \leq \lambda_{\textrm{max}}(H)\leq \lambda_{\textrm{max}}(G).
\end{align*}
\item Combine the two above results to show the following bound: for any graph $G$, we have $\chi(G) \leq \lambda_{\textrm{max}}(G) + 1$.
\end{enumerate}
\item Prove the following linear algebra results we mentioned in class:
\begin{enumerate}
\item Let $B$ be any real symmetric matrix.  Then, for any $\mathbf{v}$ with $||v|| = 1$, we have
\begin{align*}
\mu_{\textrm{min}} \leq  \langle B  \mathbf{v},  \mathbf{v} \rangle \leq \mu_{\textrm{max}},
\end{align*}
where $\mu_{\textrm{min}}, \mu_{\textrm{max}}$ are the smallest and largest eigenvalues of $B$, respectively.
\item $(-)$ The trace of a matrix is equal to the sum of its eigenvalues (counted with respect to their algebraic multiplicity.)
\end{enumerate}
\end{enumerate}


\end{document}