
% 14-5: "nonbipartite" --> "non-bipartite" in Section 15.2.1

%\section{Applications}\label{sec:applications}

\subsection{Combinatorial optimization}\label{sec:applcombo}

One of the formulations of Lov\'{a}sz's $\vartheta$-\emph{function bound} \cite{Lovasz1979IEEE} on the independence number and the Shannon capacity of a graph is as a semidefinite program (SDP).
McEliece, Rodemich, and Rumsey \cite{MRR1978JCISS} and Schrijver \cite{Schrijver1979IEEE} observed that if the adjacency matrix of the graph belongs to the Bose-Mesner algebra $\AL$ of an association scheme then we may solve the SDP as an ordinary linear program (LP) and the resulting bound `essentially' coincides with Delsarte's \emph{linear programming bound} \cite{del} on which his theory on codes and designs is based.
In fact, the same idea works for any SDP whenever the matrices defining the problem belong to $\AL$;
Goemans and Rendl \cite{GR1999C} applied this to the \emph{max-cut problem},
and Vallentin \cite{Va08} to finding the least \emph{distortion embeddings} of distance-regular graphs.
Delsarte's theory has been most successful when the association scheme is metric and/or cometric (but see also \cite[\S 8]{martintanaka}).
We especially recommend the survey by Delsarte and Levenshtein \cite{DL1998IEEE} on this topic.
Besides codes and designs, Delsarte's LP was also used to prove the \emph{Erd\H{o}s-Ko-Rado theorem} for several families of $Q$-polynomial distance-regular graphs; cf.~Section \ref{sec:EKR}.

In 2005, Schrijver \cite{Schrijver2005IEEE} applied a variant of an extension of the $\vartheta$-function bound based on \emph{matrix cuts} \cite{LS1991SIAM} to get a new upper bound on the sizes of binary codes.
In this case, the matrices defining the SDP belong to the Terwilliger algebra $\TT$ of the hypercube $H(D,2)$.
This method has been applied to codes in Johnson graphs
by Schrijver \cite{Schrijver2005IEEE}, to codes in (nonbinary) Hamming graphs
by Gijswijt, Schrijver, and Tanaka \cite{Gijswijt2005PhD,GST2006JCTA}, and also to the \emph{kissing number} problem in the real sphere $S^{n-1}\subset\mathbb{R}^n$ by Bachoc and Vallentin \cite{BV2008JAMS}; see \cite{BGSV2012B} for more results on this topic.

Generalizing De Klerk and Sotirov's idea of exploiting group symmetry \cite{DKSot10}, De Klerk, De Oliveira
Filho, and Pasechnik \cite{KOP2012B} recently proposed an SDP relaxation\footnote{It seems that this possible
generalization was indicated implicitly in \cite[p.~232]{DKSot10}. It should be remarked that the Bose-Mesner
algebra may also be replaced by a coherent algebra.} of the \emph{quadratic assignment problem} (without
linear term) for which one of the two defining matrices belongs to the Bose-Mesner algebra $\AL$. For
example, the polygons and the complete multipartite graphs correspond to the \emph{traveling salesman
problem} (cf.~\cite{KPS2008SIAM}) and the \emph{maximum $k$-partition problem} (cf.~\cite{Dobre}),
respectively. De Klerk and Sotirov \cite{KS2011MPA} showed that the relaxation can be strengthened further,
provided the association scheme is vertex transitive. Their computational results involve instances related
to the hypercube $H(D,2)$, and we again encounter the Terwilliger algebra $\TT$; see also
\cite{Sotirov2012B}. Van Dam and Sotirov \cite{DS12, DS13} exploited symmetry to obtain bounds for the
bandwidth of among others Hamming and Johnson graphs, and for the graph partition problem for several other
distance-regular graphs.

We finally mention Lee \cite{Leespectral, Leedimension}, who used the symmetry
of the Johnson graph (and other association schemes) to derive results on the
dimension of certain polytopes that are relevant to cutting plane algorithms
for combinatorial optimization problems such as the bisection problem, the
traveling salesman problem, and the perfect matching problem.



\subsection{Random walks, diffusion models, and quantum walks}\label{sec:randomwalks}

Given a graph $\G$, a {\it random walk} on $\G$ is the walk of a particle that
travels at random upon the vertices of a graph. At each stage the particle
moves to a vertex that is adjacent to its current location, and the
probabilities that it moves to each of its neighbors are equal. The particle
has no memory, so it is as likely to return to a vertex it has just been to as
it is to move to a new vertex.

\subsubsection{Diffusion models and stock portfolios}\label{sec:diffusionmodels}

Random walks on certain distance-regular graphs correspond to important models
for the diffusion of particles. The Ehrenfests' urn model that was proposed to
explain the second law of thermodynamics corresponds to random walks on the
hypercube $H(D,2)$. The classical Bernoulli-Laplace diffusion model corresponds
to random walks on the Johnson graph $J(2D,D)$. Diaconis and Shahshahani
\cite{DiaSha87} obtained results on the rate of convergence (i.e., total
variation distance) to the stationary distribution in the latter model, using
the algebraic properties of the Johnson graph. They find a sharp cut-off point
at about $\frac14 D \log D$ steps, in the sense that a few steps earlier the
variation distance is essentially maximal, while a few steps later it tends to
0 exponentially fast. Belsley \cite{Bels98} obtained similar results for the
(non-bipartite) classical families of examples of Section
\ref{sec:clasfamilies}, and Hora \cite{Hora00} obtained results for the halved
cube and the quadratic forms graph (among others). Diaconis and Saloff-Coste
\cite{DiSaCo} studied separation cut-offs for infinite families of Markov
chains and applied their results to families of distance-regular graphs with
unbounded diameter.

Distance-regular graphs have also been used as examples for interacting particle systems such as the so-called
antivoter model; see \cite[Ch.~14]{Aldousbook}.

An application in finance is given by Billio, Cal\`{e}s, and Gu\'{e}gan
\cite{Billio}, who used random walks on the Johnson graph to study the momentum
strategy for stock portfolios.

\subsubsection{Chip-firing and the abelian sandpile model}

Chip-firing on a graph is a solitaire game that is related to random walks. It
is played with a pile of chips at each vertex of the graph. At each step of the
game, a vertex is {\em fired}, in the sense that a chip moves to each of its
adjacent vertices (if the vertex has sufficient chips). Chip-firing is related
to the abelian sandpile model for self-organized criticality from statistical
physics \cite{LevineSandpile}, to avalanche models, and the dollar game.
Related to these games and models is the critical group (sandpile group, Picard
group) of a graph. Biggs \cite{Biggschipfiring} observed that the critical
group of a distance-regular graph is in general not determined by the
intersection array. He also introduced a subgroup of layered configurations
that {\em is} determined by the intersection array. The Shrikhande graph and
Hamming graph $H(2,4)$ were discussed to illustrate these issues.

\subsubsection{Biggs' conjecture on resistance and potential}\label{sec:biggsconjecture}

Let $x$ be a vertex of $\G$, and suppose we start a random walk at $x$. For
every other vertex $y$, we let the {\it hitting time} $H_{xy}$ be the
expected number of steps needed to get to $y$. The {\it cover time} $C_x(\G)$
is the expected number of steps that a random walk started at $x$ requires
before it has visited every vertex of $\G$.

The calculations required to determine these notions for arbitrary graphs are
often quite intensive, even for moderately-sized graphs. It is therefore
desirable to study graphs possessing symmetry properties that make calculations
feasible. Van Slijpe \cite{Slijpe84}, Devroye and Sbihi \cite{DevSb90}, and
Biggs \cite{biggsp} all (independently) derived that in distance-regular
graphs, the hitting times for vertices $x$ and $y$ at distance $j$ are given in
terms of the intersection numbers and valencies by
$$H_{xy}=k \sum_{i=1}^j \frac{1}{k_ic_i} \sum_{h=i}^D k_h.$$
Biggs \cite{biggsp} did not have this result explicitly, as he stated it in
terms of potentials and electric resistance: let us consider a graph to be an
electric circuit with edges corresponding to resistors of unit resistance. The
effective resistance between two vertices can
--- in theory --- be calculated using the familiar rules for resistances in
series and in parallel. This resistance measures how easily electricity may
flow between the vertices, and can likewise be shown (see \cite{doysne} or
\cite{biggs97}) to measure how easily a random walk will move from one vertex
to another. Naturally, the higher the resistance between $x$ and $y$, the more
difficult it is for a random walk to pass from $x$ to $y$, and conversely. For
distance-regular graphs it is possible to give an explicit value for the
resistance between two vertices, as we shall now describe.

Let $\G$ be a distance-regular graph with valency at least 3. Using the
intersection numbers, define the {\it Biggs potentials} $\phi_i$ recursively by
$\phi_0=v-1$ and $\phi_i = (c_i\phi_{i-1}-k)/b_i$, for $i=0,1,\ldots,D-1.$

The resistance $\rho_j$ between vertices at distance $j$ is then
obtained by $\rho_j=2 \sum_{i=0}^{j-1}\phi_i/vk$; see \cite{biggsp}
(and the hitting time is a factor $vk/2$ larger). This shows that
understanding the behavior of the Biggs potentials is crucial for
the study of electric resistance in distance-regular graphs. Biggs
\cite{biggsp} conjectured that $\phi_1+ \phi_2+
\cdots + \phi_{D-1} \leq \frac{94}{101}\phi_0$ and thus $\max_j \rho_j = \rho_D
\leq (1 + \frac{94}{101}) \rho_1$ with equality only in the case of the
Biggs-Smith graph. This conjecture was later proved by Markowsky and Koolen
\cite{MK10}. It implies that the resistance between two vertices is always at
most $4/k$, and turns out to be a characteristic feature of the Biggs
potentials, namely that the sum of the later $\phi_i$ is dominated by the
earlier ones. In particular, Koolen, Markowsky, and Park \cite{phi1} showed\footnote{It was even conjectured that
the factor $3j+3$ can be replaced by a universal constant, but this was disproved in \cite{kmcollection}.}
that $\phi_{j+1} + \phi_{j+2}+ \cdots + \phi_{D-1} < (3j+3)\phi_j$ for each
$j = 0,1,\ldots,D-2$, and that $\phi_{2} + \phi_3 +
\cdots + \phi_{D-1} \leq \phi_1$ with equality only in the case of the
dodecahedron. The latter result can be used to prove Biggs' conjecture, and is
a much stronger statement. It also implies that if $D\geq 3$, then
$\rho_D/\rho_1 \leq 1+6/k$, which shows that for large $k$, all vertices become
nearly equidistant when measured with respect to the resistance metric.

By applying techniques from \cite{comcov}, the above implies the following for
the hitting times and cover times in distance-regular graphs: For all vertices
$x,y$, we have that $H_{xy} \leq (1+\min(\frac{6}{k},\frac{94}{101}))(v-1)$ and
$C_x(\G) \leq (4+o(1))(v-1)\ln{v}.$ In fact, Feige \cite{fue} showed that for
arbitrary graphs, we have $C_x(\G) \geq (1+o(1))v\ln{v}$, so that the upper
bound for distance-regular graphs is the best possible for large $v$, up to the
multiplicative constant.

We note that the resistances between vertices at distance at
most 3 in distance-regular graphs on at most 70 vertices have been calculated
explicitly by Jafarizadeh, Sufiani, and Jafarizadeh \cite{JaSuJa07}, whereas
those in some other families of distance-regular graphs, such as Hadamard
graphs, were calculated in \cite{JaSuJa09}.




\subsubsection{Quantum walks}

 The above classical random walks can be considered as
 Markov chains on the set of vertices of a graph, with the stochastic transition matrix $\frac1k A$. These
 have applications as described, but also in classical randomized algorithms.
 Likewise, in quantum information theory and quantum physics, there are applications of {\em quantum walks} in quantum
 computing. In the case of quantum walks, the state space is the set of
 directed edges (where each edge in the graph is replaced by two oppositely directed
 edges), and the transition matrix $U$ is unitary, that is, $UU^*=I$. For
 details, we refer to the introductory overview by
 Kempe \cite{Kempe03} and the more graph-theoretical description by Emms, Severini, Wilson, and
 Hancock \cite{Emms}.

The first results on quantum walks on distance-regular graphs
concerned the hypercubes, and were obtained by Moore and Russell \cite{MR2002P}
and Kempe \cite{Kempe}. Jafarizadeh and Salimi \cite{JaSa06} studied quantum
walks on, among others, Hamming graphs and Johnson graphs, using the quantum
decomposition $A=L+F+R$ (see \eqref{quantum decomposition}) of the adjacency
matrix.
See also Section \ref{sec:spectral analysis}.
Similarly, Salimi \cite{Salimi} considered the Odd graphs.

An important feature of quantum networks is {\em perfect state transfer}. This occurs for example between the
antipodes in the hypercubes. Godsil \cite{Godsilperiodic} obtained that if a distance-regular graph $\G$ has
perfect state transfer, then $\G$ is an antipodal double cover. He also constructed a family of Taylor graphs
with perfect state transfer coming from certain Hadamard matrices. Jafarizadeh and Sufiani \cite{JaSu08}
discussed perfect state transfer in several other distance-regular antipodal double covers. Coutinho, Godsil,
Guo, and Vanhove \cite{CGGV14} determined for many more distance-regular antipodal double covers whether they
have perfect state transfer; among others for all such graphs in the tables of `BCN' \cite{bcn}.
Chan \cite{Chan2013pre} showed among other results that for arbitrary $\tau>0$ there exist graphs having perfect state transfer at time less than $\tau$ by taking unions of some of the distance-$i$ graphs of the hypercubes.

