# On the spectral gap and the automorphism group of distance-regular graphs

Bohdan Kivva111University of Chicago, e-mail<EMAIL_ADDRESS>
###### Abstract

We prove that a distance-regular graph with a dominant distance is a spectral
expander. The key ingredient of the proof is a new inequality on the
intersection numbers. We use the spectral gap bound to study the structure of
the automorphism group.

The minimal degree of a permutation group $G$ is the minimum number of points
not fixed by non-identity elements of $G$. Lower bounds on the minimal degree
have strong structural consequences on $G$. In 2014 Babai proved that the
automorphism group of a strongly regular graph with $n$ vertices has minimal
degree $\geq cn$, with known exceptions. Strongly regular graphs correspond to
distance-regular graphs of diameter 2. Babai conjectured that Hamming and
Johnson graphs are the only primitive distance-regular graphs of diameter
$d\geq 3$ whose automorphism group has sublinear minimal degree. We confirm
this conjecture for non-geometric primitive distance-regular graphs of bounded
diameter. We also show if the primitivity assumption is removed, then only one
additional family of exceptions arises, the cocktail-party graphs. We settle
the geometric case in a companion paper.

##  1 Introduction

In this paper we prove a tradeoff between combinatorial and spectral
parameters of distance-regular graphs and apply the result to the structure of
the automorphism group.

###  1.1 Main results: Spectral expansion of distance-regular graphs

We say that a $k$-regular graph is a spectral $\eta$-expander for $\eta>0$, if
every non-principal eigenvalue $\xi_{i}$ of its adjacency matrix satisfies
$|\xi_{i}|\leq k(1-\eta)$. We say that a graph on $n$ vertices has
$(1-\varepsilon)$-dominant distance $t$, if among the $\binom{n}{2}$ pairs of
distinct vertices at least $(1-\varepsilon)\binom{n}{2}$ are at distance $t$.

In our main result on spectral expansion we show that distance-regular graphs
of bounded diameter are spectral expanders if they have
$(1-\varepsilon)$-dominant distance for sufficiently small $\varepsilon>0$,
depending only on the diameter.

######  Theorem 1.1.

For every $d\geq 2$ there exist $\epsilon=\epsilon(d)>0$ and $\eta=\eta(d)>0$
such that the following holds. If a distance-regular graph $X$ of diameter $d$
has a $(1-\epsilon)$-dominant distance, then $X$ is a spectral
$\eta$-expander.

We prove this theorem in equivalent formulation as Theorem 3.14, and its
slightly modified variant stated as Theorem 3.12 is the heart of the proof of
our main result on the minimal degree of the automorphism group (Theorem 1.6).

The key ingredient of our proof of the spectral expansion is the following (we
believe new) inequality for the intersection numbers of a distance-regular
graph. This inequality provides a tradeoff between $b_{j+1}$ and $c_{j+2}$, if
there are (significantly) more vertices at distance $j+1$ from a vertex $v$,
than vertices at distance $j$ from $v$. In particular, this inequality implies
that if $b_{j}$ is large and $c_{j+1}$ is small, then $c_{j+2}$ and $b_{j+1}$
cannot be small simultaneously.

######  Theorem 1.2 (Growth-induced tradeoff).

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Let $0\leq j\leq
d-2$. Assume $b_{j}>c_{j+1}$ and let $C=b_{j}/c_{j+1}$. Then for any $1\leq
s\leq j+1$ we have

$b_{j+1}\left(\sum\limits_{t=1}^{s}\frac{1}{b_{t-1}}+\sum\limits_{t=1}^{j+2-s}\frac{1}{b_{t-1}}\right)+c_{j+2}\sum\limits_{t=1}^{j+1}\frac{1}{b_{t-1}}\geq
1-\frac{4}{C-1}.$ (1)

Further comments on this result are in Remark 3.4. The proof appears in
Section 3.2 (see Theorem 3.3).

In a distance-regular graph denote by $\lambda$ and $\mu$ the number of common
neighbours of a pair of adjacent vertices and a pair of vertices at distance
2, respectively. We mention, that a result of Terwilliger [26], as
strengthened in [4, Theorem 4.3.3], shows that any non-principal eigenvalue of
a $k$-regular distance-regular graph $X$ has absolute value at most
$k-\lambda$ if $\mu>1$ and $X$ is not the icosahedron. This result assures
that $X$ is a spectral $\eta$-expander, if $\lambda\geq\eta k$. We note that
while both our result and Terwilliger’s result provide simple sufficient
combinatorial conditions for being spectral expanders, they are incomparable.
In fact, our primary motivation for a spectral gap bound is an application of
Lemma 1.14, where Terwilliger’s gap is not sufficient.

Additionally, we note that we do not exclude the elusive case $\mu=1$, for
which almost no classification results are known, and which is known to be a
difficult case in various circumstances. A remarkable example is the Bannai-
Ito conjecture, where the case $\mu=1$ was the only obstacle for 30 years, and
was resolved only recently in the breakthrough paper by Bang, Dubickas, Koolen
and Moulton [8].

###  1.2 Main results: Minimal degree of the automorphism group

Let $\sigma$ be a permutation of a set $\Omega$. The number of points not
fixed by $\sigma$ is called the degree of the permutation $\sigma$. Let $G$ be
a permutation group on the set $\Omega$. The minimum of the degrees of non-
identity elements in $G$ is called the minimal degree of $G$. We denote this
quantity by $\operatorname{mindeg}(G)$. The study of minimal degree goes back
to Jordan [15] and Bochert [10] in 19th century. Lower bounds on the minimal
degree have strong structural consequences on $G$. In 1934 Wielandt [28]
showed that a linear lower bound on the minimal degree implies a logarithmic
upper bound on the thickness of the group (the greatest $t$ for which the
alternating group $A_{t}$ is involved as a quotient group of a subgroup of $G$
[2]). Liebeck [18], Liebeck and Saxl [19] characterized all primitive
permutation groups with minimal degree less than $n/3$.

Switching from the theory of permutation groups to automorphisms of
combinatorial structures, we use the following terminology [23].

######  Definition 1.3 (Russell, Sundaram).

For a graph $X$ we use term motion for the minimal degree of the automorphism
group $\operatorname{Aut}(X)$,

$\operatorname{motion}(X):=\operatorname{mindeg}(\operatorname{Aut}(X)).$ (2)

In 2014 Babai [2] proved that the motion of a strongly regular graph is linear
in the number of vertices, with known exceptions.

######  Theorem 1.4 (Babai).

Let $X$ be a strongly regular graph on $n\geq 29$ vertices. Then either

$\operatorname{motion}(X)\geq n/8,$

or $X$, or its complement is a Johnson graph $J(s,2)$, a Hamming graph
$H(2,s)$ or a union of cliques.

The connected strongly-regular graphs are precisely distance-regular graphs of
diameter two. For distance-regular graphs of diameter $d\geq 3$ Babai made the
following conjecture.

######  Conjecture 1.5 (Babai).

For any $d\geq 3$ there exists $\gamma_{d}>0$, such that for any primitive
distance-regular graph $X$ of diameter $d$ with $n$ vertices either

$\operatorname{motion}(X)\geq\gamma_{d}n,$

or $X$ is the Hamming graph $H(d,s)$ or the Johnson graph $J(s,d)$.

We confirm this conjecture in a pair of papers. In the present paper we cover
the case when $X$ is not geometric. Moreover, we prove an eigenvalue lower
bound, which will be one of the main ingredients in the analysis of the
remaining cases in the companion paper [16].

######  Theorem 1.6.

For any $d\geq 3$ there exist $\gamma_{d}>0$ and a positive integer $m_{d}$,
such that for any primitive distance-regular graph $X$ of diameter $d$ with
$n$ vertices either

$\operatorname{motion}(X)\geq\gamma_{d}n,$

or $X$ is geometric with smallest eigenvalue at least $-m_{d}$.

We confirm Conjecture 1.5 for the cases not covered by the theorem above,
i.e., for geometric distance-regular graphs with bounded smallest eigenvalue,
in [16].

######  Remark 1.7.

The proof of the conjecture is split between two papers222This paper
significantly overlaps with the author’s earlier preprint arXiv:1802.06959.
The new results obtained since that posting warrant the current reorganization
of the material. In particular, that preprint did not address the imprimitive
case, and none of the main results of the companion paper [16] were available.
due to the different nature of techniques and results obtained. In particular,
in [16] we obtain a classification of geometric distance-regular graphs with
bounded smallest eigenvalue under certain combinatorial and spectral
assumptions, but with no assumption on the motion.

In Section 5 we analyze imprimitive distance-regular graphs and show that if
the primitivity assumption in Conjecture 1.5 is removed then only one new
family of exceptions arises. More precisely, we show that any imprimitive
distance-regular graph with sublinear motion is antipodal and its (primitive)
folded graph has sublinear motion as well. Note that all antipodal covers of
the Hamming graphs and Johnson graphs are known [27] (see Theorem 5.14 below).
Thus we prove that Conjecture 1.5 will automatically extend to the imprimitive
case as follows.

######  Theorem 1.8.

Assume Conjecture 1.5 is true. Then for any $d\geq 3$ there exists
$\widetilde{\gamma}_{d}>0$, such that for any distance-regular graph $X$ of
diameter $d$ on $n$ vertices either

$\operatorname{motion}(X)\geq\widetilde{\gamma}_{d}n,$

or $X$ is a Johnson graph $J(s,d)$, or a Hamming graph $H(d,s)$, or a
cocktail-party graph.

######  Remark 1.9.

We will give a proof of Conjecture 1.5 in [16], so the theorem above will turn
into an unconditional result.

###  1.3 Graphs with bounded smallest eigenvalue

In Theorem 1.6 we show that the exceptions with sublinear motion have bounded
smallest eigenvalue. A number of classification results is known under the
assumption of bounded smallest eigenvalue.

For strongly regular graphs, Neumaier [21] showed in 1979 that if the smallest
eigenvalue is $-m$ (for $m\geq 2$), then it is a Latin square graph
$LS_{m}(n)$, a Steiner graph $S_{m}(n)$, complete multipartite graph or one of
finitely many other graphs. A classification of the strongly regular graphs
with smallest eigenvalue $-2$ was known earlier (Seidel [24]) (1968) .
Moreover, in 1976 [11] Cameron, Goethals, Seidel and Shult gave a complete
classification of all graphs with smallest eigenvalue $-2$. They proved that
all but finitely many of such graphs have rich geometric structure (they are
generalized line graphs).

Bang and Koolen [17] proved that all but finitely many distance-regular graphs
with smallest eigenvalue $-m$ and $\mu\geq 2$ are geometric. For geometric
distance-regular graphs with smallest eigenvalue $\geq-3$ and $\mu\geq 2$ Bang
[6] and Bang, Koolen [7] gave a complete classification. Moreover, they
conjectured [17, Conjecture 7.4] that for any integer $m$ all but finitely
many geometric distance-regular graphs with smallest eigenvalue $-m$ and
$\mu\geq 2$ are known.

######  Conjecture 1.10 (Bang, Koolen).

For a fixed integer $m\geq 2$, any geometric distance-regular graph with
smallest eigenvalue $-m$, diameter $\geq 3$ and $\mu\geq 2$ is either a
Johnson graph, or a Hamming graph, or a Grassmann graph, or a bilinear forms
graph, or the number of vertices is bounded above by a function of $m$.

In [16] we confirm the above conjecture in the very special case, when the
second largest eigenvalue is sufficiently close to $b_{1}$, and some distance
$i$ is dominant. We note that all families mentioned in Conjecture 1.10 have
dominant distance $d$. Among these families, only the Hamming and the Johnson
graphs satisfy the assumption that the second largest eigenvalue is close to
$b_{1}$.

###  1.4 The main tools to bound motion

To obtain lower bounds on motion we follow the approach proposed by Babai in
[2]. In that paper he used a combination of an old combinatorial tool [1] and
a new spectral tool. We combine his tools with a structural theorem of Metsch.

####  1.4.1 Combinatorial tool

######  Definition 1.11 (Babai [1]).

A pair of vertices $u$ and $v$ is distinguished by a vertex $x$ in a graph $X$
if the distances $\operatorname{dist}(x,u)$ and $\operatorname{dist}(x,v)$ in
$X$ are distinct.

######  Definition 1.12.

In any graph define $D(u,v)$ to be the number of vertices that distinguish $u$
and $v$. Define the minimal distinguishing number $D_{\min}(X)$ of the graph
$X$ to be

$D_{\min}(X)=\min\limits_{u\neq v\in V}D(u,v).$

A simple observation shows that the minimal distinguishing number gives a
lower bound on the motion of a graph.

######  Lemma 1.13.

Let $X$ be a graph with $n$ vertices. If each pair of distinct vertices $u,v$
of $X$ is distinguished by at least $m$ vertices, then
$\operatorname{motion}(X)\geq m$.

###### Proof.

Indeed, let $\sigma\in\operatorname{Aut}(X)$ be any non-trivial automorphism
of $X$. Let $u$ be a vertex not fixed by $\sigma$. No fixed point of $\sigma$
distinguishes $u$ and $\sigma(u)$, so the degree of $\sigma$ is $\geq m$. ∎

####  1.4.2 Spectral tool

For a $k$-regular graph $X$ let $k=\xi_{1}\geq\xi_{2}\geq...\geq\xi_{n}$
denote the eigenvalues of the adjacency matrix of $X$. Following [2], we call
$\xi=\xi(X)=\max\\{|\xi_{i}|:2\leq i\leq n\\}$ the zero-weight spectral radius
of $X$. We refer to the quantity $(k-\xi)$ as the spectral gap of $X$. Note
that $\xi(X)\leq(1-\eta)k$ if and only if $X$ is a spectral $\eta$-expander.

The next lemma gives a lower bound on the motion of a regular graph $X$ in
terms of the zero-weight spectral radius and the maximum number of common
neighbors for a pair of distinct vertices in $X$.

######  Lemma 1.14 (Babai, [2, Proposition 12]).

Let $X$ be a regular graph of degree $k$ on $n$ vertices with zero-weight
spectral radius $\xi$. Suppose every pair of vertices in $X$ has at most $q$
common neighbors. Then

$\operatorname{motion}(X)\geq n\cdot\frac{(k-\xi-q)}{k}.$

Note that for bipartite graphs the zero-weight spectral radius equals $k$, the
degree of a vertex. So Lemma 1.14 cannot be applied. We prove a bipartite
analog in Section 5.1.

