%\section{An introduction to distance-regular graphs}\label{sec2:basics}

In this section we intend to introduce some basics about
distance-regular graphs to the reader that is unfamiliar with
the topic. This includes some basic proofs and questions to
give some (first) flavors of the area of distance-regular
graphs.

\subsection{Definition}\label{sec2:definition}

Let $\G$ denote a simple, undirected, connected graph, with vertex set $V=V_{\G}$ of size $v=|V|$. Whenever there is an
edge between two vertices $x$ and $y$, we say that $x$ is {\em adjacent} to $y$, or that $x$ and $y$ are {\em
neighbors}, use the notation $x \sim y$, and denote the edge by $xy$. The {\em distance} in the graph between two
vertices $x$ and $y$ is denoted by $d(x,y)=d_{\G}(x,y)$, and is given by the length of the shortest path between
$x$ and $y$. The {\em diameter} of the graph is $D=D_{\G}=\max_{x,y\in V} d(x,y)$. The set of vertices at distance
$i$ from a given vertex $z\in V$ is denoted by $\G_i(z)$, for $i=0,1,\dots,D$. The {\em distance-$i$ graph} $\G_i$
is the graph with vertex set $V$, where two vertices $x$ and $y$ are adjacent if and only if $d_{\G}(x,y)=i$. A
graph is called {\em bipartite} if the vertex set can be partitioned into two parts such that every edge has one end
(vertex) in each part.

A connected graph $\G$ with diameter $D$ is called {\em
distance-regular} if there are constants $c_i, a_i, b_i$ ---
the so-called {\em intersection numbers} --- such that for all
$i=0,1,\dots, D$, and all vertices $x$ and $y$ at distance
$i=d(x,y)$, among the neighbors of $y$, there are $c_i$ at
distance $i-1$ from $x$, $a_i$ at distance $i$, and $b_i$ at
distance $i+1$. It follows that $\G$ is a regular graph with
valency $k=b_0$, and that $c_i+a_i+b_i=k$ for all $i=0,1,\dots,
D$. By these equations, the intersection numbers $a_i$ can be
expressed in terms of the others, and it is standard to put
these others in the so-called {\em intersection array}
$$\{b_0,b_1,\dots,b_{D-1};c_1,c_2,\dots,c_D\}.$$
Note that $b_D=0$ and $c_0=0$ are not included in this array, whereas $c_1=1$
is included (note that all numbers in the intersection array are positive
integers). Also the number of vertices can be obtained from the intersection
array. In fact, every vertex has a constant number of vertices $k_i$ at given
distance $i$, that is, $k_i=|\G_i(z)|$ for all $z \in V$. Indeed, this follows
by induction and counting the number of edges between $\G_i(z)$ and
$\G_{i+1}(z)$ in two ways. In particular, it follows that $k_0=1$ and
$k_{i+1}=b_ik_i/c_{i+1}$ for all $i=0,1,\dots,D-1$. The number of vertices now
follows as $v=k_0+k_1+ \cdots + k_D$. In combinatorial arguments such as the
above, it helps to draw pictures; in particular, of the so-called {\em
distance-distribution diagram}, as depicted in Figure \ref{pic:dddiagram}.
\begin{figure}[h!]
\centering
\includegraphics[viewport=0 20 1280 170,width=120mm]{distribution-diagram.pdf}
\caption{Distance-distribution diagram} \label{pic:dddiagram}
\end{figure}

\subsection{A few examples}

\subsubsection{The complete graph} The complete graphs $K_v$
(i.e., the graphs where all vertices are adjacent to each other)
are the distance-regular graphs with diameter $1$, and have
intersection array $\{v-1;1\}$ if $v>1$.

\subsubsection{The polygons}\label{sec:polygons} The polygons (cycles) $C_v$ are the
distance-regular graphs with valency $2$, and have intersection
array $\{2,1,\dots,1;1,1,\dots,1\}$ if $v$ is odd, and
$\{2,1,\dots,1;1,\dots,1,2\}$ if $v$ is even.

\subsubsection{The Petersen graph and other Odd
graphs}\label{sec:oddgraphs} The well-known Petersen graph is a
distance-regular graph with diameter $2$, and has intersection
array $\{3,2;1,1\}$. The distance-regular graphs with diameter $2$
are very special, and form a subject of their own. They are exactly
the connected strongly regular graphs (for more on such graphs, see
\cite[Ch.~9]{BrHa}).

The Petersen graph is the same as the Odd graph $O_3$. For an integer $k \ge
2$, the vertices of the Odd graph $O_k$ are the $(k-1)$-subsets of a set of
size $2k-1$, and two vertices are adjacent if the corresponding subsets are
disjoint. The Odd graph $O_k$ is distance-regular with diameter $k-1$. For odd
$k=2l-1$, its intersection array is
$\{k,k-1,k-1,\dots,l+1,l+1,l;1,1,2,2,\dots,l-1,l-1\}$. For even $k=2l$, the
intersection array is $\{k,k-1,k-1,\dots,l+1,l+1;1,1,2,2,\dots,l-1,l-1,l\}$.
Consequently, the numbers $a_i$ are zero for all $i=0,1,\ldots,D-1$, but
$a_D=l>0$.

\subsection{Which graphs are determined by their intersection
array?}\label{sec:determinedbyarray}

All graphs in the above examples have the property that they are the only ones
that are distance-regular with the given intersection array. In other words,
given the particular intersection array, it is possible to reconstruct the
graph uniquely (up to isomorphism). A typical combinatorial argument can be
used to show this for the Petersen graph.

