\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{3: The Petersen Graph is Weird, part 1/2}{Week 4}
The Petersen graph.
\begin{center}
\includegraphics[width=5in]{petersen.pdf}
\end{center}
Just \textbf{look} at it.\\
\ldots \\
Man.  So gorgeous.\\
\ldots \\
\ldots anything else like it?
\section{Yes!}

What do we mean by ``like\footnote{Do we mean ``like,'' or ``\textbf{like}-like?''}?'' What properties does the Petersen graph have that we'd like to find in other graphs?  

Well, one nice property it has is that it's \textbf{regular}: i.e. all of its vertices have degree 3.  Furthermore, it's \textbf{really} regular: if you look at any two adjacent vertices, they have no neighbors in common, and if you look at any two nonadjacent vertices, they have precisely one vertex in common.  

Because this is such an awesome property, let's give it a name!  Call such graphs \textbf{strongly regular} graphs (SRGs,) with parameters $(n,k,\lambda, \mu)$, if they have 
\begin{itemize}
\item $n$ vertices,
\item are regular with degree $k$,
\item every pair of adjacent vertices have $\lambda$ neighbors in common, and
\item every pair of nonadjacent vertices have $\mu$ neighbors in common.
\end{itemize}

In this notation, the Petersen graph is a $(10,3,0,1)$-SRG.

There are a few degenerate cases of SRG's: we note them here, and recommend that you check the validity of these claims on your own.
\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$; if $k = 0$, then $G$ is a disjoint union of isolated vertices.
\item If $\lambda = k-1,$ then $G$ is a disjoint union of $K_k$'s.
\end{enumerate}

Apart from these cases, what can we say about these Petersen-like graphs?  We study this in the next section:
\section{The Integrality Conditions}
Strongly regular graphs, as it turns out, are \textbf{magic}.  We make this rigorous through the next three lemmas:

\begin{lemma}
Suppose that $G$ is a strongly regular graph, with parameters $(n,k\lambda, \mu)$.  Then $A_G$ has at most three eigenvalues.
\end{lemma}
\begin{proof}
Consider $A_G^2$.  Specifically, consider $(A_G^2)_{ij}$, which we can write as
\begin{align*}
(a_{i1}, \ldots a_{in}) \cdot \left( \begin{array}{c} a_{1j} \\ \vdots \\ a_{nj} \\ \end{array}  \right) &= \sum_{i=1}^n a_{ik}a_{kj}. \\
\end{align*}
What is this?  
\begin{itemize}
\item If $i=j$, then we have that this is just the number of elements adjacent to vertex $i$, which is $k$ because our graph is regular.
\item If $(v_i, v_j)$ is an edge in our graph, then the elements $a_{ik}a_{kj}$ of this sum are nonzero precisely where $v_k$ is a common neighbor of $v_i$ and $v_j$; so this counts the number of common neighbors to $v_i$ and $v_j$, and is thus $\lambda.$
\item If $(v_i, v_j)$ is \textbf{not} edge in our graph, then the elements $a_{ik}a_{kj}$ of this sum are still nonzero precisely where $v_k$ is a common neighbor of $v_i$ and $v_j$; so this counts the number of common neighbors to $v_i$ and $v_j$, and is thus $\mu$.
\end{itemize}
So, in other words, we've just proven that 
\begin{align*}
A_G^2 &= k \cdot I + \lambda \cdot A_G + \mu \cdot A_{\overline{G}}\\
&= k \cdot I + \lambda \cdot A_G + \mu \cdot \left(J - I - A_G \right) \\
&= (k - \mu) \cdot I + (\lambda - \mu) \cdot A_G + \mu \cdot J, \\
\end{align*}
where $J$ is the all-1's matrix.

This looks suspiciously like a quadratic equation!  Except, you know, with matrices.  Does this form mean that our matrix can only have three eigenvalues?   Well: let's see!   Recall from earlier in the course that if $G$ is a $k$-regular graph, then the all-1's vector is an eigenvector for its adjacency matrix with eigenvalue $k$: this is because $A_G \cdot (1,\ldots 1)$ returns a vector with entries corresponding to the degrees of the vertices in $G$.   By the spectral theorem, we know that $A_G$ has an orthogonal basis of eigenvectors, and furthermore that we can pick such a basis that contains $(1,\ldots 1)$ as an element.

Choose any \textbf{other} eigenvector, $\mathbf{y}$, and let $s$ be its corresponding eigenvalue.  We know that $\mathbf{y}$ is orthogonal to the all-1's vector.  Therefore, on one hand we have
\begin{align*}
A_G^2\mathbf{y} &= \left((k - \mu) \cdot I + (\lambda - \mu) \cdot A_G + \mu \cdot J\right)\mathbf{y}\\
 &= (k - \mu) \cdot I\mathbf{y} + (\lambda - \mu) \cdot A_G\mathbf{y}  + \mu \cdot J\mathbf{y}\\
 &= (k - \mu)\mathbf{y} + (\lambda - \mu) \cdot s \mathbf{y}  + 0,\\
