\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}

\lecture{4: Petersen Graph 2/2; also, Friendship is Magic!}{Week 4}

We did a ton of things yesterday!  Here's a quick recap:
\begin{enumerate}
\item If $G$ is a $(n,k,\lambda, \mu)$ strongly regular graph, then 
\begin{align*}
k(k-\lambda - 1) = \mu(n-k-1).
\end{align*}
\item If $G$ is a strongly regular graph, then $A_G$ has at most three eigenvalues.  Explicitly, these three eigenvalues are
\begin{align*}
k, \frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2},
\end{align*}
with multiplicities
\begin{align*}
1, \frac{1}{2}\left(n-1 \pm \frac{(n-1)(\mu-\lambda) - 2k}{\sqrt{(\mu-\lambda)^2 + 4(k-\mu)}}   \right).
\end{align*}
\item As a very specific corollary of the above, these multiplicities are \textbf{integers}.  This means that either the two non-$k$ eigenvalues of $A_G$ occur with the same multiplicity (i.e. $(n-1)(\mu-\lambda) - 2k = 0$,) or the eigenvalues themselves are all integers.
\item In the case where these eigenvalues occur with the same multiplicity, our graph is of the form $(4t+1, 2t, t-1, t)$.   
\item Specifically: if we're looking for a SRG of the form $(n,k,0,1)$, it either has to have integral eigenvalues or is a $(5,2,0,1)$ -- i.e. a pentagon.
\end{enumerate}

Our goal yesterday was to find all of the graphs that were Petersen-like: that's why we started studying strongly regular graphs, and that's why we proved the statements above.  How can we use these observations to find the others?
\section{Finding All Of The SRGs}
So: as discussed above, we can assume that the eigenvalues $r,s$ of our strongly regular graph's adjacency matrix are integral (as otherwise we're looking at a pentagon.)  What else can we conclude?

Well: if we use the relation
\begin{align*}
k(k-\lambda - 1) = \mu(n-k-1)
\end{align*}
we derived earlier, and plug in $\lambda = 0, \mu = 1,$ we get
\begin{align*}
n = k^2 + 1.
\end{align*}

That's something.  What else can we get?  Well: if $r,s$ are integers, then in specific the denominator 
\begin{align*}
 \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}
 \end{align*}
must also be an integer.  In specific, because $\lambda = 0, \mu = 1$, this means that
\begin{align*}
\sqrt{4k -3}
\end{align*}
is an integer: i.e. that $4k-3$ is a square of some integer!  Denote this square as $s$, and by solving for $k$ write $k = \frac{1}{4}(s^2 + 3)$.  Then, if you plug first our formula $n = k^2 + 1$ and then this formula $k = \frac{1}{4}(s^2 + 3)$ into the formula for one of our multiplicities (say the one for $r$), we get
\begin{align*}
a &= \frac{1}{2}\left(n-1 + \frac{(n-1)(\mu-\lambda) - 2k}{\sqrt{(\mu-\lambda)^2 + 4(k-\mu)}}   \right)\\
& = \frac{1}{2} \left( (k^2 + 1) - 1 + \frac{(k^2 + 1 - 1)(1) - 2k}{\sqrt{4k-3}} \right) \\
& = \frac{1}{2} \left( \frac{1}{16}(s^2+3)^2 + \frac{\frac{1}{16}(s^2+3)^2 - \frac{1}{2}(s^2+3)}{s} \right) \\
\Rightarrow 32a \cdot s &= s(s^2 + 3)^2 + (s^2+3)^2 - 8(s^2 + 3) \\
&= s^5 + s^4 + 6s^3 - 2s^2 + 9s - 15 \\
\Rightarrow 15 &= s^5 + s^4 + 6s^3 - 2s^2 + (9 - 32a)s\\
 &= s\left( s^4 + s^3 + 6s^2 - 2s + (9 - 32a)\right).\\