\begin{prop} The Petersen graph is determined as distance-regular
graph by its intersection array.
\end{prop}
%
\begin{proof}
Consider a distance-regular graph with intersection array $\{3,2;1,1\}$.
Take a vertex $z$; it has $b_0=3$ neighbors, each of which has $b_1=2$
neighbors at distance 2 from $z$ (and hence there are no triangles in the
graph; $a_1=0$). Each of the vertices at distance 2 from $z$ has precisely
$c_2=1$ common neighbors with $z$ (hence there are no 4-cycles in the graph
either). This already determines the $10=1+3+6$ vertices and all edges except
those having both ends in $\G_2(z)$. The graph induced on $\G_2(z)$ is regular
with valency $a_2=2$, and because the graph has no triangles, this must be a
$6$-cycle. Now there is (up to isomorphism) only one way to make this $6$-cycle
if one takes into account that the entire graph has no triangles and
$4$-cycles; we obtain the Petersen graph as the only graph with intersection
array $\{3,2;1,1\}$; see Figure \ref{pic:petersen}.
\begin{figure}[ht!]
\centering
\includegraphics[angle=90,width=30mm]{petersen3.pdf}
\caption{The Petersen graph} \label{pic:petersen}
\end{figure}
\end{proof}

\noindent This is clearly a very interesting property; however
it does not hold for all intersection arrays. The smallest
intersection array (smallest in terms of the number of
vertices) that corresponds to more than one graph is
$\{6,3;1,2\}$; it corresponds to the Hamming graph $H(2,4)$
(also known as the lattice graph $L_2(4)$) and the Shrikhande
graph.

One of the problems in the field of distance-regular graphs is
therefore to determine which graphs are determined by their
intersection array, and more generally, to determine all graphs
that have the same intersection array as a given graph. While
for many graphs this problem is still open, for the Odd graphs
the problem was settled already long ago by Moon \cite{Moon}. Her result
was later generalized by Koolen \cite{Ko93} as follows.

\begin{prop}\label{prop:odd} Let $\G$ be a non-bipartite distance-regular graph with diameter
$D \ge 4$, and intersection numbers $a_1=a_2=a_3=0$,
$c_2=1$, and $c_3=c_4=2$. Then $\G$ is an Odd graph.
\end{prop}