See \cite{MR2002P,BKMT2008IJQI,Chan2013pre} for some work on \emph{instantaneous uniform mixing} of continuous-time quantum walks on the Hamming graphs, folded cubes, halved cubes, and the folded halved cubes.

\subsection{Miscellaneous applications}

New classes of error-correcting pooling designs were constructed by Bai, Huang,
and Wang \cite{BHW09} from Johnson graphs, Grassmann graphs, antipodal
distance-regular graphs, and distance-regular graphs of order $(s,t)$. Other
classes were constructed by Zhang, Guo, and Gao \cite{ZGG09}, who used
$D$-bounded distance-regular graphs. Gao, Guo, Zhang, and Fu \cite{GGZF08} used
subspaces in $D$-bounded distance-regular graphs to construct authentication
codes.

Some applications of distance-transitive graphs referred to by Cohen
\cite{cohen04} also apply to distance-regular graphs: Driscoll, Healy Jr., and
Rockmore \cite{DrHeRo} apply the discrete polynomial transform to obtain fast
algorithms for data analysis on distance-transitive graphs, mainly just by
using its three-term recurrence relation; Jwo and Tuan \cite{JwoTu} determined
the transmitting delay in networks that can be modeled as a distance-transitive
antipodal double cover (such as the hypercube).

Distance-regularity is one of the symmetry properties that are studied in a
survey paper by Lakshmivarahan, Jwo, and Dhall \cite{LaJwoDh} on
interconnection networks. Among others, shortest routing algorithms in such
networks are discussed.

Distance-regular graphs, in particular strongly regular graphs,
occur in constructions of energy minimizing spherical codes. As shown by Cohn,
Elkies, Kumar, and Sch\"urmann \cite{CEKS10}, spherical codes obtained from a
spectral embedding of a strongly regular graph are {\em balanced}, that is,
they are in equilibrium under all force laws acting between pairs of points
with strength given by a fixed function of distance. As a consequence, these
spherical codes appear frequently in the study of universally optimal spherical
codes; see \cite{CK07, BBCGKS09}.