\end{align*}
Because all of the quantities on the right-hand-side above are integers, we must have that $s$ divides $15$: i.e. $s$ can be one of $1,3,5,$ or $15$, which forces $k$ to be one of $1,3,7, 57$.  Plugging in, using our identity $n = k^2 + 1$, and remembering the pentagon which we already considered, we can see that any possible $(n,k,0,1)$ graph must have one of the following five parameter sets:
\begin{align*}
(2,1,0,1), (5,2,0,1), (10,3,0,1), (50, 7,0,1), (3250, 57, 0,1).
\end{align*}
The first is just $K_2$; the second is $C_5$, a pentagon; and the third is the Petersen graph.  How about the fourth?
\newpage 
\section{A Really Pretty Picture}
\begin{center}
\includegraphics[width=6in]{hoffman_singleton.pdf}
\end{center}
This graph is the \textbf{Hoffman-Singleton} graph\footnote{Roughly speaking, it's a bunch of Petersen graphs inside of Petersen graphs.  Depending on which meme you prefer, you can caption this as either ``Peteception'' or ``Yo dawg, I heard you like the Petersen graph so I put a Petersen graph in your Petersen graph so you can disprove conjectures while you disprove conjectures.'' }, and is formed as follows: Take five stars $P_0, \ldots P_4$ and five pentagons $Q_0, \ldots Q_4$.  Enumerate the vertices of each pentagon and star in counterclockwise order as $0,1,2,3,4$, and  for every $i,j,k$ connect the vertex $i$ in $P_j$ to the vertex $i + jk$ in $Q_k$.

It is also absolutely \textit{gorgeous}.
\newpage
You know what's also amazing -- dare I say it, magical?
\section{Friendship is Magic!}
So magical, that we even have a theorem about it (whose name I swear I have not made up, this is what it is in the literature:)
\begin{theorem}
(Friendship Theorem)  Suppose you have a gathering of people wherein every two people have exactly one friend in common.  Then there is someone at this gathering who is friends with everyone.
\end{theorem}
In the language of graph theory, we're saying that any graph where every two vertices have exactly one common neighbor is a collection of $k$ triangles joined along a common vertex:
\begin{center}
\includegraphics[width=4.5in]{Friendship_graphs.pdf}
\end{center}
We call such a graph a \textbf{friendship} graph.



How can we prove our theorem? With our earlier tools about strongly regular graphs!
\begin{proof}
Specifically: let $G$ be any such friendship graph.  If $G$ is regular, then it is strongly regular (as any two adjacent or nonadjacent vertices have exactly one neighbor in common) with parameter set $(n,k,1,1)$.  For what values of $k$ do our integrality conditions say that these are possible?

We know that 
\begin{align*}
\frac{1}{2}\left(n-1 + \frac{(n-1)(\mu-\lambda) - 2k}{\sqrt{(\mu-\lambda)^2 + 4(k-\mu)}}   \right) &= 
\frac{1}{2}\left(n-1 - \frac{2k}{\sqrt{ 4k-4}}   \right)\\
 &= \frac{1}{2}\left(n-1 - \frac{2k}{\sqrt{ 4k-4}}   \right)\\
 &= \frac{1}{2}\left(n-1 - \frac{k}{\sqrt{k-1}}   \right)\\
\end{align*}
must be an integer: i.e. that $k/\sqrt{k-1}$ is an integer.  But (via the quadratic formula and some algebra,) we know that this can only happen when $k=2$, in which case our graph is a triangle.

Therefore, in any case where we have more than three people, our graph is not regular.  In an attempt to find out just what we do know about our graph, we start writing down observations about what we're seeing:
\begin{itemize}
\item Because of the unique common neighbor feature of our graph, we don't have any 4-cycles.
\item Conversely, given any pair of adjacent vertices $i,j$, let $k$ be their common neighbor.  This forms a triangle: therefore, every vertex has degree at least 2, as every vertex is part of at least one edge.
\item Now, take any pair of nonadjacent vertices $i,j$ (these exist because our graph is not regular, and therefore in particular not the complete graph.)  Let $k$ be the common neighbor of $i$ and $j$, $m_1$ be the common neighbor of $j,k$ and $n_1$ the common neighbor of $i,k$.

For every vertex $x \in N(i), x \neq k, n_1$, look at the unique common neighbor $f(x)$ that $j$ and $x$ share.  

If there are two distinct values $x_1, x_2$ for which $f(x_1) = f(x_2)$, then the 4-tuple $x_1, j, x_2, f(x_1)$ is a 4-cycle, a contradiction: therefore, all of the values of $f(x)$ are distinct and involve edges from these distinct values to $j$!  Using symmetry, we can reverse this argument to show that the same thing holds for $N(j)$; this tells us us that we have $|N(i)| = |N(j)|$.  In particular, whenever two vertices are not connected, they must have the same degree.
\item Our graph is not regular: therefore, there must be at least three vertices $i,j,k$ such that one of these three vertices has degree different than the other two.  Let $k$ be this vertex without any loss of generality.

 We claim that $k$ is in fact connected to every vertex.  To see this, suppose not: i.e. take any other vertex $x$ that's not connected to $k$.  Then $\deg(x) = \deg(k)$, and in particular this means that $x$ also must have an edge to $i$ and $j$: i.e. we have a 4-cycle, which is impossible.  Therefore, $k$ is in fact connected to everything, and we've proven our claim!
\end{itemize}
\end{proof}
\end{document}