####  1.4.3 Structural tool

Together with the two tools mentioned, an important ingredient of our proofs
is Metsch’s geometricity criteria (see Theorem 2.7). Intuitively, Metsch’s
criteria states that if the number $\lambda$ of common neighbors of a pair of
adjacent vertices is much larger than the number $\mu$ of common neighbors of
a pair of vertices at distance 2, then the graph has a clique geometry (see
Definition 2.6).

####  1.4.4 How do we apply these tools?

We show that if a distance-regular graph $X$ is primitive and not a spectral
expander, then the minimal distinguishing number is linear in the number of
vertices. Thus we can apply the Combinatorial tool.

Hence, we may assume that the graph $X$ is a spectral expander. If $\lambda$
and $\mu$ are small, a linear lower bound on motion follows from the Spectral
tool. If $\mu$ is large, we again show that the minimal distinguishing number
is linear in the number of vertices.

Finally, in the remaining case when $\lambda$ is large and $\mu$ is small, we
use the Metsch criteria to deduce geometricity of $X$.

###  1.5 Organization of the paper

Basic concepts and definitions are given in Section 2. In Section 3 we prove
the spectral gap bound for distance-regular graphs with dominant color. More
specifically, in Section 3.1 we use the perturbation theory of matrices to
show that under modest assumptions on the intersection numbers, the spectrum
of a graph can be approximated by the intersection numbers $a_{i}$. In Section
3.2 we prove a growth-induced tradeoff for the intersection numbers (Theorem
1.2). In Section 3.3 we use this inequality to derive our main result on
spectral expansion (Theorem 1.1).

In Section 4 we analyze the motion of distance-regular graphs and prove our
main result about automorphism groups (Theorem 1.6).

Finally, in Section 5 we prove a bipartite analog of the Spectral tool and
show that this is sufficient to prove Conjecture 1.5 to obtain a similar
classification for imprimitive graphs (Theorem 1.8).

## Acknowledgments

The author is grateful to Professor László Babai for introducing him to the
problems discussed in the paper and suggesting possible ways of approaching
them, his invaluable assistance in framing the results, and constant support
and encouragement.

##  2 Preliminaries

In this section we introduce distance-regular graphs and other related
definitions and concepts that will be used throughout the paper. For more
about distance-regular graphs we refer the reader to the monograph [4] and the
survey article [12].

###  2.1 Basic concepts and notation for graphs

Let $X$ be a graph. We will always denote by $n$ the number of vertices of $X$
and if $X$ is regular we denote by $k$ its degree. Denote by
$\lambda=\lambda(X)$ the minimum number of common neighbors for pairs of
adjacent vertices in $X$. Denote by $\mu=\mu(X)$ the maximum number of common
neighbors for pairs of vertices at distance 2. We will denote the diameter of
$X$ by $d$. If the graph is disconnected, then its diameter is defined to be
$\infty$. Denote by $q(X)$ the maximum number of common neighbors of two
distinct vertices in $X$.

Let $N(v)$ be the set of neighbors of vertex $v$ in $X$ and $N_{i}(v)=\\{w\in
X|\operatorname{dist}(v,w)=i\\}$ be the set of vertices at distance $i$ from
$v$ in the graph $X$.

Let $A$ be the adjacency matrix of $X$. Suppose that $X$ is $k$-regular. Then
the all-ones vector is an eigenvector of $A$ with eigenvalue $k$. We will call
them the trivial (principal) eigenvector and the trivial (principal)
eigenvalue. All other eigenvalues of $A$ have absolute value not greater than
$k$. We call them non-trivial (non-principal) eigenvalues.

###  2.2 Distance-regular graphs

######  Definition 2.1.

A connected graph $X$ of diameter $d$ is called distance-regular if for any
$0\leq i\leq d$ there exist constants $a_{i},b_{i},c_{i}$ such that for any
$v\in X$ and any $w\in N_{i}(v)$ the number of edges between $w$ and
$N_{i}(v)$ is $a_{i}$, between $w$ and $N_{i+1}(v)$ is $b_{i}$, and between
$w$ and $N_{i-1}(v)$ is $c_{i}$. The sequence

$\iota(X)=\\{b_{0},b_{1},\ldots,b_{d-1};c_{1},c_{2},\ldots,c_{d}\\}$

is called the intersection array of $X$.

Note, that for a distance-regular graph $b_{d}=c_{0}=0$, $b_{0}=k$, $c_{1}=1$,
$\lambda=a_{1}$ and $\mu=c_{2}$. By edge counting, the following
straightforward properties of the parameters of a distance-regular graph hold.

  1. 1.

$a_{i}+b_{i}+c_{i}=k$ for every $0\leq i\leq d$,

  2. 2.

$|N_{i}(v)|b_{i}=|N_{i+1}(v)|c_{i+1}$, $\Rightarrow\quad$ $k_{i}:=|N_{i}(v)|$
does not depend on vertex $v\in X$.

  3. 3.

$b_{i+1}\leq b_{i}$ and $c_{i+1}\geq c_{i}$ for $0\leq i\leq d-1$.

With any graph of diameter $d$ we can naturally associate matrices $A_{i}\in
M_{n}(\mathbb{R})$, for which rows and columns are marked by vertices, with
entries $(A_{i})_{u,v}=1$ if and only if $\operatorname{dist}(u,v)=i$. That
is, $A_{i}$ is the adjacency matrix of the distance-$i$ graph $X_{i}$ of $X$.
For a distance-regular graph they satisfy the relations

$A_{0}=I,\quad A_{1}=:A,\quad\sum\limits_{i=0}^{d}A_{i}=J,$ (3)
$AA_{i}=c_{i+1}A_{i+1}+a_{i}A_{i}+b_{i-1}A_{i-1}\quad\text{for }0\leq i\leq
d,$ (4)

where $c_{d+1}=b_{-1}=0$ and $A_{-1}=A_{d+1}=0$. Clearly, Eq. (4) implies that
for every $0\leq i\leq d$ there exists a polynomial $\nu_{i}$ of degree
exactly $i$, such that $A_{i}=\nu_{i}(A)$. Moreover, the minimal polynomial of
$A$ has degree exactly $d+1$. Hence, since $A$ is symmetric, $A$ has exactly
$d+1$ distinct real eigenvalues. Additionally, we conclude that for all $0\leq
i,j,s\leq d$ there exist intersection numbers $p_{i,j}^{s}$, such that

$A_{i}A_{j}=\sum\limits_{s=0}^{d}p_{i,j}^{s}A_{s}.$

The definition of $A_{i}$ implies that for any $u,v\in X$ with
$\operatorname{dist}(u,v)=s$ there exist exactly $p_{i,j}^{s}$ vertices at
distance $i$ from $u$ and distance $j$ from $v$, i.e., $|N_{i}(u)\cap
N_{j}(v)|=p_{i,j}^{s}$.

Note, that

$p_{1,i}^{i-1}=b_{i-1},\quad p_{1,i}^{i}=a_{i},\quad p_{1,i}^{i+1}=c_{i+1}.$

######  Definition 2.2.

A distance-regular graph $X$ of diameter $d$ is called primitive if for each
$i\in[d]$ the distance-$i$ graph $X_{i}$ of $X$ is connected.

Let $\eta$ be an eigenvalue of $A$, then Eq. (4) implies that

$\eta\nu_{i}(\eta)=c_{i+1}\nu_{i+1}(\eta)+a_{i}\nu_{i}(\eta)+b_{i-1}\nu_{i-1}(\eta),\text{
so}$ $\eta
u_{i}(\eta)=c_{i}u_{i-1}(\eta)+a_{i}u_{i}(\eta)+b_{i}u_{i+1}(\eta),$

where $u_{i}(\eta)=\frac{\nu_{i}(\eta)}{k_{i}}$. Therefore, the eigenvalues of
$A$ are precisely the eigenvalues of tridiagonal $(d+1)\times(d+1)$
intersection matrix

$T(X)=\left(\begin{matrix}a_{0}&b_{0}&0&0&...\\\ c_{1}&a_{1}&b_{1}&0&...\\\
0&c_{2}&a_{2}&b_{2}&...\\\ ...&&\vdots&&...\\\
...&&0&c_{d}&a_{d}\par\end{matrix}\right).$

###  2.3 Johnson and Hamming graphs

In this section we define families of graphs with huge automorphism groups. In
particular, for certain range of parameters they have motion sublinear in the
number of vertices.

######  Definition 2.3.

Let $d\geq 2$ and $\Omega$ be a set of $m\geq 2d+1$ points. The Johnson graph
$J(m,d)$ is a graph on a set $V(J(m,d))=\binom{\Omega}{d}$ of $n=\binom{m}{d}$
vertices, for which two vertices are adjacent if and only if the corresponding
subsets $U_{1},U_{2}\subseteq\Omega$ differ by exactly one element, i.e.,
$|U_{1}\setminus U_{2}|=|U_{2}\setminus U_{1}|=1$.

It is not hard to check that $J(m,d)$ is a distance-regular graph of diameter
$d$ with intersection numbers

$b_{i}=(d-i)(m-d-i)\quad\text{and}\quad c_{i+1}=(i+1)^{2},\quad\text{for
}0\leq i<d.$

In particular, $J(m,d)$ is regular of degree $k=d(m-d)$ with $\lambda=m-2$ and
$\mu=4$. The eigenvalues of $J(m,d)$ are

$\xi_{j}=(d-j)(m-d-j)-j\quad\text{with
multiplicity}\quad\binom{m}{j}-\binom{m}{j-1},\,\text{for }0\leq j\leq d.$

The automorphism group of $J(m,d)$ is the induced symmetric group
$S_{m}^{(d)}$, which acts on $\binom{\Omega}{d}$ via the induced action of
$S_{m}$ on $\Omega$. Indeed, it is clear, that
$S^{(d)}_{m}\leq\operatorname{Aut}(J(m,d))$. The opposite inclusion can be
derived from the Erdős-Ko-Rado theorem.