\end{align*}
while on the other we have
\begin{align*}
A_G^2\mathbf{y} = s\cdot A_G \mathbf{y} = s^2\mathbf{y}.
\end{align*}
Combining these results, we have that 
\begin{align*}
s^2 = s(\lambda - \mu) + (k-\mu),
\end{align*}
which we know has precisely two solutions:
\begin{align*}
\frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2}.
\end{align*}
So there are at most three eigenvalues:
\begin{align*}
k, \frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2}.
\end{align*}
\end{proof}


\begin{lemma}
Suppose that $G$ is a strongly regular graph, with parameters $(n,k,\lambda, \mu)$, and that we're not in any of our degenerate cases (i.e. $\mu > 0, k < n-1, \lambda < k-1.$) Then the three eigenvalues of $A_G$ have 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*}
In particular, these quantities are \textbf{integers}.
\end{lemma}
\begin{proof}
First, notice that the eigenvalue $k$ has multiplicity 1: this is a consequence of a result we proved last week (when we showed that a graph was regular iff $\Delta(G)$ was an eigenvalue).  So the only other possible eigenvalues are
\begin{align*}
\frac{(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}{2} = r,s.
\end{align*}
Let $a$ be the multiplicity of the $r$ eigenvalue, and $b$ the multiplicity of the $s$ eigenvalue.  Then, we know that (because the sum of all of the eigenvalues is 0, because the trace of our matrix is 0)
\begin{align*}
k + ra + sb = 0;
\end{align*}
as well, because there are $n$ eigenvalues counting multiplicity, we know that
\begin{align*}
1 + a + b = 0.
\end{align*}
Combining, this forces
\begin{align*}
a = -\frac{k+s(n-1)}{r-s}, b = \frac{k+r(n-1)}{r-s};
\end{align*}
i.e.
\begin{align*}
a,b =  \frac{1}{2}\left(n-1 \pm \frac{(n-1)(\mu-\lambda) - 2k}{\sqrt{(\mu-\lambda)^2 + 4(k-\mu)}}   \right).
\end{align*}
\end{proof}
\begin{lemma}
For a strongly regular graph as above, we have
\begin{align*}
k(k-\lambda - 1) = \mu(n-k-1).
\end{align*}
\end{lemma}
\begin{proof}
HW!
\end{proof}

\begin{lemma}
If $r,s$ as above are not integers, then $a=b$, and our strongly regular graph is specifically of the form $(4t+1, 2t, t-1, t)$ if it's not degenerate.
\end{lemma}
\begin{proof}
If $a \neq b$, then the numerator in the fraction part of each multiplicity must be nonzero (to make them distinct); this forces the denominator part of each of these fractions to be rational, which in turn forces $r,s$ to be rational.  But if $r,s$ are a pair of rational roots to a monic polynomial with integer coefficients, they must be in fact integers!

So, the only other case left to us is when $a=b$.  In this case, we have 
\begin{align*}
0 &= \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{(n-1)(\mu-\lambda) - 2k}{\sqrt{(\mu-\lambda)^2 + 4(k-\mu)}}   \right)\\
\Rightarrow 0 &= \frac{(n-1)(\mu-\lambda) - 2k}{\sqrt{(\mu-\lambda)^2 + 4(k-\mu)}}\\
\Rightarrow 0 &= (n-1)(\mu-\lambda) - 2k\\
\Rightarrow 2k &= (n-1)(\mu-\lambda).\\
\end{align*}
What does this force?  Well: if $\mu - \lambda \geq 2$, we'd have to have $k \geq n-1$, which we disallowed as a degenerate case.  So we must have $\mu- \lambda = 1,$ (as otherwise forces $k = 0$, which is also a degenerate case.)  This forces $n = 2k+1$, and thus that (by the third lemma) we have
\begin{align*}
k(k-\lambda - 1) &= \mu(n-k-1) = \mu k \\
\Rightarrow k^2 - k\lambda - k &= \mu k \\
\Rightarrow k^2 - 2k\lambda - k &= (\mu - \lambda) k \\
\Rightarrow k^2 - 2k\lambda - k &= k \\
\Rightarrow k^2 - 2k\lambda - 2k &= 0\\
\Rightarrow k^2 - 2k(\lambda - 1) &= 0\\
\Rightarrow \lambda &= (k+1)/2,\\
\end{align*}
and thus that our graph is of the form $(4t+1, 2t, t-1, t)$.
\end{proof}


\end{document} 