%\section{The Bannai-Ito conjecture}\label{sec:BIconjecture}

In 1984, Bannai and Ito \cite[p.~237]{bi} made the following conjecture.

\begin{biconj} There are finitely many distance-regular graphs with fixed
valency at least three.
\end{biconj}

This Bannai-Ito conjecture has recently been proved by Bang, Dubickas, Koolen,
and Moulton \cite{BaDuKoMo09}. In the next section, we will give an outline of
this proof.


\subsection{Proof of the Bannai-Ito conjecture}\label{sec:proofBIconjecture}

Let $\G$ be a distance-regular graph with valency $k \geq 3$, head $h$, and
diameter $D$. The Ivanov bound (Theorem \ref{ivanovbound}) tells us that $D
\leq 4^k h$. So in order to prove the conjecture it suffices to bound $h$ as a
function of $k$.

Bannai and Ito \cite{BI89} obtained the following result, using head and tail.
Recall that the latter is defined by $t = \ell(b_1, a_1, c_1)$.

\begin{theorem}\label{banito}
Let $M \geq 1$ and $k \geq 3$. Then there are finitely many triangle-free
distance-regular graphs with valency $k$, and diameter $D \leq h + t + M$.
\end{theorem}

\noindent The key idea of the proof of this theorem is as follows. By
interlacing, $\G$ has an eigenvalue $\theta$ in the interval $(2\sqrt{k-1} \cos
\frac{3\pi}{h+1}, 2\sqrt{k-1} \cos \frac{\pi}{h+1})$. Let $\Theta$ be the set
of algebraic conjugates of $\theta$. Then
$$\prod_{\theta' \in \Theta} ((\theta')^{ 2} - k+1)$$
is a nonzero integer. Let $S = \{ x \in [-k, k] : |x^2 - k+1| > 1\}$. If $h$ is
large enough, then $\theta\not\in S$ and there is an algebraic conjugate
$\theta'$ of $\theta$ which is in $S$.  Now it can be shown, using Biggs'
formula (Theorem \ref{Biggsformula}), that the multiplicity of $\theta$ is of
order $\frac{v}{h^3}$. If $\theta' \in (-2\sqrt{k-1}, +2\sqrt{k-1})$, then the
multiplicity of $\theta'$ is $\Omega(\frac{v}{h})$, and else the multiplicity
of $\theta'$ is $O(\frac{v}{a^h})$ for some fixed real $a > 1$. This shows that
the multiplicities of $\theta$ and $\theta'$ are not the same if $h$ large,
which is a contradiction to the fact that they are algebraic conjugates.
Therefore $h$ is bounded.


Suzuki \cite{S594} generalized this result by replacing the triangle-free
condition by the condition $(a_1+1)(a_1+2) \leq k$. Bang, Koolen, and Moulton
\cite{BaKoMo07} extended the result as follows.

\begin{prop} \label{bakomo-epsilon}
Let $k \geq 3$. Then there exists a positive $\epsilon = \epsilon_k$ such that
there are finitely many distance-regular graphs $\G$ with valency $k$, and
diameter $D \leq h + t + \epsilon h$.
\end{prop}


\noindent The proof of Proposition \ref{bakomo-epsilon} closely follows the
proof of Theorem \ref{banito}. Instead of considering an eigenvalue in the
above mentioned interval close to $2\sqrt{k-1}$, so-called indicator intervals
are used.

Let $G = \{ (c_i, a_i, b_i) : i=1,2,\ldots, D-1\}$ and $g = |G|$; note that $g
\leq 2k-3$. We will assume that $G=\{ (\gamma_i, \alpha_i, \beta_i) :
i=1,2,\ldots, g\}$ is ordered by $\gamma_{i+1} \geq \gamma_i$ and $\beta_{i+1}
\leq \beta_i$. Let $\ell_i = \ell(\gamma_i, \alpha_i, \beta_i)$ for $i=1,2,
\ldots, g$, whence $h = \ell_1$. Let ${\cal L}_i = \alpha_i - 2\sqrt{\gamma_i
\beta_i}$ and  ${\cal R}_i = \alpha_i + 2\sqrt{\gamma_i \beta_i}$  be the {\em
left} and {\em right indicator points}, respectively. The {\em indicator
interval}  is defined as the open interval ${\cal I}_i=({\cal L}_i, {\cal
R}_i)$, $i=1,2, \ldots, g$. Using the fact that the $c_i$s are non-decreasing
and the $b_i$s are non-increasing, it is fairly easy to see that $({\cal
R}_i)_i$ is a unimodal sequence.  The fact that $b_i + a_i \geq a_1 +2$
$(i=1,2,\ldots, D-1)$ implies that ${\cal R}_g \geq {\cal R}_1$.

By removing from the (tridiagonal) intersection matrix $L$ rows and columns $0,
\ell_1, \ell_1 +\ell_2, \ldots, \ell_1 + \cdots +\ell_{g-1}, D$ and using
interlacing, it follows that at most $2g+2$ eigenvalues of $\G$ (in general
this is a relatively small number compared to the total) do not lie in any of
the indicator intervals. Instead of taking $\theta$ close to ${\cal R}_1$, one
can show that there must exist an eigenvalue $\theta$ close to a right
indicator point different from ${\cal R}_1$ if $D-h-t$ is large enough. Then it
is shown in a similar way as in Theorem \ref{banito} that there exists an
algebraic conjugate of $\theta$ whose multiplicity is different from the
multiplicity of $\theta$; again a contradiction, so $h$ is bounded.