Thus, for a fixed $d$ we get that the order is
$|\operatorname{Aut}(J(m,d)|=m!=\Omega(\exp(n^{1/d}))$, the thickness
satisfies $\theta(\operatorname{Aut}(J(m,d)))=m=\Omega(n^{1/d})$ and

$\operatorname{motion}(J(m,d))=O(n^{1-1/d}).$

######  Definition 2.4.

Let $\Omega$ be a set of $m\geq 2$ points. The Hamming graph $H(d,m)$ is a
graph on a set $V(H(d,m))=\Omega^{d}$ of $n=m^{d}$ vertices, for which a pair
of vertices is adjacent if and only if the corresponding $d$-tuples
$v_{1},v_{2}$ differ in precisely one position. In other words, if the Hamming
distance $d_{H}(v_{1},v_{2})$ for the corresponding tuples equals 1.

Again, it is not hard to check that $H(d,m)$ is a distance-regular graph of
diameter $d$ with intersection numbers

$b_{i}=(d-i)(m-1)\quad\text{and}\quad c_{i+1}=i+1,\quad\text{for }0\leq i\leq
d-1.$

In particular, $H(d,m)$ is regular of degree $k=d(m-1)$ with $\lambda=m-2$ and
$\mu=2$. The eigenvalues of $H(d,m)$ are

$\xi_{j}=d(m-1)-jm\quad\text{with
multiplicity}\quad\binom{d}{j}(m-1)^{j},\,\text{for }0\leq j\leq d.$

The automorphism group of $H(d,m)$ is isomorphic to the wreath product
$S_{m}\wr S_{d}$. Hence, its order is
$|\operatorname{Aut}(H(d,m))|=(m!)^{d}d!$, the thickness satisfies
$\theta(H(d,m))\geq m=n^{1/d}$ and

$\operatorname{motion}(H(d,m))\leq 2m^{d-1}=O(n^{1-1/d}).$

###  2.4 Geometric distance-regular graphs

In this section we discuss geometric distance-regular graphs. More on
geometric distance-regular graphs can be found in [12] and [5].

Let $X$ be a distance-regular graph, and $\theta_{\min}$ be its smallest
eigenvalue. Delsarte proved in [13] that any clique $C$ in $X$ satisfies
$|C|\leq 1-k/\theta_{\min}$. A clique in $X$ of size $1-k/\theta_{\min}$ is
called a Delsarte clique.

######  Definition 2.5.

A distance-regular graph $X$ is called geometric if there exists a collection
$\mathcal{C}$ of Delsarte cliques such that every edge of $X$ lies in
precisely one clique from $\mathcal{C}$.

######  Definition 2.6.

We say that a graph $X$ contains a clique geometry, if there exists a
collection $\mathcal{C}_{0}$ of maximal cliques, such that every edge is
contained in precisely one clique from $\mathcal{C}_{0}$.

Metsch proved that a graph $X$ under rather modest assumptions contains a
clique geometry.

######  Theorem 2.7 (Metsch [20, Result 2.2]).

Let $\mu$, $\lambda^{(1)},\lambda^{(2)}$ and $m$ be positive integers. Assume
that $X$ is a connected graph with the following properties.

  1. 1.

Every pair of adjacent vertices has at least $\lambda^{(1)}$ and at most
$\lambda^{(2)}$ common neighbors.

  2. 2.

Every pair of non-adjacent vertices has at most $\mu$ common neighbors.

  3. 3.

$2\lambda^{(1)}-\lambda^{(2)}>(2m-1)(\mu-1)-1$.

  4. 4.

Every vertex has fewer than $(m+1)(\lambda^{(1)}+1)-\frac{1}{2}m(m+1)(\mu-1)$
neighbors.

Define a _line_ to be a maximal clique $C$ satisfying
$|C|\geq\lambda^{(1)}+2-(m-1)(\mu-1)$. Then every vertex is on at most $m$
lines, and every pair of adjacent vertices lies in a unique line.

######  Remark 2.8.

Suppose that $X$ satisfies the conditions of the previous theorem. Then the
smallest eigenvalue of $X$ is at least $-m$.

###### Proof.

Let $\mathcal{C}$ be the collection of lines of $X$. Consider
$|V|\times|\mathcal{C}|$ vertex-clique incidence matrix $N$. That is,
$(N)_{v,C}=1$ if and only if $v\in C$ for $v\in X$ and $C\in\mathcal{C}$.
Since every edge belongs to exactly one line, we get $NN^{T}=A+D$, where $A$
is the adjacency matrix of $X$ and $D$ is a diagonal matrix. Moreover,
$(D)_{v,v}$ equals to the number of lines that contain $v$. By the previous
theorem, $D_{v,v}\leq m$ for every $v\in X$. Thus,

$A+mI=NN^{T}+(mI-D)$

is positive semidefinite, so all eigenvalues of $A$ are at least $-m$. ∎

We will use the following sufficient conditions of geometricity.

######  Proposition 2.9 ([12, Proposition 9.8]).

Let $X$ be a distance-regular graph of diameter $d$. Assume there exist a
positive integer $m$ and a clique geometry $\mathcal{C}$ of $X$ such that
every vertex $u$ is contained in exactly $m$ cliques of $\mathcal{C}$. If
$|\mathcal{C}|<|V(X)|=n$, then $X$ is geometric with smallest eigenvalue $-m$.
Moreover, $|\mathcal{C}|<n$ holds if $\min\\{|C|:C\in\mathcal{C}\\}>m$.

######  Corollary 2.10 ([12, Proposition 9.9, restated]).

Let $m\geq 2$ be an integer, and let $X$ be a distance-regular graph with
$(m-1)(\lambda+1)<k\leq m(\lambda+1)$ and diameter $d\geq 2$. If
$\lambda\geq\frac{1}{2}m(m+1)\mu$, then $X$ is geometric with smallest
eigenvalue $-m$.

###### Proof.

Directly follows from Theorem 2.7 and Proposition 2.9. ∎

###  2.5 Imprimitive distance-regular graphs

Here we shortly describe some basic properties of imprimitive distance-regular
graphs that we will need later. Recall that a distance-regular graph $X$ is
imprimitive if for some $1\leq i\leq d$ the distance-$i$ graph $X_{i}$ is
disconnected. Smith’s theorem states that there are only two types of
imprimitive distance-regular graphs.

######  Definition 2.11.

A distance-regular graph $X$ of diameter $d$ is called antipodal if being at
distance $d$ in $X$ is an equivalence relation, namely if $X_{d}$ is a
disjoint union of cliques.

######  Theorem 2.12 (D. H. Smith [25]).

An imprimitive distance-regular graph of degree $k>2$ is bipartite or
antipodal (or both).

If $X$ is a bipartite graph, then $X_{2}$ has two connected components $X^{+}$
and $X^{-}$, which are called the halved graphs of $X$ and are denoted
$\frac{1}{2}X$.

For an antipodal graph $X$ of diameter $d$, define the graph $\widetilde{X}$
which has the equivalence classes of $X_{d}$ as vertices and two equivalence
classes are adjacent if they contain adjacent vertices. The graph
$\widetilde{X}$ is called the folded graph of $X$.

In the next proposition we list some information about the intersection
numbers of halved and folded graphs, which we will need later.

######  Proposition 2.13 (Biggs, Gardiner [9], see [4, Proposition 4.2.2]).

Let $X$ be a distance-regular graph with intersection array
$\iota(X)=\\{b_{0},b_{1},\ldots,b_{d-1};c_{1},c_{2},\ldots,c_{d}\\}$ and
diameter $d\in\\{2t,2t+1\\}$.

  1. 1.

The graph $X$ is bipartite if and only if $b_{i}+c_{i}=k$ for
$i=0,1,\ldots,d$. In this case halved graphs are distance-regular of diameter
$t$ with intersection array

$\iota(X^{\pm})=\left\\{\frac{b_{0}b_{1}}{\mu},\frac{b_{2}b_{3}}{\mu},\ldots,\frac{b_{2t-2}b_{2t-1}}{\mu};\frac{c_{1}c_{2}}{\mu},\frac{c_{3}c_{4}}{\mu},\ldots,\frac{c_{2t-1}c_{2t}}{\mu}\right\\}.$

  2. 2.

The graph $X$ is antipodal if and only if $b_{i}=c_{d-i}$ for $i\neq t$. In
this case $X$ is an antipodal $r$-cover of its folded graph $\widetilde{X}$,
where $r=1+b_{t}/c_{d-t}$. If $d>2$, then $\widetilde{X}$ is distance-regular
of diameter $t$ with intersection array

$\iota(\widetilde{X})=\\{b_{0},b_{1},\ldots
b_{t-1};c_{1},c_{2},\ldots,c_{t-1},\gamma c_{t}\\},$

where $\gamma=r$, if $d=2t$; and $\gamma=1$, if $d=2t+1$.

It is not hard to show that given a distance-regular graph of degree $k>2$ one
may obtain a primitive distance-regular graph after halving at most once and
folding at most once. More precisely, the following is true.

######  Proposition 2.14 (see [4, Sec. 4.2.A]).

Let $X$ be a distance-regular graph of degree $k>2$.

  1. 1.

If $X$ is a bipartite graph, then its halved graph is not bipartite.

  2. 2.

If $X$ is bipartite and either has odd diameter or is not antipodal, then its
halved graph is primitive.

  3. 3.

If $X$ is antipodal and either has odd diameter or is not bipartite, then its
folded graph is primitive.

  4. 4.

If $X$ has even diameter and is both antipodal and bipartite, then the halved
graphs $\frac{1}{2}X$ are antipodal, the folded graph $\widetilde{X}$ is
bipartite and the graphs
$\widetilde{\frac{1}{2}X}\cong\frac{1}{2}\widetilde{X}$ are primitive.

###  2.6 Approximation tool

In Sections 3 we use the fact that eigenvalues of a matrix do not differ much
from the eigenvalues of its small perturbation.

######  Theorem 2.15 (Ostrowski [22, Appendix K]).

Let $A,B\in M_{n}(\mathbb{C})$. Let $\lambda_{1},\lambda_{2},...,\lambda_{n}$
be the roots of the characteristic polynomial of $A$ and
$\mu_{1},\mu_{2},...,\mu_{n}$ be the roots of the characteristic polynomial of
$B$. Consider

$M=\max\\{|(A)_{ij}|,|(B)_{ij}|:1\leq i,j\leq
n\\},\quad\delta=\frac{1}{nM}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}|(A)_{ij}-(B)_{ij}|.$

Then, there exists a permutation $\sigma\in S_{n}$ such that

$|\lambda_{i}-\mu_{\sigma(i)}|\leq 2(n+1)^{2}M\delta^{1/n},\quad\text{for all
}1\leq i\leq n.$

##  3 Spectral gap of a distance-regular graph

In this section we give a bound on the spectral gap of a distance-regular
graph in terms of its intersection numbers. The spectral gap bound will be
used in Sections 4 and 5 to achieve motion lower bounds through Lemma 1.14
(the Spectral tool).

###  3.1 Approximation of the spectrum by the intersection numbers

Note, that if $b_{i}$ and $c_{i}$ are simultaneously small, then by
monotonicity, $b_{j}$ for $j\geq i$ and $c_{t}$ for $t\leq i$ are small.
Hence, the intersection matrix $T(X)$ is a small perturbation of a block
diagonal matrix $N$, where one block is upper triangular and the other block
is lower triangular. So the eigenvalues of $N$ are just the diagonal entries.

######  Lemma 3.1.

Let $X$ be a distance-regular graph of diameter $d$. Denote by
$\theta_{0}>\theta_{1}>\ldots>\theta_{d}$ all distinct eigenvalues of $X$.
Suppose that $b_{i}\leq\varepsilon k$ and $c_{i}\leq\varepsilon k$ for some
$i\leq d$ and $\varepsilon>0$. Then

$|\theta_{i}-a_{i}|\leq 2(d+2)^{2}\varepsilon^{\frac{1}{d+1}}k.$

In particular, if furthermore $b_{i-1}\geq\alpha k$ and $c_{i+1}\geq\alpha k$,
for some $\alpha>0$ (here we define $c_{d+1}=k$), then the zero-weight
spectral radius $\xi$ of $X$ satisfies

$\xi\leq k(1-\alpha+2(d+2)^{2}\varepsilon^{\frac{1}{d+1}}).$ (5)

###### Proof.

Consider the matrix

$T=T(X)=\left(\begin{matrix}a_{0}&b_{0}&0&0&...\\\ c_{1}&a_{1}&b_{1}&0&...\\\
0&c_{2}&a_{2}&b_{2}&...\\\ ...&&\vdots&&...\\\
...&&0&c_{d}&a_{d}\end{matrix}\right)$

Let $N$ be a matrix obtained from $T$ by replacing all $b_{s}$ and $c_{t}$
with 0 for $s\geq i$ and $t\leq i$. As in Theorem 2.15, consider

$M=\max\\{|(T)_{sj}|,|(N)_{sj}|:1\leq s,j\leq d\\}=k,$
$\delta=\frac{1}{(d+1)M}\sum\limits_{s=1}^{d+1}\sum\limits_{j=1}^{d+1}|(T)_{sj}-(N)_{sj}|\leq\frac{(d+1)\varepsilon
k}{(d+1)M}=\varepsilon.$

Observe, that the diagonal entry $a_{i}$ is the only non-zero entry in the
$i$-th row of $N$. Furthermore, the upper-left $i\times i$ submatrix is upper
triangular and $(d-i)\times(d-i)$ lower-right submatrix is lower triangular.
Then the eigenvalues of $N$ are equal to $a_{j}$ for $0\leq j\leq d$. Thus,
the first part of the statement follows from Theorem 2.15.

The inequalities $b_{i-1}\geq\alpha k$ and $c_{i+1}\geq\alpha k$ imply that
$a_{j}\leq k(1-\alpha)$ for $j\neq i$, while $a_{i}\geq(1-2\varepsilon)k$.
Hence, since $k$ is an eigenvalue of multiplicity 1 of $X$, the zero-weight
spectral radius of $X$ satisfies Eq. (5). ∎

###  3.2 A growth-induced tradeoff for the intersection numbers

######  Observation 3.2.

Let $X$ be a graph. Denote by $\deg(v)$ the degree of a vertex $v$ in $X$, and
denote by $N(u,v)$ the set of common neighbors of vertices $u$ and $v$ in $X$.
Then for any vertices $u,v,w$ we have

$|N(u,v)|+|N(u,w)|\leq\deg(u)+|N(v,w)|.$

###### Proof.

The inequality above follows from the two obvious inclusions below

$N(u,v)\cup N(u,w)\subseteq N(u),\qquad\quad N(u,v)\cap N(u,w)\subseteq
N(v,w).$

∎

Next, we prove the growth-induced tradeoff for the intersection numbers.
Essentially, the theorem below claims that, if for some $j$, $b_{j}$ is large
(and therefore, by monotonicity, so are $b_{i}$ for $i\leq j$) and $c_{j+1}$
is small, then $b_{j+1}$ and $c_{j+2}$ cannot be small simultaneously.

######  Theorem 3.3 (Growth-induced tradeoff).

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Let $0\leq j\leq
d-2$. Assume $b_{j}>c_{j+1}$ and let $C=b_{j}/c_{j+1}$. Then for any $1\leq
s\leq j+1$ we have

$b_{j+1}\left(\sum\limits_{t=1}^{s}\frac{1}{b_{t-1}}+\sum\limits_{t=1}^{j+2-s}\frac{1}{b_{t-1}}\right)+c_{j+2}\sum\limits_{t=1}^{j+1}\frac{1}{b_{t-1}}\geq
1-\frac{4}{C-1}.$ (6)

######  Remark 3.4.

In applications we require the right-hand side to be bounded away from zero,
i.e., $C$ to be grater than some constant $>5$. In the case when
$b_{j}\geq\alpha k$ for some constant $\alpha>0$, each reciprocal $1/b_{t}$
for $t\leq j$ is at most $1/(\alpha k)$. Thus, if the RHS is bounded away from
zero and $d$ is bounded, we get a lower bound on $b_{j+1}$ or $c_{j+2}$ that
is linear in $k$. We also note that $b_{j}/c_{j+1}=k_{j+1}/k_{j}$, where
$k_{j}$ is the size of the sphere of radius $j$ in $X$. So the assumption says
that significant growth occurs from radius $j$ to radius $j+1$.

###### Proof of Theorem 3.3.

Consider the graph $Y$ with the set of vertices $V(Y)=V(X)$, where two
vertices $u,v$ are adjacent if they are at distance
$\operatorname{dist}(u,v)\leq j+1$ in $X$. We want to find the restriction on
the parameters of $X$ implied by Observation 3.2 applied to graph $Y$ and
vertices $w,v$ at distance $j+2$ in $X$. Let $\lambda_{i}^{Y}$ denote the
number of common neighbors in $Y$ for a pair of vertices $u,v$ at distance $i$
in $X$ for $i\leq j+1$. Let $\mu_{j+2}^{Y}$ denote the number of common
neighbors in $Y$ for a pair of vertices $u,v$ at distance $j+2$ in $X$. The
monotonicity of sequences $(b_{i})$ and $(c_{i})$ implies $k_{i+1}\geq Ck_{i}$
for $i\leq j$. Thus, the degree of every vertex in $Y$ satisfies

$k^{Y}=\sum\limits_{i=1}^{j+1}k_{i}\leq k_{j+1}\sum\limits_{i=0}^{j}C^{-i}\leq
k_{j+1}\frac{C}{C-1}.$

Note, that $\displaystyle{\sum\limits_{t=0}^{d}p^{i}_{s,t}=k_{s}}$. Hence, we
have

$\mu_{j+2}^{Y}=\sum\limits_{1\leq s,t\leq j+1}p^{j+2}_{s,t}\leq
2\sum\limits_{i=1}^{j}k_{i}+p^{j+2}_{j+1,j+1}\leq\frac{2}{C-1}k_{j+1}+p^{j+2}_{j+1,j+1},$
$\lambda_{i}^{Y}=\sum\limits_{1\leq s,r\leq
j+1}p^{i}_{r,s}\geq\sum\limits_{1\leq s\leq
j+1}p^{i}_{j+1,s}=k_{j+1}-\sum\limits_{j+2\leq s\leq
d}p^{i}_{j+1,s}-p_{j+1,0}^{i}.$

