\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{multicol}
\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}


\project{2: Strongly Regular Graphs}{Weeks 1-10}

\noindent A \textbf{graph} $G$ with $n$ vertices and $m$ edges consists of the following two objects:
\begin{enumerate}
\item a set $V = \{v_1, \ldots v_n\}$, the members of which we call $G$'s \textbf{vertices}, and
\item a set $E = \{e_1, \ldots e_m\}$, the members of which we call $G$'s \textbf{edges}, where each edge $e_i$ is an unordered pair of distinct elements in $V$, and no unordered pair is repeated.  For a given edge $e = \{v, w\}$, we will often refer to the two vertices $v,w$ contained by $e$ as its endpoints.
\end{enumerate}

\begin{exmp}
The following pair $(V,E)$ defines a graph $G$ on five vertices and five edges:
\begin{itemize}
\item $V = \{1,2,3,4,5\}$,
\item $E = \{\{1,2\}, \{2,3\}, \{3,4\}, \{4,5\}, \{5,1\} \}$.
\end{itemize}
Something mathematicians like to do to quickly represent graphs is \textbf{draw} them, which we can do by taking each vertex and assigining it a point in the plane, and taking each edge and drawing a curve between the two vertices represented by that edge.  For example, one way to draw our graph $G$ is the following:
\begin{center}
\includegraphics[width=1in]{mc2011_introgt_pentagon1.pdf}
\end{center}
However, this is not the only way to draw our graph!  Another equally valid drawing is presented here:
\begin{center}
\includegraphics[width=1in]{mc2011_introgt_pentagon2.pdf}
\end{center}


In general, all we care about for our graphs is their vertices and their edges; we don't usually care about how they are drawn, so long as they consist of the same vertices connected via the same edges.  Also, we usually will not care about how we ``label'' the vertices of a graph: i.e.\ we will usually skip the labelings on our graphs, and just draw them as vertices connected by edges.
\end{exmp}

Graphs are one of the most versatile mathematical objects; it is hard to think of a concept of area of mathematics that cannot be described using the language of graph theory.  When describing graphs, some additional terminology is handy: we list a few terms here.
\begin{itemize}
\item Two vertices are called \textbf{adjacent} if there is an edge connecting them. For example, vertices $1$ and $2$ are adjacent in the graph above, while vertices 1 and 3 are nonadjacent.
\item Given a vertex $v$ in a graph $G = (V, E)$, we define the \textbf{neighbors} of $v$, denoted $N(v)$, as the collection of all vertices that are adjacent to $v$.  For example, $N(1) = \{2,5\}$ in the graph above.
\item In a graph $G = (V, E)$, we say that a vertex $v \in V$ has \textbf{degree} $k$ if $N(v)$ contains $k$ elements.  For example, the vertex $1$ in the example above has degree 2.
\item A graph is called \textbf{$k$-regular} if every vertex has degree $k$.  For example, the graph above is 2-regular, and the graph below (called the Petersen graph) is 3-regular:
\begin{center}
\includegraphics[width=1in]{Petersen1_tiny.pdf}
\end{center}
\item A graph $G$ is called $(n, k, \lambda, \mu)$-\textbf{strongly regular} if it has the following four properties:
\begin{itemize}
\item $G$ is a graph on $n$ vertices.
\item $G$ is $k$-regular.
\item Take any two adjacent vertices $u,v \in G$.  The number of vertices $y$ that are adjacent to both $u$ and $v$, in other words the number of elements in $N(u) \cap N(v)$, is $\lambda.$
\item Take any two nonadjacent vertices $w,x \in G$.  The number of vertices $z$ that are adjacent to both $w$ and $x$, in other words the number of elements in  $N(w) \cap N(x)$, is $\mu$.
\end{itemize}
For example, the first graph we looked at was a $(5,2,0,1)$-strongly regular graph, as it contains 5 vertices, is 2-regular, any two adjacent vertices have no neighbors in common, and any two nonadjacent vertices have exactly one neighbor in common.  As well, the Petersen graph above is a $(10,3,0,1)$-strongly regular graph, as it contains 10 vertices, is 3-regular, any two adjacent vertices have no neighbor in common, and any two nonadjacent vertices have one neighbor in common.
\end{itemize}


In general, it is an open problem to determine whether strongly regular graphs (SRGs) exist for most sets of parameters $(n, k, \lambda, \mu)$; if you go to
\begin{center}
\href{http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html}{http://www.win.tue.nl/$\sim$aeb/graphs/srg/srgtab.html}
\end{center}
you can find a list of all known results on SRGs so far!  There are numbers of sets of parameters, as small as $(65,32,15,16)$ for which we do not know whether such graphs exist.  Students working on this project will study what we know about SRGs, and attempt to discover new examples of such graphs!



\end{document}