Until now the approach was to calculate the multiplicity of a specific
eigenvalue precisely and then show that this eigenvalue has an algebraic
conjugate with a different multiplicity. For a proof of the Bannai-Ito
conjecture one needs to use another tactic, especially in the case that $D-h-t$
is large. The idea here is to find an interval ${\cal I}$ in which there are at
least $\delta h$ eigenvalues (where $\delta$ is a positive real number only
depending on $k$) and in which every two algebraic conjugate eigenvalues
$\theta$ and $\theta'$ satisfy $|\theta- \theta'| \leq f(h)$, where $f(h)
\rightarrow 0 \ \ (h \rightarrow \infty)$. The main reason that one can find
such an interval ${\cal I}$ is that the right indicator points form a unimodal
sequence. Although to calculate the multiplicities of the eigenvalues only
involves three-term recurrence relations, to show that ${\cal I}$ really exists
and that we can approximate the multiplicities in ${\cal I}$ well enough is
extremely technical and subtle. Using some elementary number theory, it then
follows that the number of algebraic conjugates of eigenvalues in ${\cal I}$
(which must all be eigenvalues of $\G$) is at least $z(h) h $, where $z(h)
\rightarrow \infty \ \ (h \rightarrow \infty)$. But as the the number of
eigenvalues besides the valency is exactly $D$, which --- by the Ivanov bound
--- is at most $4^k h$, we see that this is a contradiction if $h$ is large.
Again, this means that $h$ is bounded, which proves the Bannai-Ito conjecture.




\subsection{Extensions of the Bannai-Ito conjecture}
Bannai and Ito \cite{BI87} showed that the length $\ell(c, k-2c, c)$ is bounded by $10k 2^k$ for every $c$. This
inspired Hiraki, Suzuki, and others to obtain bounds for $\ell(1, k-2, 1)$. The current best bound is by Hiraki
\cite{Hi103}, who obtained $\ell(1, k-2, 1) \leq 14$ if $k \geq 3$ and $\ell(1, k-2, 1) \leq 1$ if $k \geq 58$.
Inspired by this, Bang, Koolen, and Moulton \cite{BKM03} showed that if $b$ and $c$ are positive integers, then there
exists a constant $k_{\min} \geq \max \{b+c, 3\}$ such that if $\G$ is a distance-regular graph with valency $k
\geq k_{\min}$ and $h \geq 2$, then $\ell(c, k-b-c,b)\leq 1$. This implies, by using the validity of the Bannai-Ito
conjecture, that if $b$ and $c$ are positive integers, then there exists a constant $\ell_{\max}$ such that for every
distance-regular graph $\G$ with valency $k \geq \max \{b+c, 3\}$ and $h \geq 2$, we have that $\ell(c,
k-b-c,b)\leq \ell_{\max}$. It is still an open problem whether this is true for $h =1$ and $c_2 = 1$. This has been
conjectured by Bang et al.~\cite{BKM03}. Park, Koolen, and Markowsky \cite{PaKoMar} extended the Bannai-Ito conjecture
as follows.

\begin{prop}
Let $M$ be a positive integer. Then there are finitely many distance-regular
graphs with valency $k \geq 3$, diameter $D \geq 6$, and $\frac{k_2}{k} \leq
M$.
\end{prop}

\noindent For diameter at most four, the analogous result is not true. For
diameter two this is clear. For diameter three, the Taylor graphs have $k_2 =k$
and the incidence graphs of the complements of projective planes of order $t$
have $k = t^2$ and $k_2 = t^2 +t$. For diameter four, the Hadamard graphs  have
$k_2 = 2(k-1)$.


Koolen and Park  \cite{KoPa11} showed that the only primitive distance-regular
graphs with $\frac{k_2}{k} \leq 1.5$, and diameter at least three are  the
Johnson graph $J(7,3)$ and the halved $7$-cube.

\subsection{The distance-regular graphs with small valency}
The edge is the only distance-regular graph with valency one, and the polygons are the distance-regular graphs with
valency two. The distance-regular graphs with valency three have been classified by Biggs, Boshier, and Shawe-Taylor
\cite{BBS} (see also \cite[Thm.~7.5.1]{bcn}): There are exactly 13 of them and all have diameter at most 8.

The intersection arrays of the distance-regular graphs with valency four have been
classified by Brouwer and Koolen \cite{BK99}. There are exactly 17 such
intersection arrays and all have diameter at most 7 (all graphs are known, except perhaps
for point-line incidence graphs of a generalized hexagon of order three).

The distance-regular graphs with valency 6 and $a_1 = 1$ (i.e., of order
$(2,2)$) have been classified by Hiraki, Nomura, and Suzuki \cite{HNS}. There are
exactly five of them and they are all geometric. This last result also
completes the classification of all  distance-regular graphs with valency at
most 7 and $a_1 \geq 1$ (see \cite{HNS} for a complete list).

The larger $t$ is, the more difficult it is to classify the distance-regular
graphs of order $(s,t)$. For example, it is much harder to classify the
distance-regular graphs with valency $5$ than the distance-regular with valency
$6$ and $a_1 = 1$. For $t=1$ we have the line graphs, and Yamazaki \cite{Y95}
developed some theory for the case $t=2$. It is not known whether for a
distance-regular graph with order $(s,t)$, one can bound the diameter in terms
of $t$ only, if $t \geq 2$ (see also Corollary \ref{cordiameter}).