Now we are going to get some bounds on $\displaystyle{\sum\limits_{j+2\leq
s\leq d}p^{i}_{j+1,s}}$. We use the following observation. Suppose, that $x,y$
are two vertices at distance $i$. Then there are exactly
$\displaystyle{\prod\limits_{t=1}^{i}c_{t}}$ paths of length $i$ between $x$
and $y$. Thus,
$\displaystyle{\left(\prod\limits_{t=1}^{i}c_{t}\right)\sum\limits_{s=j+2}^{d}p^{j+1}_{i,s}}$
equals to the number of paths of length $i$ starting at $v$ and ending at
distance at least $j+2$ from $u$ and at distance $i$ from $v$, where
$\operatorname{dist}(u,v)=j+1$ in $X$. We count such paths by considering
possible choices of edges for a path at every step. At step $t$ every such
path should go from $N_{t-1}(v)$ to $N_{t}(v)$, hence there are at most
$b_{t-1}$ possible choices for a path at step $t$ for $1\leq t\leq i$.
Moreover, since path should end up at distance at least $j+2$ from $u$, then
for some $1\leq t\leq i$ path should go from $N_{j+1}(u)$ to $N_{j+2}(u)$.
Therefore, the number of paths that go from $N_{j+1}(u)$ to $N_{j+2}(u)$ at
step $t$ is at most
$\displaystyle{\left(\prod\limits_{s=1}^{i}b_{s-1}\right)\frac{b_{j+1}}{b_{t-1}}}$.
Hence,

$\sum\limits_{s=j+2}^{d}p^{i}_{j+1,s}=\frac{k_{j+1}}{k_{i}}\sum\limits_{s=j+2}^{d}p^{j+1}_{i,s}\leq\frac{k_{j+1}}{k_{i}}\sum\limits_{t=1}^{i}\left(\prod\limits_{s=1}^{i}b_{s-1}\right)\frac{b_{j+1}}{b_{t-1}}\left(\prod\limits_{t=1}^{i}c_{t}\right)^{-1}=k_{j+1}\sum\limits_{t=1}^{i}\frac{b_{j+1}}{b_{t-1}}.$

Thus, in particular,

$\lambda_{i}^{Y}\geq
k_{j+1}\left(1-\sum\limits_{t=1}^{i}\frac{b_{j+1}}{b_{t-1}}\right)-p_{j+1,0}^{i}.$
(7)

Similarly,

$p_{j+1,j+1}^{j+2}\leq k_{j+1}\sum\limits_{t=1}^{j+1}\frac{c_{j+2}}{b_{t-1}}.$

Hence,

$\mu_{j+2}^{Y}\leq
k_{j+1}\left(\frac{2}{C-1}+\sum\limits_{t=1}^{j+1}\frac{c_{j+2}}{b_{t-1}}\right).$
(8)

By applying Observation 3.2 to vertices $u$, $v$, and $w$ in $Y$, that satisfy
$\operatorname{dist}(v,w)=j+2$, $\operatorname{dist}(u,v)=s$ and
$\operatorname{dist}(w,u)=j+2-s$ in $X$, we get

$k_{j+1}+\mu_{j+2}^{Y}\geq\lambda_{s}^{Y}+\lambda_{j+2-s}^{Y}.$ (9)

The desired inequality (6) follows from Eq. (7), (8) and (9), as
$p_{j+1,0}^{i}\leq 1\leq k_{j+1}/C$. ∎

###  3.3 Spectral gap bound

In this section we prove a bound on the spectral gap of distance-regular
graphs of fixed diameter $d$ with a dominant distance. We prove Theorem 1.1 in
the equivalent formulation as Theorem 3.14.

Our key tool is the growth-induced tradeoff proven in the previous section,
which will be applied in the following setup. Assume we know lower bounds for
the intersection numbers $b_{i}$ of the form $b_{i}\geq\alpha_{i}k$. Our goal
is to get a lower bound of the similar form either for $b_{j+1}$, or for
$c_{j+2}$. We will argue, that if either $c_{j+2}\leq\varepsilon k$, or
$b_{j+1}\leq\varepsilon k$, for a sufficiently small $\varepsilon>0$, then
either second or first summand of the LHS in inequality (6) is at most a
$\delta$-fraction of the LHS. Hence, the other summand is at least
$(1-\delta)$-fraction of the LHS and we get a linear in $k$ lower bound on
either $b_{j+1}$, or $c_{j+2}$. The two sequences we define below are the
coefficients in front of $k$ in the bounds we get from inequality (6).

######  Definition 3.5.

Let $0\leq\delta<1$. We say that $(\alpha_{i})_{i=0}^{\infty}$ is the
$FE(\delta)$ sequence, if $\alpha_{0}=1$ and for $j\geq 1$ the element
$\alpha_{j}$ is defined by the recurrence

$\alpha_{j+1}=(1-\delta)\left(\sum\limits_{t=1}^{\left\lceil\frac{j+2}{2}\right\rceil}\frac{1}{\alpha_{t-1}}+\sum\limits_{t=1}^{\left\lfloor\frac{j+2}{2}\right\rfloor}\frac{1}{\alpha_{t-1}}\right)^{-1}.$
(10)

Let $\widehat{\alpha}=(\alpha_{i})_{i=0}^{s}$ be a sequence. We say that
$\widehat{\beta}=(\beta_{i})_{i=2}^{s+2}$ is the $BE(\delta,\widehat{\alpha})$
sequence, if for $j\geq 2$ the element $\beta_{j}$ is defined as

$\beta_{j}=(1-\delta)\left(\sum\limits_{t=0}^{j-2}\frac{1}{\alpha_{t}}\right)^{-1}.$
(11)

If additionally, $\widehat{\alpha}$ is the $FE(\delta)$ sequence, then we will
say that $\widehat{\beta}$ is the $BE(\delta)$ sequence.

######  Remark 3.6.

FE stands for “forward expansion” and BE stands for “backward expansion”.

Now we specify how small we expect $\varepsilon$ to be in the argument above,
so that one of the summands in the LHS of (6) is at most a $\delta$-fraction
of the LHS.

######  Definition 3.7.

Let $\widehat{\alpha}=(\alpha)_{i=0}^{s}$ be a decreasing sequence of positive
real numbers with $\alpha_{0}=1$. Let $0<\delta<1$, and
$\widehat{\beta}=(\beta_{i})_{i=2}^{s+2}$ be the corresponding
$BE(\delta,\widehat{\alpha})$ sequence. We say that $\varepsilon>0$ is
$(\delta,j,\widehat{\alpha},d)$-compatible for $j\leq s\leq d-2$, if
$\varepsilon$ satisfies

$\left(\frac{\alpha_{j}-5\varepsilon}{\alpha_{j}-\varepsilon}-2\varepsilon\sum\limits_{t=1}^{j+1}\frac{1}{\alpha_{t-1}}\right)>(1-\delta)\quad\text{and}\quad
2(d+2)^{2}\varepsilon^{\frac{1}{d+1}}\leq\beta_{j+2}\delta.$ (12)

Note that if $\varepsilon$ is $(\delta,j,\widehat{\alpha},d)$-compatible for
$j\geq 1$, then it is $(\delta,(j-1),\widehat{\alpha},d)$-compatible as well.
Note also that the second condition on $\varepsilon$ implies that
$\delta>\varepsilon$ and $\beta_{j+2}>\varepsilon$, $\alpha_{j}>\varepsilon$.

######  Definition 3.8.

We say that $\varepsilon>0$ is $(\delta,d)$-compatible, if it is
$(\delta,d-2,\widehat{\alpha},d)$-compatible for $FE(\delta)$ sequence
$\widehat{\alpha}$. We introduce notation

$EPS_{\delta}(d)=\sup\\{\varepsilon\mid\varepsilon\text{ is
$(\delta,d)$-compatible}\\}.$

In the proposition below we provide a formal version of the discussion at the
beginning of this subsection.

######  Proposition 3.9.

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Fix any
$0<\delta<1$. Let $0\leq j\leq d-2$ and
$\widehat{\alpha}=(\alpha_{i})_{i=0}^{j}$ be a decreasing sequence of positive
real numbers. Consider corresponding $BE(\delta,\widehat{\alpha})$ sequence
$\widehat{\beta}$ and $(\delta,j,\widehat{\alpha},d)$-compatible
$\varepsilon>0$. Assume that the intersection numbers of $X$ satisfy
$c_{j+1}\leq\varepsilon k$ and $b_{i}\geq\alpha_{i}k$ for all $0\leq i\leq j$.
Then one of the following is true.

  1. 1.

$b_{j+1}\geq\varepsilon k$ and $c_{j+2}\geq\varepsilon k$.

  2. 2.

The zero-weight spectral radius $\xi$ of $X$ satisfies

$\xi\leq k(1-(1-\delta)\beta_{j+2}),\quad\text{and}\quad
c_{j+2}\geq\varepsilon k.$

  3. 3.

Let
$\displaystyle{\alpha_{j+1}=(1-\delta)\left(\sum\limits_{t=1}^{\left\lceil\frac{j+2}{2}\right\rceil}\frac{1}{\alpha_{t-1}}+\sum\limits_{t=1}^{\left\lfloor\frac{j+2}{2}\right\rfloor}\frac{1}{\alpha_{t-1}}\right)^{-1}}$,
then $b_{j+1}\geq\alpha_{j+1}k$ and $c_{j+2}\leq\varepsilon k$.

###### Proof.

Case 1. Assume that $c_{j+2}\geq\beta_{j+2}k$.

If $b_{j+1}\geq\varepsilon k$, then statement 1 holds. Thus, suppose that
$b_{j+1}\leq\varepsilon k$. Then we fall into the assumptions of Lemma 3.1
with $i=j+1$. Hence, the zero-weight spectral radius $\xi$ of $X$ satisfies

$\xi\leq
k(1-\min(\alpha_{j},\beta_{j+2})+2(d+2)^{2}\varepsilon^{\frac{1}{d+1}})\leq
k(1-(1-\delta)\beta_{j+2}).$

Note, that by definition, $\beta_{j+2}<\alpha_{j}$, so
$\min(\alpha_{j},\beta_{j+2})=\beta_{j+2}$.

Case 2. Assume $\varepsilon k\leq c_{j+2}\leq\beta_{j+2}k$. Then, by Eq. (11)
and Eq. (12),

$\beta_{j+2}\leq\left(\frac{\alpha_{j}-5\varepsilon}{\alpha_{j}-\varepsilon}\right)\left(\sum\limits_{t=1}^{j+1}\frac{1}{\alpha_{t-1}}\right)^{-1}-2\varepsilon.$

Then, by Lemma 3.3 for $C=\alpha_{j}/\varepsilon$, we get
$b_{j+1}\geq\varepsilon k$.

Case 3. Finally, assume that $c_{j+2}\leq\varepsilon k$. Then, since by Eq.
(12),

$0<\alpha_{j+1}\leq\left(\frac{\alpha_{j}-5\varepsilon}{\alpha_{j}-\varepsilon}-\varepsilon\sum\limits_{t=1}^{j+1}\frac{1}{\alpha_{t-1}}\right)\left(\sum\limits_{t=1}^{\left\lceil\frac{j+2}{2}\right\rceil}\frac{1}{\alpha_{t-1}}+\sum\limits_{t=1}^{\left\lfloor\frac{j+2}{2}\right\rfloor}\frac{1}{\alpha_{t-1}}\right)^{-1},$

Lemma 3.3 for $C\geq\alpha_{j}/\varepsilon$ implies
$b_{j+1}\geq\alpha_{j+1}k$. ∎

As an immediate corollary we get a lower bound on $b_{i}$ for $i\leq t$ if
$c_{t}\leq\varepsilon k$ is small. In the Appendix (Sec. 6) we give explicit
lower bounds for elements of $BE(\delta)$ and $FE(\delta)$ sequences. Another
corollary states that we can bound each eigenvalue of $X$ if $c_{d}$ is small.

######  Corollary 3.10.

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Fix any
$0<\delta<1$. Let $\widehat{\alpha}=(\alpha_{i})_{i=0}^{\infty}$ be the
$FE(\delta)$ sequence and $\varepsilon$ be $(\delta,d)$-compatible.

Assume that $c_{t}\leq\varepsilon k$ for some $t\leq d$, then
$b_{i}\geq\alpha_{i}k$ for any $0\leq i\leq t-1$.

######  Corollary 3.11.

Fix any $0<\delta<1$. Let $X$ be a distance-regular graph of diameter $d\geq
2$. Denote by $\theta_{0}>\theta_{1}>\ldots>\theta_{d}$ all distinct
eigenvalues of $X$. Let $\widehat{\alpha}=(\alpha_{i})_{i=0}^{\infty}$ be the
$FE(\delta)$ sequence and $\varepsilon$ be $(\delta,d)$-compatible.

Assume that $c_{d}\leq\varepsilon k$, then
$\theta_{i}\leq(1-(1-\delta)\alpha_{d-i})k$ for any $1\leq i\leq d$.

###### Proof.

Follows from Corollary 3.10 and Lemma 3.1. ∎

The next theorem is the key ingredient of the proof of our main result on the
motion of distance-regular graphs (Theorem 1.6). It says that for a primitive
distance-regular graph either the minimal distinguishing number is linear, or
the spectral gap is large.

######  Theorem 3.12.

For every $d\geq 2$ there exist $\varepsilon=\varepsilon(d)>0$ and
$\eta=\eta(d)>0$ such that for any distance-regular graph $X$ of diameter $d$
one of the following is true.

  1. 1.

For some $0\leq i\leq d-1$, we have $b_{i}\geq\varepsilon k$ and
$c_{i+1}\geq\varepsilon k$.

  2. 2.

The zero-weight spectral radius of $X$ satisfies $\xi\leq k(1-\eta)$.

###### Proof.

Fix $\delta\in(0,1)$. Let $\widehat{\alpha}=(\alpha_{i})_{i=0}^{\infty}$ be
the $FE(\delta)$ sequence and $\widehat{\beta}=(\beta_{i})_{i=2}^{\infty}$ be
the $BE(\delta)$ sequence and $\varepsilon$ be $(\delta,d)$-compatible. Set
$\eta=(1-\delta)\min(\alpha_{d-1},\beta_{d})$.

Define $c_{d+1}=k$. Let $i$ be the unique index such that $c_{i+1}>\varepsilon
k$, while $c_{i}\leq\varepsilon k$. If $b_{i}\geq\varepsilon k$, then first
statement is true. So assume that $b_{i}\leq\varepsilon k$. By Corollary 3.10,
for every $j\leq i-1$ we have $b_{j}\geq\alpha_{j}k$. Thus, by Proposition
3.9, if $i\leq d-1$, then

