\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{1}{Week 4}

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 $(*)$ Find a graph such that 
\begin{align*}
\omega(G) > \left\lceil 1 - \frac{\lambda_{\textrm{max}}}{\lambda_{\textrm{min}}} \right\rceil ,
\end{align*}
or show that no such crazy thing can exist.
\item $(*)$ Prove that any complete graph $K_n$ can be decomposed into triangles, if $n \equiv 1,3 \mod 6$.
\item Suppose you want to decompose the Petersen graph into complete bipartite graphs.  What is the smallest number of bipartite graphs you'll need?
\item Prove that the Lagrangian $f_G$ is positive-semidefinite on the space generated by all of the nonnegative eigenvectors of $A_G$, and negative-semidefinite on the space generated by all of the nonpositive eigenvectors of $A_G$,
\item Let $\alpha(G)$ denote the independence number of a graph.  Show, via the Lagrangian, that the adjacency matrix of any graph has at least $\alpha(G)$-many nonnegative and $\alpha(G)$-many nonpositive eigenvalues.
\end{enumerate}


\end{document}