\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 $(-)$ Prove the three claims we made about degenerate cases for strongly regular graphs $G$ of the form $(n,k,\lambda,\mu)$ in class:
\begin{enumerate}
\item If $\mu = 0$, then $G$ is a disjoint union of $K_{k+1}$'s.
\item If $k = n-1$, then $G$ is $K_n$.
\item If $\lambda = k-1,$ then $G$ is a disjoint union of $K_k$'s.
\end{enumerate}
\item Find another graph that is a $(n,k,0,1)$-SRG.
\item By counting paths of length three in a SRG $G$ with parameters $(n,k,\lambda,\mu)$, show that
\begin{align*}
k(k-\lambda - 1) = \mu(n-k-1).
\end{align*}
\item By using our decomposition of $A_G$ into the sum of other matrices, prove in a different way the claim (that $ k(k-\lambda - 1) = \mu(n-k-1)$) that we made above.
\item Show that if $\Delta(G)$ is an eigenvalue of $A_G$, then it has multiplicity 1: i.e. the only eigenvector for $\Delta(G)$ is the all-1's vector, if it is indeed an eigenvalue.
\item Prove the last claim in the lecture notes: if the multiplicities of the two non-$k$ eigenvalues of a SRG are distinct, their corresponding eigenvalues are integral.
\end{enumerate}


\end{document}