$\xi\leq k(1-(1-\delta)\beta_{i+1})\leq
k\left(1-(1-\delta)\beta_{d}\right)\leq k(1-\eta).$

If $i=d$, using that $b_{j}\geq\alpha_{j}k\geq\alpha_{d-1}k$ for $j\leq d-1$,
we get

$\xi\leq k(1-(1-\delta)\alpha_{d-1})\leq k(1-\eta).$

∎

######  Remark 3.13.

In the theorem above one can set

$\displaystyle{\eta=\frac{1}{4}d^{-(1+\log_{2}d)}}\quad\text{ and
}\quad\displaystyle{\varepsilon=200^{-(d+1)}d^{-(d+1)(\log_{2}(d)+3)}}.$

###### Proof.

The proof is based on the explicit bound on the elements of $FE(\delta)$,
$BE(\delta)$ and $EPS_{\delta}$ sequences given in the Appendix (Lemmas 6.1
and 6.2). Note that in Theorem 3.12 $\eta$ is chosen as
$\eta=(1-\delta)\min(\alpha_{d-1},\beta_{d})$. Fix $\delta=1/9$. Using Lemma
6.1 we get

$\displaystyle{\alpha_{d-1}\geq\frac{(1-\delta)^{2}}{2}(d-1)^{-\log_{2}(d-1)}}\quad\text{and}\quad\displaystyle{\beta_{d}\geq\frac{(1-\delta)^{3}}{2(d-1)}(d-2)^{-\log_{2}(d-2)}}.$

Hence, we obtain $\displaystyle{\eta\geq\frac{1}{4}d^{-(1+\log_{2}d)}}$.
Moreover, by Lemma 6.2,
$\displaystyle{\varepsilon=200^{-(d+1)}d^{-(d+1)(\log_{2}(d)+3)}}$ is
$(\delta,d)$-compatible. ∎

Finally, we prove our main theorem on spectral expansion.

######  Theorem 3.14.

For every $d\geq 2$ there exist $\epsilon=\epsilon(d)>0$ and $\eta=\eta(d)>0$
such that the following holds. Let $X$ be a distance-regular graph of diameter
$d$. If $k_{t}\geq(1-\epsilon)n$ for some $t\in[d]$, then the zero-weight
spectral radius of $X$ satisfies $\xi\leq k(1-\eta)$.

###### Proof.

Let $\varepsilon=\varepsilon(d)$ and $\eta=\eta(d)$ be constants provided by
Theorem 3.12. Assume that for some $i$ we have $b_{i}\geq\varepsilon k$ and
$c_{i+1}\geq\varepsilon k$. Let $j$ be the smallest index for which
$c_{j+1}\geq\varepsilon k$, then by monotonicity $b_{j}\geq\varepsilon k$.

If $t\leq j-1$, then
$\displaystyle{k_{t+1}=\frac{b_{t}}{c_{t+1}}k_{t}\geq\frac{b_{j-1}}{c_{j}}k_{t}>\frac{\varepsilon
k}{\varepsilon k}k_{t}=k_{t}}$. Therefore, if $k_{s}$ is maximal, then $s\geq
j$. Observe that $k_{j+1}\geq b_{j}k_{j}/c_{j+1}\geq\varepsilon
kk_{j}/k=\varepsilon k_{j}$. Moreover, if $t\geq j$, then

$k_{t+1}=\frac{b_{t}}{c_{t+1}}k_{t}\leq\frac{k}{\varepsilon
k}k_{t}=\frac{k_{t}}{\varepsilon}.$ (13)

Let $k_{s}$ be the maximal distance degree. Note that $j<d$ as
$b_{j}\geq\varepsilon k$. Thus, if $s=j$, then $k_{s+1}\geq\varepsilon k_{s}$,
else $s>j$ and $k_{s-1}\geq\varepsilon k_{s}$, by Eq. (13). Define
$\epsilon=\epsilon(d)=\varepsilon/(1+\varepsilon)$. Hence,

$k_{s}=n-\sum\limits_{t\neq s}k_{t}<n-\varepsilon k_{s}\quad\Rightarrow\quad
k_{s}<\left(1-\frac{\varepsilon}{1+\varepsilon}\right)n=(1-\epsilon)n.$

Therefore, if $k_{s}\geq(1-\epsilon)n$ for some $s$, then there is no $i$ such
that $b_{i}\geq\varepsilon k$ and $c_{i+1}\geq\varepsilon k$. Hence, by
Theorem 3.12, $\xi\leq k(1-\eta)$. ∎

##  4 Motion of primitive non-geometric distance-regular graphs

Prior to proving our main result on motion of distance-regular graphs (Theorem
1.6) in Section 4.3, we study the minimal distinguishing number of distance-
regular graphs. In the cases, when either there is no dominant distance
(Proposition 4.9), or when the degree of a vertex is linear in the number of
vertices (Proposition 4.7), we show a lower bound on the minimal
distinguishing number that is linear in the number of vertices.

###  4.1 Case of a large vertex degree

In this section we study distance-regular graphs with a large vertex degree.

######  Lemma 4.1.

Let $X$ be a distance-regular graph of diameter $d\geq 2$.

  1. 1.

The parameters of $X$ satisfy $k-\mu\leq 2(k-\lambda)$.

  2. 2.

If $a_{2}\neq 0$, then they also satisfy $k-\lambda\leq 2(k-\mu)$.

###### Proof.

The first statement follows from Observation 3.2 applied to vertices $v$ and
$w$ at distance 2 in $X$ and their common neighbor $u$.

Suppose, that $a_{2}\neq 0$, then for a vertex $u$ there exist two adjacent
vertices $v$ and $w$ at distance 2 from $u$. So, the second statement follows
from Observation 3.2 as well. ∎

Any pair of distinct vertices in a distance-regular graph has $\lambda$, or
$\mu$, or $0$ common neighbors, if distance between them is 1, 2, or at least
3, correspondingly. Therefore, any pair of distinct vertices in a distance-
regular graph is distinguished by at least $2(k-\max(\lambda,\mu))$ vertices.
Combining this with the previous lemma we get the following bound.

######  Lemma 4.2.

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Then any pair of
distinct vertices is distinguished by at least $k-\mu$ vertices.

###### Proof.

Any two vertices $u,v\in X$ are distinguished by at least $|N(u)\bigtriangleup
N(v)|=2(k-|N(u)\cap N(v)|)$ vertices. Thus, by Lemma 4.1, we get
$2(k-\max(\lambda,\mu))\geq k-\mu$. ∎

######  Corollary 4.3.

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Fix some constants
$\gamma,\delta>0$. If $k>n\gamma$ and $\mu\leq(1-\delta)k$, then
$\operatorname{motion}(X)\geq\gamma\delta n$.

###### Proof.

The result follows from the lemma above and Lemma 1.13. ∎

Next, we bound $\mu$ and $\lambda$ away from $k$.

######  Lemma 4.4.

The parameters of a distance-regular graph of diameter $d\geq 2$ satisfy

  1. 1.

$\displaystyle{\min\left(\lambda,\mu\right)<k\cdot\left(1+\min\left(\frac{r-1}{d-1},\left(\frac{r}{d}\right)^{\frac{1}{d-1}}\right)\right)^{-1}}$,

  2. 2.

$\displaystyle{\mu<k\cdot\max\left(\frac{d-1}{r-1},\left(\frac{d}{r}\right)^{\frac{1}{d-1}}\right)}$,

where $\displaystyle{r=\frac{n-1}{k}}$.

###### Proof.

Recall that the sequences $(b_{i})$ and $(c_{i})$ are monotone, so $b_{i}\leq
b_{1}=k-\lambda-1$ and $c_{i+1}\geq\mu$ for $1\leq i\leq d-1$. Thus,
$\displaystyle{k_{i+1}\leq k_{i}\frac{k-\lambda-1}{\mu}}$. Hence,

$n=\sum\limits_{i=0}^{d}k_{i}\leq
1+\sum\limits_{i=0}^{d-1}k\left(\frac{k-\lambda-1}{\mu}\right)^{i}.$

If $k-\lambda-1\leq\mu$, then $\displaystyle{n\leq
1+k+(d-1)k\frac{k-\lambda-1}{\mu}}$, i.e.,

$\displaystyle{\left(\frac{r-1}{d-1}\right)\mu+\lambda+1\leq
k}\quad\Rightarrow\quad\min(\lambda,\mu)<k\left(1+\frac{r-1}{d-1}\right)^{-1}\quad\text{and}\quad\mu<\frac{d-1}{r-1}k.$

Otherwise, we have $\displaystyle{n\leq
1+dk\left(\frac{k-\lambda-1}{\mu}\right)^{d-1}}$, i.e.,

$\displaystyle{\left(\frac{r}{d}\right)^{\frac{1}{d-1}}\mu+\lambda+1\leq
k}\quad\Rightarrow\quad\min(\lambda,\mu)<k\left(1+\left(\frac{r}{d}\right)^{\frac{1}{d-1}}\right)^{-1}\quad\text{and}\quad\mu<\left(\frac{d}{r}\right)^{\frac{1}{d-1}}k.$

∎

######  Corollary 4.5.

Let $X$ be a distance-regular graph of diameter $d\geq 3$. Then

$\min(\lambda,\mu)\leq\frac{d-1}{d}k.$

###### Proof.

Since the diameter $d\geq 3$, we have $\displaystyle{2\leq r=\frac{n-1}{k}}$,
so the result follows from the previous lemma. ∎

######  Lemma 4.6.

Let $X$ be a distance-regular graph of diameter $d\geq 3$ and $a_{2}=0$. Then
$\lambda=0$.

###### Proof.

Fix any vertex $x\in X$. Take $v\in N_{2}(x)$. Denote the set of neighbors of
$v$ in $N_{1}(x)$ by $S(v)$. Then $|S(v)|=\mu$. Observe, that common neighbors
of $v$ and $w\in S(v)$ are in $N_{1}(x)$ or in $N_{2}(x)$. Moreover, the
condition $a_{2}=0$ force them to be in $S(v)$ and there are exactly $\lambda$
such neighbors. At the same time, $w$ has exactly $\lambda$ neighbors in
$N_{1}(x)$, i.e., all neighbors of $w\in S(v)$ within $N_{1}(x)$ lie inside
$S(v)$.

Suppose that $\lambda\neq 0$, then there are two adjacent vertices
$w_{1},w_{2}\in S(v)$. Moreover, for any $w_{3}\in N_{1}(x)$ we have
$\operatorname{dist}(w_{i},w_{3})\leq 2$ for $i=1,2$. And distance could not
be 2 for both, as $a_{2}=0$. Therefore, $w_{3}$ is adjacent to at least one of
$w_{1},w_{2}$. However, by the argument above, any such $w_{3}$ is inside
$S(v)$, i.e., $S(v)=N_{1}(x)$, or in another words $\mu=k$. But it means that
there is no vertex at distance $3$ from $x$, so we get a contradiction with
the assumtion that the diameter is at least $3$. ∎

######  Proposition 4.7.

Let $X$ be a distance-regular graph of diameter $d\geq 3$. Suppose
$k>n\gamma>2$ for some $\gamma>0$. If $X$ is not a bipartite graph, then
$\operatorname{motion}(X)$ is at least $\displaystyle{\frac{\gamma}{3}n}$.

###### Proof.

Suppose, that $\mu\leq\frac{2}{3}k$, then result follows from Corollary 4.3.

If diameter $d\geq 4$, then $\mu\leq\frac{k}{2}$. Indeed, let $v,w$ be
vertices at distance $4$ and let $y$ be a vertex at distance 2 from each of
them. Then $y$ and $v$ have $\mu$ common neighbors and $y$ and $w$ have $\mu$
common neighbors, and they are all distinct. At the same time, they all are
neighbors of $y$, so $\mu\leq k/2$.

If $d=3$ and $a_{2}>0$, then by Lemma 4.1 the inequality
$k-\min(\lambda,\mu)\leq 2(k-\max(\lambda,\mu))$ holds. Hence, any two
vertices $u,v\in X$ are distinguished by at least

$|N(u)\bigtriangleup N(v)|=2(k-|N(u)\cap N(v)|)\geq 2(k-\max(\lambda,\mu))\geq
k-\min(\lambda,\mu)$

vertices. Moreover, Corollary 4.5 for $d=3$ gives
$\min(\lambda,\mu)\leq\frac{2}{3}k$.

Finally, assume $d=3$, $a_{2}=0$ and $\mu>2k/3>1$. Lemma 5.4.1 in [4], states
that for a distance-regular graph of diameter $d\geq 3$, if $\mu>1$, then
either $c_{3}\geq 3\mu/2$, or $c_{3}\geq\mu+b_{2}=k-a_{2}$. Thus, we get that
$c_{3}\geq k$, i.e., $a_{3}=0$. Hence, by Lemma 4.6 the graph $X$ is
bipartite. ∎

###  4.2 Motion of primitive distance-regular graphs

Recall that a distance-regular graph $X$ is primitive if the distance-$i$
graph $X_{i}$ is connected for every $1\leq i\leq d$. Recall also that by
Definition 1.12,

$D_{\min}(X)=\min\limits_{u\neq v\in V}D(u,v).$

It is easy to see, that for a distance-regular graph, the number $D(u,v)$
depends only on the distance $i$ between $u$ and $v$, so one can define
$D(i)=D(u,v)$. We will need the following special case of the inequality
between the distinduishing numbers shown by Babai [1].

######  Lemma 4.8 (Babai [1, Proposition 6.4]).

Let $X$ be a primitive distance-regular graph of diameter $d$. Then for any
distances $1\leq i,j\leq d$ the inequality $D(j)\leq d\cdot D(i)$ holds.

###### Proof.

Since the distance-$i$ graph $X_{i}$ is connected, statement follows from the
triangle inequality $D(u,v)\leq D(u,w)+D(w,v)$ for any vertices $u,v,w$ of
$X$. ∎

######  Proposition 4.9.

Let $X$ be a primitive distance-regular graph of diameter $d\geq 2$ on $n$
vertices. Fix some positive real number $\alpha>0$. Suppose that for some
$1\leq j\leq d-1$ inequalities $b_{j}\geq\alpha k$ and $c_{j+1}\geq\alpha k$
hold. Then

$D_{\min}(X)\geq\frac{\alpha}{d}n.$

###### Proof.