\noindent This result shows that we do not always need all
intersection numbers to determine a graph. This is very typical in
the characterization results that we know. We will see more examples
of this later on, for example in the characterizations in Section
\ref{sec:Metsch}. Note that the condition that the graph is
non-bipartite is also a condition on the intersection numbers; it is
not hard to see that a distance-regular graph is bipartite (i.e.,
has no odd cycles) if and only if $a_i=0$ for all $i=0,1,\dots,D$.
To obtain their results, both Moon and Koolen used the
correspondence to a certain Johnson graph; and Moon characterized
this Johnson graph by just a few intersection numbers. Hiraki
\cite{Hi07} also strengthened the result by Moon; he showed ---
among others --- that $a_1=a_2$, $a_4=0$, $c_2=1$, and $c_3=c_4=2$
suffices to determine the Odd graphs among the non-bipartite
distance-regular graphs with diameter $D \ge 5$. These results also
`eliminate' intersection arrays that match the intersection arrays
of the Odd graphs partially.

This brings us to the following question: which intersection
arrays should we look at? Do we need a distance-regular graph
first, before we consider its intersection array? Perhaps
there are beautiful distance-regular graphs that we do not know
of yet. How can we find these? One way is to first try to
classify possible intersection arrays.

In order to find putative intersection arrays of distance-regular
graphs, we should in principle find as many conditions on such
arrays as possible. In this introduction, we will however only
mention some elementary standard conditions. There are many other
--- more technical --- conditions known (some of which we will see
in later sections) that eliminate certain intersection arrays, but
these are beyond the scope of this introduction. We begin with some
combinatorial conditions, and then bring linear algebra into the
game to obtain algebraic conditions.




\subsection{Some combinatorial conditions for the intersection array}

The first trivial conditions that should hold for the
intersection array
$\{b_0,b_1,\dots,b_{D-1};\break c_1,c_2,\dots,c_D\}$ of a
distance-regular graph is that the intersection numbers listed
are positive integers. Moreover, the intersection number
$a_i=b_0-b_i-c_i$ is a nonnegative integer. But we also have
some divisibility conditions as follows.

\begin{prop}
\label{order in b_i, c_i}
With notation as above, the following conditions hold:
\begin{enumerate}[{\em (i)}]
\item $k_{i+1}=\frac{b_0b_1 \cdots b_{i}}{c_1c_2 \cdots c_{i+1}}$
is an integer for $i=0,1,\dots,D-1$,
\item $vk_i$ is even for $i=1,2,\dots,D$,
\item $k_ia_i$ is even for $i=1,2,\dots,D$,
\item $vka_1$ is divisible by $6$.
\end{enumerate}
\end{prop}

\begin{proof}
(i) Earlier on, in Section \ref{sec2:definition},  we
obtained the recurrence $k_{i+1}=b_ik_i/c_{i+1}$ for all
$i=0,1,\dots,D-1$, and this implies that
$$k_{i+1}=\frac{b_0b_1 \cdots b_{i}}{c_1c_2 \cdots c_{i+1}}$$
for $i=0,1,\dots,D-1$. These numbers are clearly positive integers.

(ii) By doubly counting all pairs $(z,e)$, where $z$ is an end
vertex of edge $e$ in $\G_i$, it follows that the number of
edges in $\G_i$ equals $vk_i/2$, which should be an integer.

(iii) Similarly, there are $k_ia_i/2$ edges of $\G$ within
$\G_i(z)$ for a fixed vertex $z$, and this should be an
integer.

(iv) Finally, the number of triangles in $\G$ equals $vka_1/6$.
\end{proof}

\noindent There is also a nice order in the intersection
numbers, and consequently the $k_i$ are unimodal, as we shall see next.

\begin{prop}\label{prop:unimodal} With notation as above, the following conditions hold:
\begin{enumerate}[{\em (i)}]
\item $1=c_1 \le c_2 \le \cdots \le c_D$,
\item $k=b_0 \ge b_1 \ge \cdots \ge b_{D-1}$,
\item If $i+j \le D$, then $c_i \le b_j$,
\item There is an $i$ such that $k_0\le k_1\le\dots\le k_i$ and $k_{i+1}\ge
k_{i+2}\ge\dots\ge k_D$.
\end{enumerate}
\end{prop}

\begin{proof}
(i) and (ii) Let $i=1,2,\dots,D$. Consider two vertices $x$ and $y$ at
distance $i$, and a vertex $z$ that is adjacent to $x$ and at distance $i-1$
from $y$. Now the $c_{i-1}$ neighbors of $y$ that are at distance $i-2$ from
$z$ are all at distance $i-1$ from $x$. Therefore $c_i \ge c_{i-1}$. Similarly,
the $b_i$ neighbors of $y$ that are at distance $i+1$ from $x$ are at distance
$i$ from $z$, hence $b_{i-1} \ge b_i$.

(iii) Consider two vertices $x$ and $y$ at distance $i+j$, and
a vertex $z$ at distance $i$ from $x$ and $j$ from $y$. Then
the $c_i$ neighbors of $z$ that are at distance $i-1$ from $x$
are at distance $j+1$ from $y$. Hence $c_i \le b_j$.

(iv) It follows from (i), (ii), and Proposition \ref{order in b_i, c_i} that
$k_i^2\ge k_{i-1}k_{i+1}$ for $i=1,2,\dots,D-1$. This implies that the $k_i$
are unimodal: there is an $i$ such that $k_0\le k_1\le\dots\le k_i$ and
$k_{i+1}\ge k_{i+2}\ge\dots\ge k_D$.
\end{proof}


\noindent Even though these and other combinatorial conditions
are important, they are insufficient to obtain most of the
advanced results. We need linear algebra.

\subsection{The spectrum of eigenvalues and multiplicities}\label{sec2:evmult}

The adjacency matrix $A$ of a (simple, undirected) graph $\G$
is the $v \times v$ symmetric matrix with entries $0$ and $1$
whose rows and columns are indexed by the vertices of $\G$, and
where $A_{xy}=1$ if and only if $x \sim y$. Because $A$ is real
and symmetric, its eigenvalues are real numbers. The spectrum
of eigenvalues of a graph (that is, of its adjacency matrix)
contains quite some (but in general not all) information about
the graph. Spectra of graphs is a very fruitful subject on its
own, and it has many more applications to distance-regular
graphs than the ones that we shall see here. Good references
for spectra of graphs are the classic monograph by Cvetkovi\'c,
Doob, and Sachs \cite{CDS} and the more recent one by
Brouwer and Haemers \cite{BrHa}.

The {\em adjacency algebra} of $\G$, denoted by
$\AL=\AL(\G)$, is the matrix subalgebra of $M_{v \times
v}(\R)$ of polynomials in $A$, that is, $\AL = \R[A]$. This
algebra plays an important role for distance-regular graphs, as
we shall see later on. We note that the powers of $A$ count
walks in the graph, that is, $(A^{\ell})_{xy}$ equals the
number of walks of length $\ell$ in the graph from $x$ to $y$.
Using this, we can relate the number of distinct eigenvalues to
the diameter of the graph. To do this, assume that $\G$ is
an arbitrary graph with distinct eigenvalues $\theta_0,
\theta_1, \ldots, \theta_d$. Because the minimal polynomial of
$A$ now has degree $d+1$, it is clear that $\{I, A, A^2,
\ldots, A^d\}$ is a basis of $\AL$, and hence that $\dim \AL
= d+1$.

\begin{prop} \label{D<=d}
Let $\G$ be a connected graph with diameter $D$ and
distinct eigenvalues $\theta_0,\theta_1, \dots , \theta_d$.
Then $D \le d$.
\end{prop}
\begin{proof}
Consider two vertices $x$ and $y$ at distance $i \le D$.
Then $(A^{\ell})_{xy} =0$ if $\ell < i$ and $(A^i)_{xy} \neq
0$. This implies that the set of matrices $\{I= A^0, A, \ldots,
A^D\}$ is linearly independent in $\AL$, and hence that $D+1
\le \dim \AL = d+1$.
\end{proof}

\noindent For $i = 0,1, \ldots, d$, we define the matrix $E_i =
\prod_{j=0, j \neq i}^d \frac{A - \theta_j I}{\theta_i -
\theta_j}$. The matrix $E_i$ is the orthogonal projection onto
the eigenspace $V_i$ of $A$ corresponding to $\theta_i$. The set
$\{ E_0, E_1, \ldots, E_d\}$ forms another basis
of $\AL$. Indeed, let ${\bf v}$ be an eigenvector of $A$ with
respect to $\theta_j$. Then $E_i {\bf v} = \delta_{ij} {\bf
v}$. This implies that $\{ E_0, E_1, \ldots, E_d\}$ forms a
linearly independent set of matrices in $\AL$, and hence that
it is a basis of $\AL$. We shall see more of this basis in the
next section.

The adjacency matrix $A_i$ of $\G_i$ is called the {\em
distance-$i$ matrix} of $\G$, for $i=0,1,\dots,D$. Let us now
consider the case that $\G$ is distance-regular. In this case,
we shall see that also $\{I=A_0, A=A_1, A_2, \ldots, A_D\}$ is
a basis of $\AL$, and hence that $D=d$. Translating the
combinatorial definition of distance-regularity into matrix
language, we obtain the equation
\begin{equation}\label{a_i}
A A_i =b_{i-1} A_{i-1} + a_i A_i + c_{i+1} A_{i+1}
\end{equation} for
$i=0,1,\dots,D$. Note that for $i=0$ and $i=D$, the indices in this equation
attain undefined values. Here --- and in similar equations that will follow
later --- we will have the sensible convention that the corresponding summands
are zero (so $b_{-1}A_{-1}=c_{D+1}A_{D+1}=0$). From this recurrence (note that
the coefficients $c_{i+1}$ are nonzero for $i=0,1,\ldots,D-1$), it follows that
there exist polynomials $v_i$ of degree $i$ such that
\begin{equation}\label{distancepolynomials}
A_i = v_i(A)
\end{equation} for $i
=0,1,\ldots, D$. These polynomials also satisfy a three-term recurrence relation
 like (\ref{a_i}), and hence they form a system of orthogonal polynomials.
 Because $\sum_{i=0}^D A_i = J$ (the all-ones matrix) and $AJ=kJ$
(because $\G$ is regular with valency $k$), it follows that
$(\sum_{i=0}^D v_i(A))(A- kI) = 0$. This shows that $\dim \AL
\leq D+1$. We may conclude the following.
\begin{prop}\label{dimleqD+1}
Let $\G$ be a distance-regular graph with diameter $D$.
Then $\dim \AL = D+1$. In particular, $\G$ has exactly
$D+1$ distinct eigenvalues.
\end{prop}

\noindent Remarkably, these $D+1$ distinct eigenvalues of the distance-regular
graph $\G$ can be computed from the intersection numbers only. To see this,
consider the tridiagonal $(D +1) \times (D+1)$ matrix {\em intersection matrix}
\begin{equation}\label{matrixl}L =\left[
\begin{array}{cccccc}
 0 & b_0 & & & & \\
 c_1 & a_1 & b_1 & & 0 &  \\
 & c_2 & \cdot & \cdot & & \\
 & & \cdot & \cdot & \cdot & \\
 & 0 &  & \cdot & \cdot & b_{D-1} \\
 &&&& c_{D} & a_D
\end{array} \right].
\end{equation}
%
This matrix is diagonalizable because it is similar to a
symmetric matrix. In fact, if $\Delta$ is the diagonal matrix with
diagonal entries $\Delta_{ii}=k_i$ for $i=0,1,\dots,D$, then by
using that $k_{i+1}/k_i=b_i/c_{i+1}$, it can be verified that
$\Delta^{1/2}L\Delta^{-1/2}$ is indeed a symmetric tridiagonal matrix.

Let $\theta$ be an eigenvalue of $L$, and let ${\mathbf u} = (u_0, u_1, \ldots, u_D)^{\top}$ be a corresponding (right) eigenvector,
%Let $\theta$ be an eigenvalue of $L$ with corresponding (right) eigenvector
%${\mathbf u} = \break (u_0, u_1, \ldots, u_D)^{\top}$,
that is, $L{\mathbf u} = \theta {\mathbf u}$, with $u_0 =1$.
Then $u_1 = \theta/k$ and
\begin{equation}\label{standard_sequence}
	c_i u_{i-1} + a_i u_i + b_i u_{i+1} = \theta u_i
\end{equation}
for $i = 1,2, \ldots, D$.
The sequence $(u_i)_{i=0}^D$ is called the {\em standard}
(or \emph{cosine})
\emph{sequence} of $\G$ with respect to $\theta$.

A consequence of the above symmetrization of $L$ is that the
row vector ${\bf v}={\bf u}^{\top}\Delta$ is a left eigenvector of
$L$. Thus, the components of ${\bf v}$ also satisfy a
recurrence involving the intersection numbers. It can be
verified that these components can be obtained from the
polynomials $v_i$ in (\ref{distancepolynomials}), that
is, ${\bf v}= (v_0(\theta),v_1(\theta),\dots,v_D(\theta))$.
This gives an alternative way to obtain the standard sequence.

\begin{prop}\label{distincteig}
Let $\G$ be a distance-regular graph with diameter $D$.
Then the $D+1$ distinct eigenvalues of $\G$ are precisely the
eigenvalues of $L$.
\end{prop}
\begin{proof}
Let ${\bf u}$ be as above, i.e., an eigenvector of $L$ with
respect to eigenvalue $\theta$, and fix a vertex $x$ of
$\G$. Define the vector ${\bf w}$ by $w_y = u_{d(x,y)}$ for
$y \in V$.
It is not hard (but a bit technical) to check that $A {\bf w} =
\theta {\bf w}$. Indeed, if ${\bf a_i}$ denotes column $x$ of
$A_i$, then ${\bf w}=\sum_{i=0}^D u_i {\bf a_i}$. By
(\ref{a_i}) and the above equations for the standard sequence,
we obtain that
\begin{align*}
A {\bf w}&=\sum_{i=0}^D u_i (b_{i-1}{\bf
a_{i-1}}+a_{i}{\bf a_{i}}+c_{i+1}{\bf a_{i+1}})\\
&= \sum_{i=0}^D
(c_{i}u_{i-1}+a_{i}u_{i}+b_{i}u_{i+1}){\bf a_{i}}=\sum_{i=0}^D
\theta u_i{\bf a_{i}}=\theta {\bf w}.
\end{align*} This shows that all
eigenvalues of $L$ are eigenvalues of $\G$.

What remains is to show that $L$ has $D+1$ distinct
eigenvalues. We already observed that $L$ is diagonalizable, or
in other words, that it has $D+1$ eigenvalues. Because the
intersection numbers $c_1,c_2,\dots,c_D$ are all nonzero, it
follows that the rank of $L - \theta I$ is at least $D$ for all
$\theta \in \R$. This shows that all eigenvalues of $L$ are
distinct, which finishes the proof.
\end{proof}

\noindent Finally, also the multiplicities of the eigenvalues
of $\G$ follow from the intersection numbers, via the standard
sequence. This is known as {\em Biggs' formula}.

\begin{theorem}\label{Biggsformula}{\em (Biggs' formula)}
Let $\G$ be a distance-regular graph with diameter $D$ and
$v$ vertices. Let $\theta$ be an eigenvalue of $\G$ and
$(u_i)_{i=0}^D$ be the standard sequence with respect to
$\theta$. Then the multiplicity $m(\theta)$ of $\theta$ as an
eigenvalue of $\G$ satisfies
$$m(\theta) = \frac{v}{\sum_{i=0}^D k_iu_i^2}.$$
\end{theorem}
\begin{proof}
Let $E$ be the matrix corresponding to the orthogonal
projection onto the eigenspace of $\G$ with respect to $\theta$
(i.e., it is one of the matrices $E_i$ defined before). The
idempotent matrix $E$ only has eigenvalues $0$ and $1$, and the
multiplicity $m(\theta)$ of $\theta$ as an eigenvalue of $\G$
is the same as the multiplicity of eigenvalue $1$ of $E$, which
implies that $m(\theta)=\tr E$. Because $E \in {\AL}$ and
$\{A_0,A_1,\dots,A_D\}$ is a basis of $\AL$, there are real
numbers $\nu_i, i=0,1, \ldots, D$ such that $E = \sum_{i=0}^D
\nu_i A_i$.  Note that $A E = \theta E$, which implies that
$c_i \nu_{i-1} + a_i \nu_i + b_i \nu_{i+1} = \theta \nu_i$ for $
i=0,1, \ldots, D$. From this it follows that $\nu_i = \nu_0 u_i$
for $i=0, 1,
\ldots, D$. By considering the diagonal of the equation $E^2 =
E$, we find that $\sum_{i=0}^D k_i \nu_i^2 = \nu_0$, which implies
that $\sum_{i=0}^D k_i u_i^2 = 1/\nu_0$. Now it follows that
\begin{equation*}
m(\theta) = \tr E = \sum_{x \in V} E_{xx} = v \nu_0 =
\frac{v}{\sum_{i=0}^D k_i u_i^2}.\qedhere
\end{equation*}
\end{proof}

\noindent Thus, it is relatively easy to compute the spectrum of a
distance-regular graph from its intersection array. Remarkably,
the fact that multiplicities of eigenvalues are positive integers is a
condition that many intersection arrays (that satisfy all earlier conditions)
do not satisfy. Note also that algebraically conjugate eigenvalues must have
the same multiplicities. The latter plays an important role in the proof of the
Bannai-Ito conjecture, see Section \ref{sec:proofBIconjecture}.

Related to the vectors {\bf w} in the proof of Proposition
\ref{distincteig} and the standard sequence is the representation
associated to an eigenvalue $\theta$. Let $U$ be a matrix having as
columns an orthonormal basis of the eigenspace of eigenvalue
$\theta$. Then $UU^{\top}$ is the corresponding idempotent matrix
$E$. For every vertex $x \in V$, we denote by $\hat{x}$ the $x$-th
row of $U$. The map $x\mapsto \hat{x}$ is called a {\em
representation} (associated to $\theta$) of $\Gamma$. Given two
vertices $x,y\in V$, we have that $\langle
\hat{x},\hat{y}\rangle=E_{xy}=\nu_0u_{d(x,y)}$, which is why the
standard sequence is also called the cosine sequence. The vectors
$\hat{x}$ ($x\in V)$ all have the same length, $\sqrt{\nu_0}$,
hence we call the representation spherical.
%Because $AU=\theta U$,
%we obtain that \begin{equation*}\label{representation} \theta
%\hat{x}=\sum_{y\sim x} \hat{y}.
%\end{equation*}


\subsection{Association schemes}

In the previous section we described three different bases for the adjacency algebra $\AL$ of a distance-regular graph:
$\{I, A, A^2,\ldots, A^D\}$, $\{ E_0, E_1, \ldots, E_D\}$, and $\{A_0,A_1,\dots,A_D\}$. The last one was obtained by
explicit use of the property of distance-regularity. A consequence of this is that there are real numbers $p^h_{ij}$
$(h,i,j=0,1,\dots,D)$ such that
\begin{equation}\label{phij}
A_iA_j=\sum_{h=0}^D p^h_{ij} A_h.
\end{equation}
for all $i,j=0,1,\dots,D$. This expression has a combinatorial interpretation:
for each two vertices $x$ and $y$ at distance $h$, there are $p^h_{ij}$
vertices $z$ that are at distance $i$ to $x$ and distance $j$ to $y$. So the
{\em intersection numbers} $p^h_{ij}$ are nonnegative integers. Note that
$p^i_{1,i-1}=c_i, p^i_{1,i}=a_i$, and $p^i_{1,i+1}=b_i$. Also the other
intersection numbers $p^h_{ij}$ can be expressed in terms of the intersection
array. This gives further conditions on the intersection numbers.

What we have here is a special case of an {\em association scheme}: an edge
decomposition of the complete graph into spanning subgraphs $\G_i$
$(i=1,2,\dots,D)$ whose adjacency matrices $A_i$ $(i=1,2,\dots,D)$, together
with $A_0=I$ satisfy (\ref{phij}) for all $i,j=0,1,\dots,D$. Let us look a bit
closer at such an association scheme. Clearly also here $\{A_0,A_1,\dots,A_D\}$
is a basis of an algebra: the {\em Bose-Mesner algebra}. Because the matrices
in this algebra are symmetric, they also commute by (\ref{phij}) (and hence
$p^h_{ij}=p^h_{ji}$). This implies that they share a basis of eigenvectors and
there is also a basis of primitive idempotents $E_i$ $(i=0,1,\dots,D)$ for
$\AL$ (so $ME_i$ is a multiple of $E_i$ for all $M \in \AL$). These $E_i$ are
the projections onto the common eigenspaces, and are the same as before in case
of a distance-regular graph. They satisfy the equations $E_iE_j=\delta_{ij}E_i$
for all $i,j=0,1,\dots,D$ and $\sum_{i=0}^D E_i=I$.

The coefficients to change from one of the two bases to the
other are collected in the so-called {\em eigenmatix} $P$ and
{\em dual eigenmatrix} $Q$. That is,
$$A_i=\sum_{i=0}^D P_{ji}E_j \ \ \mbox{and} \ \ E_i=\frac{1}{v}\sum_{j=0}^D
Q_{ji}A_j$$ for $i=0,1,\dots,D$. Note that so far we did not order the
eigenvalues (or the $E_i$s), so there is some ambiguity in the definition of
$P$ and $Q$. This is not really a problem (as long as we keep some ordering
fixed), except that it has become habit that the first row of $P$ contains the
valencies of the graphs $\G_i$. For this reason, we order the eigenspace of
constant vectors first, so that $E_0=\frac{1}{v}J$, the \emph{trivial}
primitive idempotent of $\AL$. This is also justified by the fact that dually
we could reshuffle the $A_i$ (and $\G_i$), except the trivial $A_0$, and not
really get a `different' association scheme (for a distance-regular graph there
is of course an order given!). Note also that column $i$ of $P$ gives the
eigenvalues of the corresponding graph $\G_i$. The normalization factor
$\frac{1}{v}$ for $Q$ is there to make sure that the entries of $Q$ can be seen
as `dual eigenvalues'; for example the multiplicities $m_i=\tr E_i$ of the
eigenvalues are in the first row of $Q$. Just like in the case of
distance-regular graphs, the eigenvalues and multiplicities, and more
generally, all entries of $P$ and $Q$ can be derived from the intersection
numbers $p^h_{ij}$. In the case of distance-regular graphs, we see now in the
proof of Biggs' formula (Theorem \ref{Biggsformula}) that a column of $Q$ is a
multiple of the corresponding standard sequence.

Observe that the Bose-Mesner (or adjacency) algebra $\AL$ is
not just closed under ordinary matrix multiplication but also
under entrywise (\emph{Hadamard} or \emph{Schur}) matrix
multiplication, denoted by $\circ$. The matrices
$A_0,A_1,\dots,A_D$ are the primitive idempotents of $\AL$ with
respect to $\circ$, i.e., $A_i\circ A_j=\delta_{ij}A_i$,
$\sum_{i=0}^DA_i=J$. This implies that we may write
\begin{equation}\label{Krein}
E_i\circ E_j=\frac{1}{v}\sum_{h=0}^Dq_{ij}^hE_h
\end{equation}
for some real numbers $q_{ij}^h$ $(h,i,j=0,1,\dots,D)$, known as the
\emph{Krein parameters} (or {\em dual intersection numbers}) of $\G$.
Because $\frac{1}{v}q_{ij}^h$ is an eigenvalue of $E_i\circ E_j$, which is a
principal submatrix of the positive semidefinite matrix $E_i \otimes E_j$, we
get the following so-called {\em Krein conditions}.

\begin{prop}\label{Krein condisions}
The Krein parameters $q^h_{ij}$ of an association scheme are
nonnegative numbers.
\end{prop}

\noindent The Krein parameters can be calculated using the dual eigenmatrix as $$q^h_{ij}=\frac{1}{vm_h} \sum_{l=0}^D
k_lQ_{lh}Q_{li}Q_{lj}.$$ This follows from working out the sum of
entries of the matrix $E_i \circ E_j \circ E_h \circ J$ in
different ways. The Krein conditions thus put further constraints
on the intersection array of a distance-regular graph. Moreover, if
a Krein parameter equals zero, then this has certain consequences.
This is perhaps best illustrated in the case of the $Q$-polynomial
distance-regular graphs of Section \ref{sec:Qpol} (see also Section
\ref{sec:2Qpol}), where many Krein parameters vanish. See also
Section \ref{sec:vanishingKrein} for consequences of vanishing
Krein parameters.

From the definition of $P$ and $Q$, it is clear that $PQ=QP=vI$. A different
relation between $P$ and $Q$ can be obtained by working out the trace of
$A_iE_j$ (which equals the sum of entries of $A_i \circ E_j$) in different
ways. This gives the relation $m_jP_{ji}=k_iQ_{ij}$ for all $i,j=0,1,\dots, D$.
Together with $PQ=vI$, this gives certain {\em orthogonality relations} between
the columns (and rows) of $P$. For a distance-regular graph $\G$, this relation
also follows from the fact that the polynomials $v_i$ $(i=0,1,\dots,D)$ form a
system of orthogonal polynomials. Here $P_{ji}=v_i(P_{j1})$, which follows from
(\ref{distancepolynomials}), where we remind the reader that $P_{j1}$
$(j=0,1,\dots,D)$ are the distinct eigenvalues of $\G$.

A final condition that we would like to mention is the
{\em absolute bound}.

\begin{prop}\label{absolute bound}
The multiplicities $m_i$ of an association scheme satisfy the
following bound:
$$\sum_{q^h_{ij} \neq 0} m_h \le \left \{
\begin{array}{lll}
m_im_j& \mbox{if} & i \neq j\\
m_i(m_i+1)/2 & \mbox{if} & i = j.
\end{array}\right. $$

\end{prop}
\begin{proof}
The left hand side equals the rank of $E_i \circ E_j$, because of \eqref{Krein} and the fact that the idempotents are mutually orthogonal (and can be diagonalized simultaneously) so that their ranks are additive.
Let $\mathbf{u}_1,\mathbf{u}_2,\dots,\mathbf{u}_{m_i}$ be a basis of $E_i\R^v$, and let $\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_{m_j}$ be a basis of $E_j\R^v$.
Then the column space of $E_i \circ E_j$ is contained in the subspace spanned by the vectors $\mathbf{u}_s\circ\mathbf{v}_t$ $(s=1,2,\dots,m_i,\ t=1,2,\dots,m_j)$, thus proving the inequality for $i \neq j$.
For $i=j$, note that the latter subspace is spanned by the vectors $\mathbf{u}_s\circ\mathbf{u}_t$ with $s\leq t$.
\end{proof}

\noindent For more information on association schemes, we refer to the handbook chapter by Brouwer and Haemers \cite{bh95} and the
recent survey by Martin and Tanaka \cite{martintanaka}.

\subsection{The \texorpdfstring{$Q$-polynomial}{Q-polynomial} property}\label{sec:2Qpol}

We already noted that the ordering of graphs and idempotents in an association scheme is not really important. However,
in an association scheme that comes from a distance-regular graph, the graphs $\G_i$ are ordered naturally according to
distance in the graph. This ordering is called a $P$-polynomial ordering. This term comes from the fact that there are
polynomials $v_i$ of degree $i$ such that $A_i=v_i(A_1)$, as we have seen. The association scheme is therefore also
called {\em $P$-polynomial}. An equivalent property of this ordering is that the intersection numbers are such that
$p_{ij}^h = 0$ whenever $0 \le h < |i-j|$ or $i + j < h $, and $p_{ij}^{i+j} > 0$ (for $i+j \le D$). Because of this
property, we call a $P$-polynomial association scheme also {\em metric}. An association scheme can have at most two
$P$-polynomial orderings (that is, there can be at most two distance-regular graphs in it), except for the association
schemes coming from the polygons. For more on association schemes with two $P$-polynomial orderings, see
Section \ref{sec:2Porder}.

It turns out that many important families of distance-regular graphs, that is,
their corresponding association schemes, satisfy the following dual property.
We say that an association scheme (and in particular, a distance-regular graph)
is $Q$-\emph{polynomial} if there is an ordering $E_0,E_1,\dots,E_D$ and there
are polynomials $q_i$ of degree $i$ such that $E_i=q_i(E_1)$, where the matrix
multiplication is entrywise (so that $(E_i)_{xy}=q_i((E_1)_{xy})$ for all
vertices $x$ and $y$). We also say that the corresponding ordering and the
idempotent $E_1$ are $Q$-\emph{polynomial}. Also here there is an equivalent
property in terms of --- in this case --- the Krein parameters: an association
scheme is called {\em cometric} (with ordering $E_0,E_1,\dots,E_D$) if
$q_{ij}^h = 0$ whenever $0 \le h < |i-j|$ or $i + j < h $, and $q_{ij}^{i+j} >
0$ (for $i+j \le D$). It is well known though that to check the cometric
property, it suffices to check the above conditions for $i=1$ (just like in the
metric case). Dual to the intersection numbers of a distance-regular graph, we
here define  $c_i^{\ster}=q^i_{1,i-1}, a_i^{\ster}=q^i_{1,i}$,
$b_i^{\ster}=q^i_{1,i+1}$, and the Krein array
$\{b_0^{\ster},b_1^{\ster},\dots,b_{D-1}^{\ster};c_1^{\ster},c_2^{\ster},\dots,c_D^{\ster}\}.$

It was conjectured by Bannai and Ito \cite[p.~312]{bi} that for large enough $D$, a primitive $D$-class association
scheme is $P$-polynomial if and only if it is $Q$-polynomial.

\subsection{Delsarte cliques and geometric
graphs}\label{sec:geometricgraphs}

Delsarte \cite[p.~31]{del} obtained a linear programming bound for
cliques in strongly regular graphs. It was observed by Godsil
\cite[p.~276]{Godsilac} that the same {\em Delsarte bound} holds for
distance-regular graphs, as follows.

\begin{prop}\label{delbound} Let $\G$ be a distance-regular graph with valency $k$ and smallest
eigenvalue $\theta_{\min}$. Let $C$ be a clique in $\G$ with $c$
vertices. Then $c \leq 1 - \frac{k}{\theta_{\min}}.$
\end{prop}

\begin{proof}
Let $\chi$ be the characteristic vector of $C$, and let $E$ be the
primitive idempotent corresponding to $\theta_{\min}$. The result
follows from working out $\chi^{\top}E\chi \geq 0$.
\end{proof}

\noindent A clique $C$ in a distance-regular graph $\G$ that attains
this Delsarte bound is called a {\em Delsarte clique}. In Section
\ref{sec:crcdelsarte} we will characterize such cliques as certain completely regular codes.

A distance-regular graph $\G$ is called {\em geometric} (with
respect to $\cal C$) if it contains a collection ${\cal C}$ of
Delsarte cliques such that each edge is contained in a unique $C
\in {\cal C}$. The concept of a geometric distance-regular graph was introduced by Godsil
\cite{Godsil93} and generalizes the concept of a geometric
strongly regular graph as introduced by Bose \cite{Bose} (and
indeed the concepts are the same for diameter two).

Many classical examples of distance-regular graphs (see Section
\ref{sec:clasfamilies}), such as Johnson graphs, Grassmann graphs, and Hamming graphs are
geometric. Bipartite distance-regular graphs are trivially
geometric because in this case every edge is a Delsarte clique.

Even though the class of non-bipartite geometric distance-regular
graphs is clearly much more restricted than the class of arbitrary
distance-regular graphs, Koolen and Bang
\cite{KoBa10} showed that for fixed smallest eigenvalue there are
only finitely many non-geometric distance-regular graphs with both
valency and diameter at least three (see Theorem
\ref{thm:nongeometric}). They in fact conjectured that for fixed
smallest eigenvalue there are finitely many distance-regular graphs
with diameter at least three that are not a cycle, Hamming graph,
Johnson graph, Grassmann graph, or bilinear forms graph. This would
generalize a result by Neumaier
\cite{Neu80} on strongly regular graphs. On the other hand, because
geometric distance-regular graphs have more structure than
arbitrary distance-regular graphs, it may be possible to classify
them, or at least the $Q$-polynomial ones with
large diameter.


\subsection{Imprimitivity}

A connected graph $\G$ with diameter $D$ is called imprimitive if not all graphs $\G_i$ $(i=1,2,\dots,D)$ are
connected. Bipartite graphs are examples of imprimitive graphs ($\G_2$ is disconnected). Among the distance-regular
graphs, there are also the antipodal graphs that are imprimitive. These are the graphs for which $\G_D$ is a disjoint
union of complete graphs. In fact, Smith's theorem states that these are all possibilities (see
\cite[Thm.~4.2.1]{bcn}), except for the polygons (indeed, for example $C_9$ has $D=4$ and only $\G_3$ is disconnected
in this case).

\begin{theorem}\label{prop:imprimitive}{\em (Smith's theorem)}
An imprimitive distance-regular graph with valency $k>2$ is
bipartite and/or antipodal.
\end{theorem}

\noindent There is much more to say than this seemingly clear and simple statement. For this we refer to Alfuraidan and
Hall \cite[Thm.~2.9]{AlHaSmith}, who revisited Smith's theorem by working out more precisely all the cases that can
occur.

If $\G$ is a bipartite distance-regular graph, then
$\G_2$ is a graph with two components. The induced graphs on
these components are called the {\em halved graphs} of $\G$.

\begin{prop}\label{prop:halved}
The halved graphs of a bipartite distance-regular graph are
distance-regular.
\end{prop}

\noindent We already noted before that bipartiteness of a distance-regular
graph can be seen from its intersection numbers. Clearly
this is the case whenever $a_i=0$ for all $i=1,2,\dots,D$.

A distance-regular graph is antipodal whenever $b_i=c_{D-i}$ for all
$i=0,1,\dots,D$, except possibly $i=\lfloor D/2 \rfloor$. If $\G$ is an
antipodal distance-regular graph, then by definition, $\G_D$ is a disjoint
union of cliques. These cliques are called the {\em fibres} of $\G$. We can
also construct a smaller distance-regular graph from an antipodal
distance-regular graph: its {\em folded graph} $\overline{\G}$. Its vertices
are the fibres of $\G$, and two such fibres are adjacent whenever there is an
edge (in $\G$) between them. We also say the $\G$ is an {\em antipodal
$r$-cover} of $\overline{\G}$, where $r$ is the size of the cliques of $\G_D$.

\begin{prop}\label{prop:folded}
The folded graph of an antipodal distance-regular graph is
distance-regular.
\end{prop}

\noindent Typically, but certainly not always (see \cite{AlHaSmith}), the
halved graphs or folded graphs of an imprimitive distance-regular graph are
primitive (that is, not imprimitive). This suggests that the theory of
distance-regular graphs can be boiled down to that of primitive
distance-regular graphs. This is not the case however. There is no unique
recipe to construct imprimitive distance-regular graphs from the primitive
ones, for example. The halving and folding constructions mentioned above cannot
be reversed in a generic way, at least not in general. This is best illustrated
by the imprimitive distance-regular graphs with diameter three. All of these
have as halved or folded graph a complete graph. Sometimes, however, there is
an easy way to construct an imprimitive distance-regular graph from a primitive
one as follows. The {\em bipartite double} of a graph $\G$ with vertex set $V$
is the graph with vertex set $V \times \{0,1\}$, where two vertices $(x,i)$ and
$(y,j)$ are adjacent whenever $x$ is adjacent to $y$ in $\G$ and $i \neq j$.
The {\em extended bipartite double} of $\G$ is a variation on this: it has the
same vertex set, and besides the edges of the bipartite double, it has
additional edges between $(x,0)$ and $(x,1)$, $x \in V$.

If $\G$ is a distance-regular {\em generalized odd graph} (also
called {\em almost bipartite graph}) with diameter $D$, that is, if
it has intersection numbers $a_i=0$ for $i<D$ and $a_D>0$ (like the
Odd graphs), then the bipartite double of $\G$ is distance-regular
with diameter $2D+1$. This situation is interesting for several
reasons, one of them being that this bipartite double is not just
bipartite, but it is also an antipodal 2-cover of $\G$. The {\em
Doubled Odd graphs} (for example) are thus showing that
bipartiteness and antipodality can occur in the same graph. Note by
the way that the folded graph of this Doubled Odd graph is again
the Odd graph, but the halved graphs are not (these are isomorphic
to $\G_2$, a Johnson graph).

More generally, one can see from the intersection array of a
distance-regular graph whether the bipartite double or extended
bipartite double is distance-regular (see \cite[\S 1.11]{bcn}).


\subsection{Distance-transitive graphs}

Distance-regular graphs were `invented' by Biggs (for an early
account, see his monograph \cite{biggs}) while he was studying so-called
distance-transitive graphs. An automorphism of a graph is a bijection from the
vertex set to itself that respects adjacencies, i.e., that maps edges to edges.
A graph is called {\em distance-transitive} if it has a group of automorphisms
that acts transitively on each of the sets of pairs of vertices at distance
$i$, for $i=0,1,\dots,D$. In other words, for each $i$ and all pairs of
vertices $(x_1,y_1)$ and $(x_2,y_2)$ with $d(x_1,y_1)=i=d(x_2,y_2)$, there is
an automorphism that maps $x_1$ to $x_2$ and $y_1$ to $y_2$. This property is
easily seen to imply the property of distance-regularity. Many --- but not all
--- classical families of distance-regular graphs, for example the Hamming
graphs, are also distance-transitive. The earlier mentioned Shrikhande graph is
the smallest distance-regular graph that is not distance-transitive. In fact,
it is part of an infinite family of graphs that are distance-regular but not
distance-transitive: the so-called Doob graphs. It also indicates that
distance-transitivity of a distance-regular graph is not a property that can be
recognized from the intersection array.

A distance-transitive graph is clearly also {\em vertex-transitive},
that is, it has a group of automorphisms such that for all $x_1$ and
$x_2$, there is an automorphism that maps $x_1$ to $x_2$. Although
there is no apparent relation between vertex-transitivity and
distance-regularity, it was long believed that distance-regular
graphs with large enough diameter would have to be
vertex-transitive. This belief was proven wrong by the construction
of the twisted Grassmann graphs; see Section \ref{twistedsection}.
