\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 Using ideas in class, can you create a lower bound on the number of graphs you'd need if you were decomposing $K_n$ into cycles?  How about the number of Petersen graphs you'd need to decompose $K_n$?
\item To illustrate the power of the techniques we've been using here, attempt to prove the last theorem we discussed in class (Turan's theorem) \textbf{without} spectral tools: if $G$ is a graph on $n$ vertices with more than $\frac{r-2}{r-1}\cdot\frac{n^2}{2}$-many edges, $G$ contains a $K_r$.
\item The above says that the smallest number of edges in a triangle-free graph is at most $\lfloor n^2/4\rfloor$.  Can you find a triangle-free graph that realizes this bound?  Can you generalize this to $K_r$-free graphs?
\item Find a graph whose adjacency matrix is its incidence matrix\footnote{The \textbf{undirected incidence matrix} of a graph $G$ is the matrix with rows indexed by vertices, columns indexed by edges, $1$'s wherever $\{i,j\}$ intersects $j$, and 0's elsewhere.}.
\item $(*,$ some CS probably required)  In perfect graph theory/intro to graph theory, we discussed a pair of processes for making graphs that have high chromatic number and high girth: one of them was the Mycielski construction, which made triangle-free graphs of arbitrarily high chromatic number, and the other was the Descartes construction, which made girth 6 graphs of arbitrarily high chromatic number.  On input $K_2$ or $C_6$ or whatever you want, what do the eigenvalues of these graphs start to do if we keep applying these processes?  Do they start to look ``mostly'' symmetric (i.e. kind of bipartite), or do they start to clump up with one large positive eigenvalue and many negative eigenvalues (i.e. kind of like a complete graph)?
\end{enumerate}


\end{document}