Since the sequence $(b_{i})$ is non-increasing, if $t\leq j$, then
$a_{t}=k-b_{t}-c_{t}\leq(1-\alpha)k$. Similarly, the sequence $(c_{i})$ is
non-decreasing, so if $t>j$, then $a_{t}=k-b_{t}-c_{t}\leq(1-\alpha)k$.

Consider any pair of adjacent vertices $u,v\in X$. If vertex $x$ does not
distinguish $u$ and $v$, then
$\operatorname{dist}(u,x)=\operatorname{dist}(v,x)=t$ for some $1\leq t\leq
d$. Note, that for a given $t$ there are $p^{1}_{t,t}$ such vertices $x$ and

$p^{1}_{t,t}=p^{t}_{t,1}\frac{k_{t}}{k}=k_{t}\frac{a_{t}}{k}\leq(1-\alpha)k_{t}.$

Clearly, $\sum\limits_{i=1}^{d}k_{i}=n-1$. Hence, any pair of adjacent
vertices is distinguished by at least

$n-\sum\limits_{t=1}^{d}(1-\alpha)k_{t}\geq n-(1-\alpha)n=\alpha n$

vertices. Finally, the result follows from Lemma 4.8. ∎

###  4.3 Reduction to the geometric graphs

In the theorem below we prove our main result on the motion of distance-
regular graphs.

######  Theorem 4.10.

For any $d\geq 3$ there exist $\gamma_{d}>0$ and a positive integer $m_{d}$,
such that for any primitive distance-regular graph $X$ of diameter $d$ with
$n$ vertices either

$\operatorname{motion}(X)\geq\gamma_{d}n,$

or $X$ is geometric with smallest eigenvalue at least $-m_{d}$.

Furthermore, one can set $\displaystyle{m_{d}=\left\lfloor
5d^{\log_{2}d+1}\right\rfloor}$.

###### Proof.

By Theorem 3.12, there exist constants $\varepsilon>0$ and $\eta>0$, which
depend only on $d$, such that

  * •

either $b_{i}\geq\varepsilon k$ and $c_{i+1}\geq\varepsilon k$,

  * •

or the zero-weight spectral radius of $X$ satisfies $\xi\leq k(1-\eta)$.

In the first case, by Proposition 4.9, we obtain

$\operatorname{motion}(X)\geq\frac{\varepsilon}{d}n.$

Hence, assume that $\xi\leq k(1-\eta)$. For convenience, we additionally
assume $\eta\leq 1/7$.

Case 1. Suppose that $\mu>\eta^{3}k$. Then, by Lemma 4.4,
$n\leq\max\left(d,2\left(\eta^{-3}d\right)^{d-1}\right)k+1$. Therefore, by
Proposition 4.7,

$\operatorname{motion}(X)\geq\frac{1}{7}\left(\eta^{3}d^{-1}\right)^{d-1}n.$

Case 2. Suppose that $\displaystyle{\lambda<\frac{9}{10}\eta k}$ and
$\mu\leq\eta^{3}k$. Then any pair of distinct vertices in $X$ has at most
$q(X)=\max(\lambda,\mu)\leq 9\eta k/10$ common neighbors. Therefore, by Lemma
1.14,

$\operatorname{motion}(X)\geq\frac{\eta}{10}n.$

Case 3. Suppose that $\displaystyle{\lambda\geq\frac{9}{10}\eta k}$ and
$\mu\leq\eta^{3}k$. Let $m$ be the integer that satisfies

$(m-1)(\lambda+1)<k\leq m(\lambda+1).$

The assumption on $\lambda$ implies
$\displaystyle{m-1\leq\frac{10}{9}\eta^{-1}}$. We additionally assumed
$\eta\leq 1/7$, so

$\frac{1}{2}m(m+1)\mu\leq\frac{1}{2}\left(\frac{10}{9}\eta^{-1}+1\right)\left(\frac{10}{9}\eta^{-1}+2\right)\mu\leq\frac{9}{10}\eta^{-2}\mu\leq\frac{9}{10}\eta
k\leq\lambda.$

Thus, by Corollary 2.10, the graph $X$ is a geometric distance-regular graph
with smallest eigenvalue $-m$.

Finally, we note that we can take
$\displaystyle{m_{d}=\left\lfloor\frac{10}{9}\eta^{-1}+1\right\rfloor}$ and

$\gamma_{d}=\min\left(\frac{\varepsilon}{d},\frac{1}{7}\left(\eta^{3}d^{-1}\right)^{d-1},\frac{\eta}{10}\right).$

Furthermore, by Remark 3.13, $m_{d}$ can be taken as
$\displaystyle{m_{d}=\left\lfloor 5d^{\log_{2}d+1}\right\rfloor}$.

######  Remark 4.11.

A bit more careful computations show that one can in fact set

$m_{d}=\lceil\max\left(2(d-1)(d-2)^{\log_{2}(d-2)},2(d-1)^{\log_{2}(d-1)}\right)\rceil.$

In particular, for $d=3$ this estimate gives upper bound $m_{d}\leq 4$.

∎

##  5 Imprimitive case

In this section we analyze the motion of imprimitive distance-regular graphs.
We start by establishing a version of the Spectral tool in the bipartite case.
Later we show that the motion of the antipodal graphs is controlled by the
motion of their folded graphs. After that we prove motion lower bounds for
bipartite graphs and for imprimitive graphs of diameter 3 and 4. A separate
analysis for an imprimitive graph of diameter 3 and 4 is needed due to the
fact that its folded or halved graph may be a complete graph, and in this case
different arguments are required.

###  5.1 Spectral tool for bipartite graphs

To prove an analog of the Spectral tool (Lemma 1.14) for the case of bipartite
graphs we need a version of the Expander Mixing Lemma for regular bipartite
graphs.

######  Theorem 5.1 (Expander Mixing Lemma: bipartite version, Haemers [14,
Theorem 5.1]).

Let $X$ be a biregular bipartite graph with parts $U$ and $W$ of sizes $n_{U}$
and $n_{W}$. Denote, by $d_{U}$ and $d_{W}$ the degrees of the vertices in
parts $U$ and $W$, respectively. Let $\lambda_{2}$ be the second largest
eigenvalue of the adjacency matrix $A$ of $X$. Then for any $S\subseteq U$,
$T\subseteq W$

$\left(E(S,T)\frac{n_{U}}{|S|}-|T|d_{W}\right)\left(E(S,T)\frac{n_{W}}{|T|}-|S|d_{U}\right)\leq\lambda_{2}^{2}(n_{U}-|S|)(n_{W}-|T|),$

which, using $d_{U}n_{U}=d_{W}n_{W}=E(U,W)$, implies

$\left||E(S,T)|-\frac{d_{W}|S||T|}{n_{U}}\right|\leq|\lambda_{2}|\sqrt{|S||T|},$

where $E(S,T)$ is the set of edges between $S$ and $T$ in $X$.

Next lemma is an analog of Lemma 1.14 for bipartite graphs.

######  Lemma 5.2.

Let $X$ be a $k$-regular bipartite graph with parts $U$ and $W$ of size $n/2$
each. Let $\lambda_{2}$ be the second largest eigenvalue of $A$. Moreover,
suppose that any pair of distinct vertices in $X$ have at most $q$ common
neighbors. Then

$\operatorname{motion}(X)\geq\frac{k-|\lambda_{2}|-q}{2k}n.$

###### Proof.

Take any non-trivial automorphism $\sigma$ of $X$. Consider $S_{1}\subseteq U$
and $S_{2}\subseteq W$, such that $S_{1}\cup
S_{2}=\operatorname{supp}(\sigma)=\\{x\in X|x^{\sigma}\neq x\\}$ be the
support of $\sigma$. Without lost of generality, we may assume that
$|S_{1}|\geq|S_{2}|$. Denote $S=S_{1}$ and let $T\subset W$ be a set which
satisfies $S_{2}\subseteq T$ and $|T|=|S|$. By the Expander Mixing Lemma we
get

$\frac{|E(S,T)|}{|S|}\leq|\lambda_{2}|+k\frac{2|S|}{n}.$

Hence, there exists a vertex $x$ in $S$ which has at most
$\displaystyle{|\lambda_{2}|+k\frac{2|S|}{n}}$ neighbors in $T$. Thus, $x$ has
at least $\displaystyle{k-\left(|\lambda_{2}|+k\frac{2|S|}{n}\right)}$
neighbors in $W\setminus T$, and they all are fixed by $\sigma$. Therefore,
they all are common neighbors of $x$ and $x^{\sigma}\neq x$. We get the
inequality $\displaystyle{q\geq
k-\left(|\lambda_{2}|+k\frac{2|S|}{n}\right)}$, which is equivalent to
$\displaystyle{\left(\frac{|\lambda_{2}|+q}{k}\right)\frac{n}{2}\geq\frac{n}{2}-|S|}$.
By the definition of $S$ and $T$ the number of fixed points of $\sigma$ is at
most

$n-|S_{1}|-|S_{2}|\leq
n-|S|\leq\left(\frac{1}{2}+\frac{|\lambda_{2}|+q}{2k}\right)n.$

∎

###  5.2 Reduction results

We show that the motion of an imprimitive distance-regular graph is controlled
by the motion of its folded or halved graph.

######  Proposition 5.3.

Let $X$ be an antipodal distance-regular graph of diameter $d\geq 3$ on $n$
vertices and $\widetilde{X}$ be its folded graph on $\widetilde{n}$ vertices.
Suppose $\operatorname{motion}(\widetilde{X})\geq\alpha\widetilde{n}$. Then
$\operatorname{motion}(X)\geq\alpha n$.

###### Proof.

Assume that $X$ is an $r$-cover of $\widetilde{X}$ and let
$\phi:X\rightarrow\widetilde{X}$ be a cover map. Let $\sigma$ be an
automorphism of $X$. Note that by the definition of antipodal and folded
graphs, vertices of $\widetilde{X}$ are maximal cliques (connected components)
of $X_{d}$. Since $\sigma$ is an automorphism of $X$, it preserves the
relation of being at distance $d$, so $\sigma$ respects preimages of $\phi$.
Hence, it induces an automorphism $\widetilde{\sigma}$ of $\widetilde{X}$
defined as $\widetilde{\sigma}(x)=\phi(\sigma(\phi^{-1}(x)))$.

If $\widetilde{\sigma}$ is non-identity, then by the assumptions of the lemma,
the degree of $\widetilde{\sigma}$ is at least $\alpha\widetilde{n}$. Suppose
that $x\in V(\widetilde{X})$ is not fixed by $\widetilde{\sigma}$, then
$\phi^{-1}(x)$ is disjoint from $\sigma(\phi^{-1}(x))$. Thus, all vertices in
$\phi^{-1}(x)$ are not fixed by $\sigma$. Therefore, the degree of $\sigma$ is
at least $r\cdot\alpha\widetilde{n}=\alpha n$.

Assume that $\widetilde{\sigma}$ is the identity map. Suppose that $\sigma$ is
a non-identity map. Let $x$ be a vertex such that $\sigma(x)\neq x$ and let
$y$ be adjacent to $x$. Note that $\sigma(x)$ is at distance $d$ from $x$ as
$\widetilde{\sigma}$ is the identity map. Thus $\sigma(y)\neq y$, as otherwise
$y$ is adjacent to $\sigma(x)$ and we get a contradiction with the assumption
$d\geq 3$. Therefore, any vertex of $X$ which is adjacent to a vertex not
fixed by $\sigma$ is itself not fixed by $\sigma$. Since $X$ is connected, we
get that the degree of $\sigma$ is $n$ in this case. ∎

######  Remark 5.4.

If $X$ is antipodal of diameter $d=2$, then $X$ is a complete multipartite
graph and its folded graph is a complete graph. The motion of $X$ is 2 in this
case, so statement of the proposition above does not hold.

######  Proposition 5.5.

Let $X$ be a bipartite distance-regular graph on $n$ vertices and let $X^{+}$
and $X^{-}$ be its halved graphs. Then
$\operatorname{motion}(X)\geq\min(\operatorname{motion}(X^{+}),\operatorname{motion}(X^{-}))$.

###### Proof.

By the definition of the halved graphs, $X$ is bipartite with parts $V(X^{+})$
and $V(X^{-})$ of the same size $n/2$. Let $\sigma$ be a non-identity
automorphism of $X$. If $\sigma$ maps $X^{+}$ to $X^{-}$, then the degree of
$\sigma$ is $n$. Else $\sigma$ induces automorphisms $\sigma_{+}$ and
$\sigma_{-}$ of $X^{+}$ and $X^{-}$, respectively. Since $\sigma$ is non-
identity, at least one of $\sigma_{+}$ and $\sigma_{-}$ is non-identity.
Without lost of generality, assume $\sigma^{+}$ is non-identity. Then its
degree is at least $\operatorname{motion}(X^{+})$. ∎

###  5.3 Bipartite graphs of diameter at least 4

######  Theorem 5.6.

Let $X$ be a bipartite graph of diameter $d\geq 4$ on $n$ vertices. If a
halved graph of $X$ is primitive, then

$\operatorname{motion}(X)\geq\gamma_{d}^{\prime}n,\quad\text{where
}\gamma_{d}^{\prime}=(2d)^{-2d-5}.$

###### Proof.

Let $\iota(X)=\\{b_{0},b_{1},\ldots,b_{d-1};c_{1},c_{2},\ldots,c_{d}\\}$ be
the intersection array of $X$. Denote by $Y$ a halved graph of $X$. By
Proposition 2.13, the intersection array of $Y$ is

$\iota(Y)=\left\\{\frac{b_{0}b_{1}}{\mu},\frac{b_{2}b_{3}}{\mu},\ldots,\frac{b_{2t-2}b_{2t-1}}{\mu};\frac{c_{1}c_{2}}{\mu},\frac{c_{3}c_{4}}{\mu},\ldots,\frac{c_{2t-1}c_{2t}}{\mu}\right\\},$

where $d\in\\{2t,2t+1\\}$. Note that since $X$ is bipartite, $b_{i}+c_{i}=k$,
so in particular the degree of $Y$ is equal

$\widehat{k}=\frac{b_{0}b_{1}}{\mu}=\frac{k(k-c_{1})}{\mu}=\frac{k(k-1)}{\mu}.$

For convenience, define $c_{i}=k$ for any $i>d$. Take $1\leq j\leq t$ such
that $c_{2j-1}\leq\varepsilon k$ and $c_{2j+1}\geq\varepsilon k$, where
$\varepsilon=\left(2d\right)^{-d-2}$. Then for any $i\leq j$

