\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 Consider the following generalization of the friendship question: suppose we have a graph $G$ such that every pair of vertices have exactly two neighbors in common.  What kinds of graphs are possible?  
\item Let $q = 4t+1$ be some prime power that's congruent to 1 mod 4, and let $\mathbf{F}_q$ be a finite field of size $q$.  Turn this into a graph by considering its elements as vertices, and connecting two elements whenever their difference is a nonzero square.  

Show that this graph (the Paley graph) is a strongly regular graph, with parameter set $(4t+1, 2t, t-1, t)$.  What are its eigenvalues?
\item Show that the dual polytope to the tesseract is a strongly regular graph, if we think of it as a collection of vertices linked by edges.
\item Check that the graph\footnote{This is known as the Shrikhande graph.} drawn below is a $(16,6,2,2)$.
\begin{center}
\includegraphics[width=3in]{shrikhande.pdf}
\end{center}
\item Take a latin square\footnote{A \textbf{latin square} is a $n \times n$ array filled with the symbols $1, \ldots, n$, so that no symbol is repeated in any row or column.}, and turn it into a graph by using its $n^2$ cells as vertices, and connecting two vertices iff they lie in the same row, same column, or contain the same symbol.  Show that this graph is strongly regular.  What are the parameters of this graph?  How does it change when you use different latin squares?
\item Conclude from the previous two problems that there can be cospectral nonisomorphic strongly regular graphs with the same parameter set.
\end{enumerate}


\end{document}