$\frac{c_{2i-1}c_{2i}}{\mu}\leq\frac{c_{2j-1}c_{2j}}{\mu}\leq
2\varepsilon\widehat{k}\quad\text{and}\quad\frac{b_{2i-2}b_{2i-1}}{\mu}\geq\frac{b_{2j-1}^{2}}{\mu}=\frac{(k-c_{2t-1})^{2}}{\mu}\geq(1-\varepsilon)^{2}\widehat{k}.$
(14)

Case 1. Assume that $j=1$ and $b_{2j+1}\leq\varepsilon k$. Then

$\lambda(Y)=\widehat{k}-\frac{b_{2}b_{3}}{\mu}-1\geq\widehat{k}-2\varepsilon\widehat{k}.$

By Lemma 4.1 we obtain that
$\mu(Y)\geq\widehat{k}-4\varepsilon\widehat{k}>\widehat{k}/2$. By Lemma 4.4,
we get $|V(Y)|<t2^{t}k$. Therefore, as halved graph is not bipartite, by
Proposition 4.7, we obtain

$\operatorname{motion}(Y)\geq\frac{1}{3t2^{t}}|V(Y)|.$

Case 2. Assume that $j\geq 2$ and $b_{2j+1}\leq\varepsilon k$. Then, for any
$i\geq j+1$

$\frac{c_{2i-1}c_{2i}}{\mu}\geq\frac{c_{2j+1}^{2}}{\mu}=\frac{(k-b_{2j+1})^{2}}{\mu}\geq(1-\varepsilon)^{2}\widehat{k}.$
(15)

Hence, combining Eq. (14) and Eq. (15), by Lemma 3.1, the zero-weight spectral
radius of $Y$ satisfies

$\xi(Y)\leq\left(1-(1-\varepsilon)^{2}+2(t+2)^{2}\varepsilon^{\frac{1}{t+1}}\right)\widehat{k}.$

Since $j\geq 2$, using Eq. (14), we can estimate

$\lambda(Y)\leq\widehat{k}-\frac{b_{2}b_{3}}{\mu}\leq\widehat{k}-(1-\varepsilon)^{2}\widehat{k}\leq
2\varepsilon\widehat{k}\quad\text{and}\quad\mu(Y)=\frac{c_{3}c_{4}}{\mu}\leq
2\varepsilon\widehat{k}.$

Therefore, by Lemma 1.14 and the choice of $\varepsilon$,

$\operatorname{motion}(Y)\geq\left((1-\varepsilon)^{2}-2(t+2)^{2}\varepsilon^{\frac{1}{t+1}}-2\varepsilon\right)|V(Y)|\geq\frac{1}{3}|V(Y)|.$

Case 3. Assume that $b_{2j+1}>\varepsilon k$. Then

$\frac{c_{2j+1}c_{2j+2}}{\mu}\geq\frac{c_{2j+1}^{2}}{\mu}\geq\varepsilon^{2}\widehat{k}\quad\text{and}\quad\frac{b_{2j}b_{2j+1}}{\mu}\geq\frac{b_{2j+1}^{2}}{\mu}\geq\varepsilon^{2}\widehat{k}.$

Since $Y$ is primitive, by Proposition 4.9,

$\operatorname{motion}(Y)\geq\frac{\varepsilon^{2}}{t}|V(Y)|.$

Finally, since $|V(Y)|=n/2$, the inequality
$\operatorname{motion}(X)\geq\gamma n$ follows from Proposition 5.5 for
$\displaystyle{\gamma=\min\left(\frac{1}{6t2^{t}},\frac{1}{6},\frac{(2d)^{-2d-4}}{2t}\right)\geq(2d)^{-2d-5}}$.
∎

###  5.4 Bipartite antipodal graphs of diameter 4

######  Fact 5.7 ([4], p. 425).

Let $X$ be a bipartite antipodal distance-regular graph of diameter $d=4$.
Then there exist $\mu$ and $m$ such that the number of vertices is
$n=2m^{2}\mu$, the degree is $k=m\mu$, and the intersection array is

$\iota(X)=\\{m\mu,m\mu-1,(m-1)\mu,1;1,\mu,m\mu-1,m\mu\\}.$

Moreover, the spectrum of $X$ consists of $k$ and $-k$ of multiplicity 1,
$\sqrt{k}$ and $-\sqrt{k}$ of multiplicity $(m-1)k$, and $0$ of multiplicity
$(2k-2)$.

######  Proposition 5.8.

Let $X$ be a bipartite antipodal distance-regular graph of diameter $d=4$ on
$n$ vertices. Then

$\operatorname{motion}(X)\geq 0.15n.$

###### Proof.

Consider a pair of distinct vertices $u,v$ of $X$. If
$\operatorname{dist}(u,v)>2$, then they are distinguished by at least
$D(u,v)\geq 2k$ vertices. Since $X$ is bipartite, if
$\operatorname{dist}(u,v)=1$, then $D(u,v)\geq 2k$ as well. Clearly, for $u,v$
at distance 2, we have $D(u,v)\geq 2(k-\mu)$. Thus $D_{\min}(X)\geq 2(k-\mu)$.

By Fact 5.7, $k=m\mu$ and $n=2m^{2}\mu$ for some integer $m\geq 2$. Therefore,
by Lemma 1.13,

$\operatorname{motion}(X)\geq D_{\min}(X)\geq\frac{m-1}{m^{2}}n.$ (16)

At the same time, by Fact 5.7, we know that the second largest eigenvalue of
$X$ equals $\sqrt{k}$. Then, by Lemma 5.2,

$\operatorname{motion}(X)\geq\frac{k-\sqrt{k}-\mu}{2k}n=\frac{m\mu-\sqrt{m\mu}-\mu}{2m\mu}n\geq\frac{m-\sqrt{m}-1}{2m}n.$
(17)

Using the bound given by Eq. (16) for $m\leq 4$, and the bound given by Eq.
(17) for $m>4$, we get the desired inequality. ∎

###  5.5 Bipartite graphs of diameter 3

######  Fact 5.9 ([4], p. 432).

Let $X$ be a bipartite distance-regular graph of diameter $3$. Then the number
of vertices of $X$ is $n=2+2k(k-1)/\mu$ and $X$ has the intersection array

$\iota(X)=\\{k,k-1,k-\mu;1,\mu,k\\}.$

The eigenvalues of $X$ are $k$, $-k$ with multiplicity 1, and
$\pm\sqrt{k-\mu}$ with multiplicity $\frac{n}{2}-1$.

######  Definition 5.10.

A graph $X$ is called a cocktail-party graph if it is obtained from a regular
complete bipartite graph by deleting one perfect matching.

######  Proposition 5.11.

Let $X$ be a bipartite distance-regular graph of diameter $3$. If $X$ is not a
cocktail-party graph, then

$\operatorname{motion}(X)\geq\frac{1}{12}n.$

###### Proof.

Denote the parts of the bipartite graph $X$ by $U$ and $W$. Let $Y=X_{3}$ be a
distance-3 graph of $X$. We consider 2 cases.

Case 1. Suppose that $Y$ is disconnected. Then there exists a pair of vertices
$u,v$ in one of the parts, so that $u$ and $v$ lie in different connected
components of $Y$. Clearly, $\operatorname{dist}(u,v)=2$, so $p^{2}_{3,3}=0$.
Hence, $k_{3}=1$, and the pairs of vertices at distance $3$ form a perfect
matching. Therefore, $X$ is a regular complete bipartite graph with one
perfect matching deleted.

Case 2. $Y$ is connected and so is itself a distance-regular graph of diameter
$3$. Note, that $k+k_{3}=n/2$, so if necessary, by passing to $Y$, we may
assume that the degree of $X$ satisfies $k\leq n/4$. Lemma 4.4 implies
$\mu<\frac{\sqrt{3}}{2}k$. The graph $X$ is bipartite, so $\lambda=0$ and by
Lemma 1.13,

$\operatorname{motion}(X)\geq D_{\min}(X)\geq
2(k-\mu)\geq(2-\sqrt{3})k>\frac{1}{4}k.$ (18)

If $\mu\geq 2k/3$, then by Fact 5.9, $n\leq 3k$, so
$\operatorname{motion}(X)\geq n/12$. If $k/4\leq\mu<2k/3$, then $n\leq 8k$,
and Eq. (18) implies

$\operatorname{motion}(X)\geq 2(k-\mu)\geq\frac{2}{3}k\geq\frac{n}{12}.$

Finally, assume $\mu\leq k/4$. By Fact 5.9, the second largest eigenvalue is
$\lambda_{2}=\sqrt{k-\mu}$. Using that $k\geq 4\mu\geq 4$ and the function
$x-\sqrt{x}$ is increasing for $x\geq 1$, by Lemma 5.2,

$\operatorname{motion}(X)\geq\frac{k-\mu-\sqrt{k-\mu}}{2k}n\geq\frac{3k-2\sqrt{3k}}{8k}n\geq\frac{3-\sqrt{3}}{8}n\geq\frac{n}{7}.$

∎

###  5.6 Antipodal graphs of diameter 3

######  Fact 5.12 (see [4, p. 431]).

Let $X$ be an antipodal distance-regular graph of diameter $d=3$ on $n$
vertices. There exist integers $m\geq 2$, $r\geq 2$ and $t\geq 1$ such that
the following holds.

  * •

If $\lambda\neq\mu$, then $n=r(k+1)$, $k=mt$, $\mu=(m-1)(t+1)/r$,
$\lambda=\mu+t-m$. Moreover, the distinct eigenvalues of $X$ are $k$, $t$,
$-1$ and $-m$, with multiplicities $1$, $m(r-1)(k+1)/(m+t)$, $k$,
$t(r-1)(k+1)/(m+t)$, respectively.

  * •

If $\lambda=\mu$, then $n=r(k+1)$, $k=r\mu+1$. The distinct eigenvalues of $X$
are $k$, $\sqrt{k}$, $-1$ and $-\sqrt{k}$.

######  Proposition 5.13.

Let $X$ be an antipodal distance-regular graph of diameter $d=3$ on $n$
vertices. If $X$ is not a cocktail-party graph, then

$\operatorname{motion}(X)\geq\frac{1}{13}n.$

###### Proof.

Case 1. Suppose that $\lambda\neq\mu$ and $t>m$. Then $\lambda>\mu$ and so

$k-q(X)-\xi(X)=tm-\frac{(m-1)(t+1)}{r}-t+m-t\geq
t\left(m-2-\frac{m-1}{r}\right).$

If $m\geq 3$ and $r\geq 3$, then

$k-q(X)-\xi(X)\geq
t\left(m-2-\frac{m-1}{3}\right)=t\left(\frac{2}{3}m-\frac{5}{3}\right)\geq\frac{1}{9}tm=\frac{k}{9}.$

If $r=2$ and $m\geq 4$, then

$k-q(X)-\xi(X)\geq
t\left(m-2-\frac{m-1}{2}\right)=t\left(\frac{1}{2}m-\frac{3}{2}\right)\geq\frac{1}{8}tm=\frac{k}{8}.$

Therefore, in both of these situations, by Lemma 1.14,

$\operatorname{motion}(X)\geq\frac{n}{9}.$

If $r=2$ and $m=3$, then $n=6t+2$, $k=3t$, $\mu=t+1$ and $\lambda=2t-2$. Note
that by Lemma 1.13, in this case

$\operatorname{motion}(X)\geq
D_{\min}(X)\geq\min(2(k-\lambda),2(k-\mu))=2(t+2)\geq\frac{n}{3}.$

Finally, if $m=2$, then $k=2t$, $\mu=(t+1)/r$ is integer, and the multiplicity
of $t$ as an eigenvalue is an integer number equal $2(r-1)(2t+1)/(t+2)$. Thus
we may conclude that

$(t+2)\mid 2(r-1)(2t+4-3)\quad\Rightarrow\quad(t+2)\mid
6(r-1)\quad\Rightarrow$ $\Rightarrow\quad(t+2)\mid
6\left(\frac{t+1}{\mu}-1\right)\quad\Rightarrow\quad(t+2)\mid
6(t+1-\mu)\quad\Rightarrow\quad(t+2)\mid 6(\mu+1).$

Hence, in particular,

$(t+2)\leq 6\left(\frac{t+1}{r}+1\right),\quad\text{so}\quad(t-4)r\leq 6t+6.$

If $t\geq 10$, we get $r\leq 11$. If $t<10$, then $r=(t+1)/\mu\leq t+1<11$.
Therefore, by Lemma 1.13,

$\operatorname{motion}(X)\geq D_{\min}(X)\geq
2(k-\lambda)=2\left(t+2-\frac{t+1}{r}\right)\geq\frac{r-1}{r^{2}}n\geq\frac{n}{13}.$

Case 2. Suppose that $\lambda\neq\mu$ and $m>t$. Then $\lambda<\mu$ and so

$k-q(X)-\xi(X)=tm-\frac{(m-1)(t+1)}{r}-m\geq m\left(t-1-\frac{t+1}{r}\right).$

If $r\geq 4$ and $t\geq 2$, we get

$k-q(X)-\xi(X)\geq
m\left(t-1-\frac{t+1}{4}\right)=m\left(\frac{3}{4}t-\frac{5}{4}\right)\geq\frac{1}{8}mt=\frac{k}{8}.$

Therefore, by Lemma 1.14,

$\operatorname{motion}(X)\geq\frac{n}{8}.$

If $r\leq 4$ and $t\geq 2$, then $n\leq 4(k+1)$, and by Lemma 1.13,

$\operatorname{motion}(X)\geq D_{\min}(X)\geq\min(2(k-\lambda),2(k-\mu))\geq$
$\geq 2\left(mt-\frac{(m-1)(t+1)}{2}\right)\geq
2\left(mt-\frac{m(t+1)}{2}\right)\geq
2\left(mt-\frac{3mt}{4}\right)=\frac{k}{2}\geq\frac{n}{12}.$

Finally, if $t=1$, then $\lambda\geq 0$ implies $r=2$. Hence, we obtain
$n=2(k+1)$, $\mu=k-1$ and $\lambda=0$. It follows that $X$ is a cocktail-party
graph in this case.

Case 3. Assume $\lambda=\mu$. Then by Fact 5.12, $n=r(k+1)$, $k=r\mu+1$ and
$\xi(X)=\sqrt{k}$. By Lemma 1.14, for $r\geq 4$

$\operatorname{motion}(X)\geq\frac{k-\mu-\sqrt{k}}{k}n\geq\frac{(r-1)\mu+1-\mu\sqrt{r+1}}{r\mu+1}n\geq\frac{r-\sqrt{r+1}-1}{r}n\geq\frac{n}{6}.$

At the same time, since $\lambda=\mu$, for $2\leq r\leq 3$, by Lemma 1.13,

$\operatorname{motion}(X)\geq D_{\min}(X)\geq
2(k-\mu)\geq\frac{r-1}{r}k\geq\frac{2(r-1)}{3r^{2}}n\geq\frac{4}{27}n.$

∎

###  5.7 Collecting together the analysis for imprimitive graphs

In this section we collect analysis of the imprimitive case into Theorem 5.15.
In the proof we use the following result about antipodal covers proved by Van
Bon and Brouwer [27].

######  Theorem 5.14 (Van Bon, Brouwer).

  1. 1.

The Hamming graph $H(d,s)$ has no distance-regular antipodal covers, except
for $H(2,2)$, the quadrangle, which is covered by the octagon.

  2. 2.

The Johnson graph $J(s,d)$ has no distance-regular antipodal covers for $d\geq
2$.

  3. 3.

The complement $\overline{J(s,2)}$ has no distance-regular antipodal covers
for $s\geq 8$.

  4. 4.

The complement $\overline{H(2,s)}$ has no distance-regular antipodal covers
for $s\geq 4$.

######  Theorem 5.15.

Assume Conjecture 1.5 is true. Then for any $d\geq 3$ there exists
$\widetilde{\gamma}_{d}>0$, such that for any distance-regular graph $X$ of
diameter $d$ on $n$ vertices either

$\operatorname{motion}(X)\geq\widetilde{\gamma}_{d}n,$

or $X$ is a Johnson graph $J(s,d)$, or a Hamming graph $H(d,s)$, or a
cocktail-party graph.

###### Proof.

Assume that Conjecture 1.5 is true and $\gamma_{d}>0$ is a constant provided
by the conjecture. If $X$ is primitive, then there is nothing to prove. If $X$
is bipartite and not antipodal of diameter $d\geq 4$, then by Theorem 5.6
$\operatorname{motion}(X)\geq\gamma_{d}^{\prime}n$. If $X$ is bipartite
(possibly antipodal) graph of diameter $d=3$, then by Theorem 5.11, $X$ is
either a cocktail-party graph, or $\operatorname{motion}(X)\geq n/12$.

If $X$ is bipartite and antipodal of even diameter $d\geq 6$, then by
Proposition 2.14, folded graph $\widetilde{X}$ is bipartite (and not
antipodal) of diameter $d/2$. So

$\operatorname{motion}(\widetilde{X})\geq\min\left(\gamma_{d/2}^{\prime},\frac{1}{12}\right)|V(\widetilde{X})|$

(we use that cocktail-party graph is antipodal). Therefore, by Proposition
5.3,

$\operatorname{motion}(X)\geq\min\left(\gamma_{d/2}^{\prime},\frac{1}{12}\right)n.$

In the case when $X$ is bipartite and antipodal of diameter $d=4$, by
Proposition 5.8,

$\operatorname{motion}(X)\geq 0.15n.$

We still need to analyze the cases when $X$ is antipodal, but not bipartite,
or when $X$ is antipodal of odd diameter. By Proposition 2.14, in these cases,
folded graph of $X$ is primitive. If diameter of $X$ is 3, then by Proposition
5.13, $\operatorname{motion}(X)\geq n/13$. If diameter of $X$ is $d\geq 4$,
then by Proposition 2.14, folded graph $\widetilde{X}$ is primitive of
diameter $\displaystyle{\widetilde{d}=\left\lfloor d/2\right\rfloor\geq 2}$.
Since $\widetilde{X}$ is primitive, $\widetilde{X}$ is not the complement to a
disjoint union of cliques. If $\widetilde{X}$ has at least $29$ vertices, and
$X$ is not a Johnson graph $J(s,d)$, the Hamming graph $H(d,s)$, or the
complement of $J(s,2)$ or $H(2,s)$, then by Theorem 1.4 and the assumption
that Conjecture 1.5 is true,

$\operatorname{motion}(\widetilde{X})\geq\min\left(\gamma_{\widetilde{d}},\frac{1}{8}\right)|V(\widetilde{X})|.$

Therefore, in this case, by Theorem 5.3,

$\operatorname{motion}(X)\geq\min\left(\gamma_{\widetilde{d}},\frac{1}{8}\right)n.$

Finally we note, that by Theorem 5.14, if $Y$ is the Johnson graph $J(s,d)$,
the Hamming graph $H(d,s)$, or the complement of $J(s,2)$ or $H(2,s)$ and $Y$
has at least $29$ vertices, then $Y$ has no antipodal covers. In the case when
$Y$ has at most $28$ vertex, $\operatorname{motion}(Y)\geq|Y|/14$. So by
Proposition 5.3, if the graph $X$ on $n$ vertices is a distance-regular
antipodal cover of such $Y$, then $\operatorname{motion}(X)\geq n/14$.

Taking
$\displaystyle{\widetilde{\gamma}=\min\left(\gamma_{d},\gamma_{d}^{\prime},\gamma_{d/2}^{\prime},\gamma_{\lfloor
d/2\rfloor},\frac{1}{14}\right)}$ we get the desired statement. ∎

##  6 Appendix: Explicit bounds for $FE(\delta)$ and $BE(\delta)$

In this section we compute expilicit lower bounds for $BE(\delta)$,
$FE(\delta)$ and $EPS_{\delta}$ sequences.

######  Lemma 6.1.

Fix $0<\delta\leq\frac{1}{9}$. Let $(\alpha_{i})_{i=0}^{\infty}$ be the
$FE(\delta)$ sequence and the corresponding $BE(\delta)$ sequence
$(\beta_{i})_{i=2}^{\infty}$. Then for $j\geq 1$

$\alpha_{j}\geq\frac{(1-\delta)^{2}}{2}j^{-\log_{2}(j)}\quad\text{and}\quad\beta_{j+2}\geq\frac{(1-\delta)^{3}}{2(j+1)}j^{-\log_{2}(j)}.$

###### Proof.

We prove the statement of the lemma by induction. Indeed, for $j=1,2$ we have
$\alpha_{1}=\frac{1-\delta}{2}$ and $\alpha_{2}\geq\frac{(1-\delta)^{2}}{4}$,
so the inequality is true. For $j\geq 2$, we have

$\alpha_{j+1}=(1-\delta)\left(\sum\limits_{t=1}^{\lceil\frac{j+2}{2}\rceil}\frac{1}{\alpha_{t-1}}+\sum\limits_{t=1}^{\lfloor\frac{j+2}{2}\rfloor}\frac{1}{\alpha_{t-1}}\right)^{-1}\geq\frac{(1-\delta)}{j+2}\alpha_{\lceil\frac{j}{2}\rceil}\geq$
$\geq\frac{(1-\delta)^{3}}{2(j+2)}\left(\frac{j+1}{2}\right)^{-\log_{2}\left(\frac{j+1}{2}\right)}=\frac{(1-\delta)^{3}2^{\log_{2}\left(\frac{j+1}{2}\right)}}{2(j+2)}(j+1)^{-\log_{2}(j+1)+1}=$
$=\frac{(1-\delta)(j+1)^{2}}{2(j+2)}\frac{(1-\delta)^{2}}{2}(j+1)^{-\log_{2}(j+1)}\geq\frac{(1-\delta)^{2}}{2}(j+1)^{-\log_{2}(j+1)}.$

Thus,

$\beta_{j+2}=(1-\delta)\left(\sum\limits_{t=0}^{j}\frac{1}{\alpha_{t}}\right)^{-1}\geq\frac{1-\delta}{j+1}\alpha_{j}\geq\frac{(1-\delta)^{3}}{2(j+1)}j^{-\log_{2}(j)}.$

∎

######  Lemma 6.2.

Let $0<\delta\leq 1/9$ and $d\geq 3$. Then

$EPS_{\delta}(d)\geq\left(\frac{\delta}{22}\right)^{(d+1)}d^{-(d+1)(3+\log_{2}d)}.$

###### Proof.

Note that for the inequality
$\displaystyle{2(d+2)^{2}\varepsilon^{\frac{1}{d+1}}\leq\beta_{d+2}\delta}$ to
be satisfied it is enough to have

$\varepsilon\leq\left(\frac{2^{7}\delta
d^{-\log_{2}d}}{9^{3}(d+1)(d+2)^{2}}\right)^{d+1}\leq\left(\frac{\delta\beta_{d+2}}{2(d+2)^{2}}\right)^{d+1}.$

In particular, this is true if

$0<\varepsilon\leq\left(\frac{\delta}{22}\right)^{(d+1)}d^{-(d+1)(3+\log_{2}d)}.$

To check that the other condition on $\varepsilon$ is satisfied, note that
such choice of $\varepsilon$ satisfies $\varepsilon<\alpha_{d-2}/2$. Thus we
have

$\left(\frac{\alpha_{d-2}-5\varepsilon}{\alpha_{d-2}-\varepsilon}-2\varepsilon\sum\limits_{t=1}^{d-1}\frac{1}{\alpha_{t-1}}\right)\geq
1-10\alpha_{d-2}^{-1}\varepsilon-2d\alpha_{d-2}^{-1}\varepsilon\geq$ $\geq
1-\frac{2\varepsilon}{(1-\delta)^{2}}(2d+10)d^{\log_{2}d}\geq
1-22d^{1+\log_{2}d}\varepsilon>(1-\delta).$

∎

## References

  * [1] László Babai. “On the order of uniprimitive permutation groups.” Ann. Math. 113.3 (1981): 553-568. (An updated version of the paper appears on the author’s website: http://people.cs.uchicago.edu/ laci/papers/uni-update.pdf.)
  * [2] László Babai. “On the Automorphism Groups of Strongly Regular Graphs I.” Proc. 5th Innovations in Theoretical Comp. Sci. conf. (ITCS’14), ACM, (2014): 359-368.
  * [3] László Babai. “On the automorphism groups of strongly regular graphs II.” J. Algebra 421 (2015): 560-578.
  * [4] Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier. “Distance-Regular Graphs.” Springer, 1989.
  * [5] Sejeong Bang, Akira Hiraki, and Jacobus H. Koolen. “Delsarte clique graphs.” European J. of Combin. 28.2 (2007): 501-516.
  * [6] Sejeong Bang. “Geometric distance-regular graphs without 4-claws.” Linear Alg. Appl. 438.1 (2013): 37-46.
  * [7] Sejeong Bang, and Jacobus H. Koolen. “On geometric distance-regular graphs with diameter three.” European J. Combinatorics 36 (2014): 331-341.
  * [8] Sejeong Bang, Arturas Dubickas, Jack H. Koolen, and Vincent Moulton. “There are only finitely many distance-regular graphs of fixed valency greater than two.” Advances in Mathematics 269 (2015): 1-55.
  * [9] Norman L. Biggs and Anthony Gardiner “The classification of distance transitive graphs.” Manuscript (1974).
  * [10] Alfred Bochert.“Ueber die Classe der transitiven Substitutionengruppen.” Mathematische Annalen 40.2 (1892): 176-193.
  * [11] Peter J. Cameron, Jean-Marie Goethals, Johan Jacob Seidel, E.E. Shult. “Line graphs, root systems and elliptic geometry.” J. Algebra 43 (1976): 305-327.
  * [12] Edwin R. van Dam, Jack H. Koolen, and Hajime Tanaka. “Distance-regular graphs.” Preprint arXiv:1410.6294 (2014).
  * [13] Philippe Delsarte. “An algebraic approach to the association schemes of coding theory.” Philips Res. Reports Suppls. 10 (1973): vi+-97.
  * [14] Willem H. Haemers. “Interlacing eigenvalues and graphs.” Linear Alg. Appl.  226 (1995): 593-616.
  * [15] Camille Jordan. “Theoremes sur les groupes primitifs.” J. Math Pures Appl. 17 (1871): 351-367.
  * [16] Bohdan Kivva. “A characterization of Johnson and Hamming graphs and proof of Babai’s conjecture.” To appear on arXiv.
  * [17] Jacobus H. Koolen, and Sejeong Bang. “On distance-regular graphs with smallest eigenvalue at least $-m$.” J. of Combinatorial Theory, Ser. B 100.6 (2010): 573-584.
  * [18] Martin W. Liebeck. “On minimal degrees and base sizes of primitive permutation groups.” Archiv der Mathematik 43.1 (1984): 11-15.
  * [19] Martin W. Liebeck, Jan Saxl. “Minimal Degrees of Primitive Permutation Groups, with an Application to Monodromy Groups of Covers of Riemann Surfaces.” Proc. London Math. Soc. 3.2 (1991): 266-314.
  * [20] Klaus Metsch. “A characterization of Grassmann graphs.” European J. Combin. 16 (1995): 639-644.
  * [21] Arnold Neumaier.“Strongly regular graphs with smallest eigenvalue $-m$.” Archiv der Mathematik 33.1 (1979): 392-400.
  * [22] Alexander M. Ostrowski. “Solution of Equations and Systems of Equations.” Elsevier, 1966.
  * [23] Alexander Russell, and Ravi Sundaram. “A note on the asymptotics and computational complexity of graph distinguishability.” The Electronic J. Combin. 5.1 (1998): 23-30.
  * [24] Johan Jacob Seidel.“Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Alg. Appl. 1.2 (1968): 281-298.
  * [25] Derek H. Smith. “Primitive and imprimitive graphs.” The Quarterly J. of Math. 22.4 (1971): 551-557.
  * [26] Paul Terwilliger. “A new feasibility condition for distance-regular graphs.” Discrete Math. 61 (1986): 311-315.
  * [27] John Van Bon, and Andries E. Brouwer. “The distance-regular antipodal covers of classical distance-regular graphs.” In Colloq. Math. Soc. Janos Bolyai, Proc. Eger, vol. 1988, (1987): 141-166.
  * [28] Helmut Wielandt. “Abschätzungen für den Grad einer Permutationsgruppe von vorgeschriebenem Transitivitätsgrad.” Schriften des Math. Seminars und des Instituts für angew. Math. der Universität Berlin 2 (1934): 151-174.