# A characterization of Johnson and Hamming graphs and proof of Babai’s
conjecture

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

One of the central results in the representation theory of distance-regular
graphs classifies distance-regular graphs with $\mu\geq 2$ and second largest
eigenvalue $\theta_{1}=b_{1}-1$. In this paper we give a classification under
the (weaker) approximate eigenvalue constraint
$\theta_{1}\geq(1-\varepsilon)b_{1}$ for the class of geometric distance-
regular graphs. As an application, we confirm Babai’s conjecture on the
minimal degree of the automorphism group of distance-regular graphs.

##  1 Introduction

In this paper we characterize Johnson and Hamming graphs as geometric
distance-regular graphs satisfying certain relaxed spectral constraints.
Classical characterization results of Hamming graphs $H(d,q)$ assume equality
constraints on certain parameters such as the assumption $\theta_{1}=b_{1}-1$
on the second largest eigenvalue (Theorem 1.1 below) or the assumption
$n=(\lambda+2)^{d}$ on the number of vertices (Enomoto [17] and Egawa [16]).
The principal novelty of our result is that we make no such tight assumptions.
We apply our characterization to confirm Babai’s conjecture on the minimal
degree of the automorphism group of distance-regular graphs.

###  1.1 Characterization of Johnson and Hamming graphs

A result of Terwilliger [34] (see [9, Theorem 4.4.3]) implies that the
icosahedron is the only distance-regular graph, for which the second largest
eigenvalue $\theta_{1}$ (of the adjacency matrix) satisfies
$\theta_{1}>b_{1}-1$ and a pair of vertices at distance 2 has $\mu\geq 2$
common neighbors. Another classical result gives the classification of
distance-regular graphs with $\mu\geq 2$ and $\theta_{1}=b_{1}-1$.

######  Theorem 1.1 ([9, Theorem 4.4.11]).

Let $X$ be a distance-regular graph of diameter $d\geq 3$ with second largest
eigenvalue $\theta_{1}=b_{1}-1$. Assume $\mu\geq 2$. Then one of the following
holds:

  1. 1.

$\mu=2$ and $X$ is a Hamming graph, a Doob graph, or a locally Petersen graph
(and all such graphs are known).

  2. 2.

$\mu=4$ and $X$ is a Johnson graph.

  3. 3.

$\mu=6$ and $X$ is a half cube.

  4. 4.

$\mu=10$ and $X$ is a Gosset graph $E_{7}(1)$.

In this paper we consider the case $\theta_{1}\geq(1-\varepsilon)b_{1}$ for
sufficiently small $\varepsilon>0$. The relaxation of the assumption on the
second largest eigenvalue comes at the cost of requiring additional structural
constraints. Our main structural assumption is that $X$ is a geometric
distance-regular graph, meaning that there exists a collection of Delsarte
cliques (see Sec. 2.3) $\mathcal{C}$ such that every edge of $X$ belongs to a
unique clique in $\mathcal{C}$. Additional technical structural assumptions
depend on whether the neighborhood graphs of $X$ are connected. We note that
for a geometric distance-regular graph $X$ either the neighborhood graph
$X(v)$ is connected for every vertex $v$, or $X(v)$ is disconnected for every
vertex $v$ (see Lemma 2.19). We give the following two characterizations.

######  Theorem 1.2.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ with
smallest eigenvalue $-m$. Suppose that $\mu\geq 2$ and
$\theta_{1}+1>(1-\varepsilon^{*})b_{1}$ for an absolute constant
$\displaystyle{0<\varepsilon^{*}\approx 0.0065}$. Moreover, assume that the
vertex degree satisfies $k\geq\max(m^{3},29)$ and the neighborhood graph
$X(v)$ is connected for some vertex $v$ of $X$.

Then $X$ is a Johnson graph $J(s,d)$ for $s=(k/d)+d\geq 2d+1$.

######  Remark 1.3.

We give the exact definition of $\varepsilon^{*}$ in Proposition 3.6 (see also
Def. 3.3 and Theorem 3.5). We note that $\varepsilon^{*}$ can be set to be as
large as $2/7$, if we additionally assume $k$ to be sufficiently large (see
Remark 3.13).

######  Theorem 1.4.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ with
smallest eigenvalue $-m$. Suppose that $\mu\geq 2$ and
$\theta_{1}\geq(1-\varepsilon)b_{1}$, where $0<\varepsilon<1/(6m^{4}d)$.
Moreover, assume $c_{t}\leq\varepsilon k$ and $b_{t}\leq\varepsilon k$ for
some $t\leq d$, and the neighborhood graph $X(v)$ is disconnected for some
vertex $v$ of $X$.

Then $X$ is a Hamming graph $H(d,s)$, for $s=1+k/d$.

######  Remark 1.5.

If $s>6d^{5}+1$, then the Hamming graph $H(d,s)$ satisfies the assumptions of
this theorem with $1/(s-1)\leq\varepsilon<1/(6d^{5})$ and $t=d$.

The assumption that a distance-regular graph is geometric excludes only
finitely many graphs with $\mu\geq 2$, if the smallest eigenvalue of the graph
is assumed to be bounded, as proved by Bang and Koolen [25] in 2010.

######  Theorem 1.6 (Koolen, Bang).

Fix an integer $m\geq 2$. There are only finitely many non-geometric distance-
regular graphs of diameter $\geq 3$ with $\mu\geq 2$ and smallest eigenvalue
at least $-m$.

Moreover, they conjecture the following classification of geometric distance-
regular graphs with fixed smallest eigenvalue $-m$ and $\mu\geq 2$.

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

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

Our characterizations confirm this conjecture in rather special cases.

Theorem 1.4 is one of the main technical contributions of the paper. Even
though the assumptions of Theorem 1.2 seem weaker (for instance, $\varepsilon$
is absolute), we believe that, in comparison with known results, Theorem 1.4
brings more novelty. The known characterization of Johnson graphs in terms of
the local structure (Theorem 2.21) seems to be more easily applicable than the
known characterizations of Hamming graphs. All characterizations of Hamming
graphs known to the author, in terms of intersection numbers, eigenvalues or
local structure, make strong equality constraints either on the number of
vertices, or on the eigenvalues. In contrast, Theorem 1.4 makes no assumptions
of such flavor and therefore might be more broadly applicable.

###  1.2 Motion: Minimal degree of the automorphism group

For a permutation $\sigma$ 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 a set $\Omega$. The minimum of the degrees of non-
identity elements of $G$ is called the minimal degree of $G$. We denote this
quantity by $\operatorname{mindeg}(G)$. Lower bounds on the minimal degree of
a group have strong constraints on the structure of the group. A result of
Wielandt [37] implies that a linear lower bound on $\operatorname{mindeg}(G)$
provides a logarithmic upper bound on the degree of an alternating group
involved in $G$ as a quotient of a subgroup. The study of the minimal degree
goes back to 19th century (Jordan [22], Bochert [7]). We briefly indicate some
of the history and the motivation of this classical concept in the Outlook
section (Sec. 6).

######  Definition 1.8 (Motion).

Following [31], for a combinatorial structure $\mathcal{X}$ we use term motion
for the minimal degree of the automorphism group
$\operatorname{Aut}(\mathcal{X})$,

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

In 2014 Babai [3], [4] classified the strongly regular graphs with sublinear
motion.

######  Theorem 1.9 (Babai).

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

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

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

Non-trivial strongly regular graphs are primitive distance-regular graphs of
diameter 2. Babai conjectured that a similar classification should be true for
primitive distance-regular graphs of fixed diameter.

######  Conjecture 1.10 (Babai).

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

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

or $X$ is the Johnson graph or the Hamming graph.

Using our characterizations of Johnson and Hamming graphs, we confirm the
conjecture in the stronger form dropping the primitivity assumption. (The
imprimitive case admits one more class of exceptions, the cocktail-party
graphs). A large portion of the proof relies on the results we prove in [23].

######  Theorem 1.11.

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

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

or $X$ is a Johnson graph, or a Hamming graph, or a cocktail-party graph.

In [23] we reduced the case of imprimitive distance-regular graphs to
confirming the conjecture for primitive graphs. Moreover, in one of the main
results of [23] we show that it is sufficient to study geometric distance-
regular graphs with bounded smallest eigenvalue, which is the case we settle
in this paper.

######  Theorem 1.12 ([23, Theorem 1.6]).

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

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

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

######  Remark 1.13.

The reason we split the proof of Theorem 1.11 between two papers is the
different nature of techniques and results obtained. In particular, in [23] we
prove a spectral gap bound for distance-regular graphs which have a dominant
distance. We use it as one of the ingredients in the analysis of $\mu=1$ case
in this paper (see Theorem 5.2).

###  1.3 A few words on the proof of the characterization theorems

The proof of Theorem 1.1 has two crucial ingredients. The first ingredient is
Terwilliger’s $1+b_{1}/(\theta_{1}+1)$ lower bound on the smallest eigenvalue
of the neighborhood graphs. In the case when $\theta_{1}=b_{1}-1$ this bound
implies that the smallest eigenvalue of each neighborhood graph is at least
$-2$ and all such graphs are classified by Cameron, Goethals, Seidel and Shult
[11] (note that the neighborhood graphs are regular). In particular, if a
neighborhood graph has no induced quadrangle, then the neighborhood graph is a
clique, the pentagon or the Peterson graph. The second ingredient is the
existence of a root representation (an integral affine (2, 4)-representation)
for a distance-regular graph with $\theta_{1}=b_{1}-1$ and which contains a
quadrangle. The classification of the amply regular graphs with $\mu\geq 2$,
which have a root representation, is known (see [9, Theorems 3.15.1-3.15.4]).

We note that in the case of geometric distance-regular graphs the condition
$\mu\geq 2$ implies the existence of an induced quadrangle. The argument that
shows the existence of the root representation heavily depends on the equality
constraint $\theta_{1}=b_{1}-1$ and does not survive when this condition is
relaxed to $\theta_{1}\geq(1-\varepsilon)b_{1}$. However, under our
assumptions, we are still able to make use of the first ingredient. Indeed,
results of Hoffman [21] and Bussemaker, Neumaier [10] imply that no graph has
the smallest eigenvalue in the range $(-2-\delta,-2)$ for some constant
$\delta>0$. This will be sufficient to prove Theorem 1.2 (see Section 3).

The proof of Theorem 1.4 requires a different approach. A distance-regular
graph is geometric with disconnected neighborhood graphs if and only if each
of its neighborhood graphs is a disjoint union of cliques. We prove that if
$X$ satisfies the assumptions of Theorem 1.4 and is not a Hamming graph, then
the second largest eigenvalue has multiplicity less than the vertex degree of
$X$. Terwilliger [34] proved that this implies that each neighborhood graph
has an eigenvalue less than $-1$. This leads to a contradiction, as the least
eigenvalue of a disjoint union of cliques is $-1$. We prove Theorem 1.4 in
Section 4.

## Acknowledgments

The author is grateful to Professor László Babai for introducing him to the
problems discussed in the paper, for his invaluable assistance in framing the
results, which significantly improved the presentation of the paper, and for
his constant support and encouragement.

##  2 Preliminaries

In this section we give definitions and basic properties for the objects and
notions that are used in the paper. For more about distance-regular graphs we
refer the reader to the monograph [9] and the survey article [14].

###  2.1 Basic concepts and notation for graphs

Let $X$ be a graph. We always denote by $n$ the number of vertices of $X$ and
for a regular graph $X$ we denote by $k$ its degree. We denote the diameter of
$X$ by $d$. If the graph is disconnected, then its diameter is defined to be
$\infty$.

######  Definition 2.1.

A regular graph is called edge-regular if every pair of adjacent vertices has
the same number $\lambda$ of common neighbors.

######  Definition 2.2.

A regular graph is called amply regular if every pair of vertices at distance
2 has the same number $\mu$ of common neighbors.

Let $N(v)$ be the set of neighbors of a 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$. By $X(v)$ we denote the neighborhood
graph of $v$ in $X$, namely, the graph induced by $X$ on $N(v)$.

######  Definition 2.3.

Let $X$ be a graph. Denote by $V(X)$ and $E(X)$ the set of vertices and the
set of edges of $X$. The line graph of $X$ is the graph $L(X)$ with the set of
vertices $E(X)$, in which distinct $e_{1},e_{2}\in E(X)$ are adjacent if they
(as edges of $X$) share a vertex.

By eigenvalues of a graph we mean the eigenvalues of its adjacency matrix.

###  2.2 Distance-regular graphs

######  Definition 2.4.

A connected graph $X$ of diameter $d$ is called distance-regular if for every
$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 $c_{i}$, and between
$w$ and $N_{i+1}(v)$ is $b_{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 every distance-regular graph is edge-regular and amply regular with
$\lambda=a_{1}$ and $\mu=c_{2}$.

By simple counting, the following properties of the parameters of distance-
regular graphs hold.

  1. 1.

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

  2. 2.

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

  3. 3.

$|N_{i}(v)|b_{i}=|N_{i+1}(v)|c_{i+1}$, for $0\leq i\leq d-1$ and any vertex
$v$.

Thus, the numbers $k_{i}=|N_{i}(v)|$ do not depend on a vertex $v\in X$, and
we can rewrite the last property as

  1. 3’.

$k_{i}b_{i}=k_{i+1}c_{i+1}$, for $0\leq i\leq d-1$.

From the definition of a distance-regular graph it can be deduced that there
are parameters $p_{i,j}^{s}$ such that for any $u,v\in X$ with
$\operatorname{dist}(u,v)=s$ there exist precisely $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}$. The parameters $p_{i,j}^{s}$ are called intersection
numbers.

######  Lemma 2.5.

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Then $2\lambda\leq
k+\mu$.

###### Proof.

Denote $N(x,y)=N(x)\cap N(y)$ for vertices $x$ and $y$ of $X$. The inequality
above follows from the two obvious inclusions below applied for $v$ and $w$ at
distance $2$ and their common neighbor $v$

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

∎

In Section 4 we will need the following inequality proved by Terwilliger [33].

######  Theorem 2.6 (Terwilliger [33], see [9, Theorem 5.2.1]).

Let $X$ be a distance-regular graph. If $X$ contains an induced quadrangle,
then

$c_{i}-b_{i}\geq c_{i-1}-b_{i-1}+\lambda+2,\quad\text{for }i=1,2,\ldots,d.$

We also need the following result regarding the increase $c_{i}-c_{i-1}$.

######  Theorem 2.7 ([9, Theorem 5.4.1]).

Let $X$ be a distance-regular graph of diameter $d\geq 3$. If $\mu\geq 2$,
then either $c_{3}\geq 3\mu/2$, or $c_{3}\geq\mu+b_{2}$ and $d=3$.

######  Corollary 2.8.

Let $X$ be a distance-regular graph of diameter $d\geq 3$. If $\mu\geq 2$,
then $c_{3}>\mu$.

A distance-regular graph $X$ of diameter $d$ has precisely $d+1$ distinct
eigenvalues. Denote these eigenvalues by
$\theta_{0}=k>\theta_{1}>\ldots>\theta_{d}$. They are the eigenvalues of the
tridiagonal intersection matrix below.

$L_{1}=\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).$

For an eigenvalue $\theta$, consider the sequence $(u_{i}(\theta))_{i=0}^{d}$
defined by the relations

$u_{0}(\theta)=1,\qquad u_{1}(\theta)=\frac{\theta}{k},$
$c_{i}u_{i-1}(\theta)+a_{i}u_{i}(\theta)+b_{i}u_{i+1}(\theta)=\theta
u_{i}(\theta),\quad\text{for }i=1,2,...,d-1,$
$c_{d}u_{d-1}(\theta)+a_{d}u_{d}(\theta)=\theta u_{d}(\theta).$

The vector $u=(u_{0}(\theta),u_{1}(\theta),...,u_{d}(\theta))^{T}$ is an
eigenvector of $L_{1}$ corresponding to $\theta$.

######  Definition 2.9.

The sequence $(u_{i}(\theta))_{i=0}^{d}$ is called the standard sequence of
$X$ corresponding to the eigenvalue $\theta$.

We denote by $f_{i}$ the multiplicity of the eigenvalue $\theta_{i}$ of $X$.
Since $X$ is a connected graph, $f_{0}=1$. In general, the multiplicities
$f_{i}$ can be computed using the Biggs formula.

######  Theorem 2.10 (Biggs [6], see [9, Theorem 4.1.4]).

The multiplicity of an eigenvalue $\theta$ of a distance-regular graph $X$ can
be expressed as

$f(\theta)=\frac{n}{\sum\limits_{i=0}^{d}k_{i}u_{i}(\theta)^{2}}.$

###  2.3 Geometric distance-regular graphs

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

######  Definition 2.11.

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 exactly
one clique of $\mathcal{C}$.

More generally, we say that a graph contains a clique geometry, if there
exists a collection $\mathcal{C}_{0}$ of maximal cliques, such that every edge
is contained in exactly one clique of $\mathcal{C}_{0}$. Metsch proved that a
graph satisfying rather modest assumptions contains a clique geometry.

######  Theorem 2.12 (Metsch [28, Result 2.2]).

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

  1. 1.

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

  2. 2.

Each 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.

The following sufficient condition for being geometric is a slightly
reformulated version of a result from [14].

######  Proposition 2.13 ([14, Proposition 9.8]).

Let $X$ be a distance-regular graph of diameter $d\geq 2$. 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
$k\geq m^{2}$, then $X$ is geometric with smallest eigenvalue $-m$.

The converse holds without the $k\geq m^{2}$ assumption.

######  Lemma 2.14.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ with
smallest eigenvalue $-m$. Let $\mathcal{C}$ be a Delsarte clique geometry.
Then $m$ is an integer and every vertex belongs to precisely $m$ Delsarte
cliques in $\mathcal{C}$.

###### Proof.

By the definition of a Delsarte clique, its size is $1+k/m$. Let
$C_{1},C_{2},\ldots,C_{t}$ be the cliques in $\mathcal{C}$ which contain a
vertex $v$. Since $\mathcal{C}$ is a clique geometry, any distinct $C_{i}$ and
$C_{j}$ for $i,j\in[t]$ have only $v$ in their intersection, and every vertex
adjacent to $v$ belongs to one of the cliques $C_{1},C_{2},\ldots,C_{t}$.
Therefore, $k=t(|C_{i}|-1)=tk/m$. ∎

In the case, when the smallest eigenvalue of a geometric distance-regular
graph is $-2$, we can deduce that the graph is a line graph.

######  Lemma 2.15.

Let $X$ be a geometric distance-regular graph with smallest eigenvalue $-2$.
Then $X$ is the line graph $L(Y)$ for some graph $Y$.

###### Proof.

Let $\mathcal{C}$ be a Delsarte clique geometry of $X$. Define the graph $Y$
with the set of vertices $V(Y)=\mathcal{C}$, in which a pair of distinct
vertices $C_{1},C_{2}\in\mathcal{C}$ in $Y$ is adjacent if and only if
$C_{1}\cap C_{2}\neq\emptyset$. We claim that $L(Y)\cong X$. Indeed, since
every edge of $X$ is in exactly one clique from $\mathcal{C}$, $|C_{1}\cap
C_{2}|\leq 1$ for any distinct $C_{1},C_{2}\in\mathcal{C}$. So there is a
well-defined map $f:E(Y)\rightarrow V(X)$. Moreover, by Lemma 2.14, every
vertex of $X$ is in exactly two cliques from $\mathcal{C}$, so $f$ is
bijective. Additionally, a pair of edges in $Y$ share a vertex if and only if
there is an edge between the corresponding vertices in $X$. Hence, $L(Y)\cong
X$. ∎

Suppose that $X$ is a geometric distance-regular graph with a Delsarte clique
geometry $\mathcal{C}$. Consider a Delsarte clique $C\in\mathcal{C}$. Assume
$x\in X$ satisfies $\operatorname{dist}(x,C)=i$. Define

$\psi_{i}(C,x):=|\\{y\in C\mid d(x,y)=i\\}|.$ (1)

By [5], numbers $\psi_{i}(C,x)$ do not depend on $C$ and $x$, but only on the
distance $\operatorname{dist}(x,C)=i$. Thus, we may define
$\psi_{i}:=\psi(C,x)$.

For $x,y\in X$ with $\operatorname{dist}(x,y)=i$ define

$\tau_{i}(x,y;\mathcal{C})=|\\{C\in\mathcal{C}\mid x\in C,\,d(y,C)=i-1\\}|.$
(2)

Again, in [5] it is shown that for a geometric distance-regular graph $X$ the
number $\tau_{i}(x,y;\mathcal{C})$ does not depend on the pair $x,y$, but only
on the distance $\operatorname{dist}(x,y)=i$. Therefore, we may define
$\tau_{i}:=\tau_{i}(x,y;\mathcal{C})$.

######  Lemma 2.16 (Bang, Hiraki, Koolen [5, Proposition 4.2]).

Let $X$ be a geometric distance-regular graph of diameter $d$, with smallest
eigenvalue $-m$. Then

  1. 1.

$c_{i}=\tau_{i}\psi_{i-1}$, for $1\leq i\leq d$;

  2. 2.

$\displaystyle{b_{i}=(m-\tau_{i})\left(\frac{k}{m}+1-\psi_{i}\right)}$, for
$1\leq i\leq d-1$.

######  Lemma 2.17.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$. Then
$\tau_{2}\geq\psi_{1}$.

###### Proof.

Let $C\in\mathcal{C}$ be a Delsarte clique of $X$ and let $v$ be a vertex with
$\operatorname{dist}(v,C)=1$. Since $C$ is a maximal clique, there exists a
vertex $y\in C$ non-adjacent to $v$. Then $\operatorname{dist}(v,y)=2$. Let
$u_{1},u_{2},\ldots,u_{\psi_{1}}$ be the neighbors of $v$ in $C$. Denote by
$C_{i}\in\mathcal{C}$ a Delsarte clique that contains $v$ and $u_{i}$ for
$i\in[\psi_{1}]$. Note that since $C$ intersects each of $C_{i}$ in at most
one vertex, all $C_{i}$ are distinct. Moreover,
$\operatorname{dist}(y,C_{i})=1$, while $\operatorname{dist}(v,y)=2$.
Therefore, $\tau_{2}\geq\psi_{1}$. ∎

######  Corollary 2.18.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$, with
smallest eigenvalue $-m$. Then $\mu\leq m^{2}$.

###### Proof.

$\mu=\tau_{2}\psi_{1}\leq\tau_{2}^{2}\leq m^{2}$. ∎

######  Lemma 2.19.

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

  1. 1.

If $\psi_{1}=1$, then for each vertex $v\in X$ its neighborhood graph $X(v)$
is a disjoint union of $m$ cliques, where $-m$ is the smallest eigenvalue of
$X$.

  2. 2.

If $\psi_{1}\geq 2$, then for each vertex $v\in X$ its neighborhood graph
$X(v)$ is connected.

Thus, in particular, either each neighborhood graph of $X$ is connected, or
each neighborhood graph of $X$ is disconnected.

###### Proof.

Fix a Delsarte clique geometry $\mathcal{C}$ of $X$. Let
$C_{1},C_{2},\ldots,C_{m}\in\mathcal{C}$ be the cliques which contain $v$.
Take $w\in N(v)$ and let $C_{i}$ be the clique which contains $w$. If
$\psi_{1}=1$, then $v$ is the only neighbor of $w$ in $C_{j}$ for $j\neq i$.
Thus $X(v)$ is a disjoint union of $m$ cliques, where by Lemma 2.14, $-m$ is
the smallest eigenvalue of $X$. If $\psi_{1}\geq 2$, then $w$ is adjacent with
at least one vertex in $C_{j}$ distinct from $u$ for every $j\neq i$. Thus
$X(v)$ is a connected graph in this case. ∎

###  2.4 Johnson graphs and Hamming graphs

####  2.4.1 Johnson graphs

######  Definition 2.20.

Let $d\geq 2$ and $\Omega$ be a set of $s\geq 2d$ points. The Johnson graph
$J(s,d)$ is a graph on the set $V(J(s,d))=\binom{\Omega}{d}$ of
$n=\binom{s}{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(s,d)$ is a distance-regular graph of diameter
$d$ with intersection numbers

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

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

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

Using Lemma 2.16 it is easy to see that for the Johnson graph $J(s,d)$

$\tau_{i}=i\quad\text{and}\quad\psi_{i-1}=i,\quad\text{for }1\leq i\leq d.$

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

Thus, for a fixed $d$ and $s\geq 2d+1$, the order is
$|\operatorname{Aut}(J(s,d)|=s!=\Omega(\exp(n^{1/d}))$, the thickness
satisfies $\theta(\operatorname{Aut}(J(s,d)))=s=\Omega(n^{1/d})$ and

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

######  Theorem 2.21 ([9, Theorem 9.1.3]).

Let $X$ be a connected graph such that

  1. 1.

for each vertex $v$ of $X$ the graph $X(v)$ is the line graph of $K_{s,t}$;

  2. 2.

if $\operatorname{dist}(x,y)=2$, then $x$ and $y$ have at most $4$ common
neighbors.

Then $X$ is a Johnson graph or is doubly covered by a Johnson graph. More
precisely, in the latter case $X$ is the quotient of the Johnson graph
$J(2d,d)$ by an automorphism of the form $\tau\omega$, where $\tau$ is the
automorphism sending each $d$-set to its complement, and $\omega$ is an
element of order at most $2$ in $Sym(X)$ with at least $8$ fixed points.

####  2.4.2 Hamming graphs

######  Definition 2.22.

Let $\Omega$ be a set of $s\geq 2$ points. The Hamming graph $H(d,s)$ is a
graph on the set $V(H(d,s))=\Omega^{d}$ of $n=s^{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,s)$ is a distance-regular graph of
diameter $d$ with intersection numbers

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

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

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

Using Lemma 2.16 it is easy to see that for the Hamming graph $H(d,s)$

$\tau_{i}=i\quad\text{and}\quad\psi_{i-1}=1,\quad\text{for }1\leq i\leq d.$

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

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

In Section 4 we use the classification of distance-regular graphs with the
same intersection array as Hamming graphs. In the case of diameter $2$, the
unique non-Hamming graph that has the intersection array of a Hamming graph is
the Shrikande graph. It has 16 vertices and has the same parameters as
$H(2,4)$.

######  Definition 2.23.

The direct product of a Hamming graph $H(t,4)$ with $\ell\geq 1$ copies of the
Shrikande graph is called a Doob graph.

One can check that Doob graphs are distance-regular and have the same
intersection numbers as the Hamming graph $H(t+2\ell,4)$. Yoshimi Egawa [16]
proved that Doob graphs are the only graphs with this property.

######  Theorem 2.24 (Egawa [16], see [9, Corollary 9.2.5]).

A distance-regular graph of diameter $d$ with intersection numbers given by
Eq. (6) is a Hamming graph or a Doob graph.

###  2.5 Dual graphs

Let $X$ be a distance-regular graph which has a clique geometry $\mathcal{C}$.

######  Definition 2.25.

By a dual graph of $X$ (that corresponds to $\mathcal{C}$) we mean the graph
$\widetilde{X}$ with the vertex set $\mathcal{C}$, in which $C_{i}$ and
$C_{j}$ are adjacent if and only if $|C_{i}\cap C_{j}|=1$.

######  Lemma 2.26.

Let $X$ be a geometric distance-regular graph of diameter $d$ with smallest
eigenvalue $-m$. Then its dual graph $\widetilde{X}$ is an edge-regular graph
of diameter $d-1$ with the vertex degree
$\displaystyle{\widetilde{k}=(m-1)\left(\frac{k}{m}+1\right)}$ and
$\displaystyle{\widetilde{\lambda}=(m-2)+(\psi_{1}-1)\frac{k}{m}}$.

###### Proof.

It is known that every Delsarte clique is completely regular, with covering
radius $d-1$, see [19, Lemma 7.2]. In particular, this implies that the
diameter of $\widetilde{X}$ is $d-1$. Every clique in the Delsarte clique
geometry $\mathcal{C}$ of $X$ has size $1+k/m$ and, by Lemma 2.14, every
vertex is in precisely $m$ cliques from $\mathcal{C}$. Since every pair of
non-disjoint cliques intersects in precisely one vertex, we get
$\widetilde{k}=(m-1)(1+k/m)$.

Now assume that $C_{1}$ and $C_{2}$ are distinct cliques in $\mathcal{C}$ that
share a vertex $v$. Let $u\in C_{1}$ be a vertex distinct from $v$. Then $u$
has $\psi_{1}$ neighbors in $C_{2}$. Let $u^{\prime}$ be one of such neighbors
distinct from $v$. Then the edge $\\{u,u^{\prime}\\}$ belongs to some clique
$C$ which is distinct from $C_{1}$ and $C_{2}$ and intersects both of them.
Thus, $C$ is a common neighbor of $C_{1}$ and $C_{2}$. Note, that a common
neighbor $C\in\mathcal{C}$ of $C_{1}$ and $C_{2}$, which does not contain $v$,
is uniquely determined by $u\in C_{1}$ and its neighbor $u^{\prime}$ in
$C_{2}$. Finally, note that any clique from $\mathcal{C}$ which contains $v$
and is distinct from $C_{1}$ and $C_{2}$ is their common neighbor. Hence,
$\widetilde{\lambda}=(m-2)+(\psi_{1}-1)k/m$. ∎

Let $A$ and $\widetilde{A}$ be the adjacency matrices of $X$ and
$\widetilde{X}$. Denote by $\operatorname{spec}(X)$ and
$\operatorname{spec}(\widetilde{X})$ the sets of eigenvalues of $A$ and
$\widetilde{A}$, respectively.

######  Lemma 2.27.

Let $X$ be a geometric distance-regular graph with smallest eigenvalue $-m$.
If $k\geq m^{2}$, then
$\displaystyle{\operatorname{spec}(\widetilde{X})\subseteq\\{\theta-\frac{k}{m}+m-1\mid\theta\in\operatorname{spec}(X)\\}}$.

###### Proof.

Let $\mathcal{C}$ be a Delsarte clique geometry of $X$. Note that, by Lemma
2.14, every vertex of $X$ belongs to precisely $m$ cliques of $\mathcal{C}$.
Define $N$ to be an $n\times|\mathcal{C}|$ vertex-clique incidence matrix,
i.e, $N_{i,j}=1$ if the vertex $v_{i}$ belongs to the clique $C_{j}$, and
$N_{i,j}=0$ otherwise. Then

$A=NN^{T}-mI\qquad\text{and}\qquad\widetilde{A}=N^{T}N-\left(\frac{k}{m}+1\right)I.$
(9)

From linear algebra it is known that non-zero eigenvalues of $NN^{T}$ and
$N^{T}N$ coincide. Since $|\mathcal{C}|(1+k/m)=nm$, we get $|\mathcal{C}|<n$,
so 0 is an eigenvalue of $NN^{T}$. Therefore,
$\operatorname{spec}(N^{T}N)\subseteq\operatorname{spec}(NN^{T})$ and the
statement of the lemma follows from Eq. (9). ∎

##  3 Spectral gap characterization of Johnson graphs

In this section we prove Theorem 1.2, our characterization of Johnson graphs.
Namely, we prove that a distance-regular graph with
$\theta_{1}+1>(1-\varepsilon^{*})b_{1}$ and connected neighborhood graphs is a
Johnson graph (for sufficiently large $k$). We also show that the inequality
$\theta_{1}+1>(1-\varepsilon^{*})b_{1}$ can hold for a distance-regular graph
with disconnected neighborhood graphs only if $\mu\leq 2$ (see Proposition
3.11).

The main idea of the proofs is to use the fact that for
$\displaystyle{b^{+}=\frac{b_{1}}{\theta_{1}+1}}$ the expression $-1-b^{+}$ is
a lower bound on the smallest eigenvalue of the neighborhood graph $X(v)$.
More precisely, we use the following result of Terwilliger [34].

######  Theorem 3.1 (Terwilliger [34], see [9, Theorem 4.4.3]).

Let $X$ be a distance-regular graph of diameter $d\geq 2$ with distinct
eigenvalues $k=\theta_{0}>\theta_{1}>\ldots>\theta_{d}$, and put
$\displaystyle{b^{+}=\frac{b_{1}}{\theta_{1}+1}}$,
$\displaystyle{b^{-}=\frac{b_{1}}{\theta_{d}+1}}$. Then each neighborhood
graph $X(v)$ has the smallest eigenvalue $\geq-1-b^{+}$, and the second
largest eigenvalue $\leq-1-b^{-}$.

Recall, we assume that the second largest eigenvalue of $X$ satisfies
$\theta_{1}+1\geq(1-\varepsilon)b_{1}$. In this case the smallest eigenvalue
of the neighborhood graph $X(v)$ is at least $-2-\delta$, for
$\delta=\varepsilon/(1-\varepsilon)$. We also observe that if $X$ is an edge-
regular graph, its neighborhood graph $X(v)$ is regular for every vertex $v\in
X$.

First, we note that if the diameter $d$ of a distance-regular graph $X$ is at
least 2, $\lambda>2$ and the neighborhood graph $X(v)$ is connected, then the
smallest eigenvalue of $X(v)$ is at most $-2$. Indeed, if a regular connected
graph has the smallest eigenvalue $>-2$, then it is a complete graph or an odd
polygon. The neighborhood graph $X(v)$ cannot be complete as $d\geq 2$ and
$X(v)$ cannot be an odd polygon as $\lambda>2$.

The graphs for which smallest eigenvalue is precisely $-2$ were classified by
Cameron, Goethals, Seidel and Shult [11]. We use their classification in the
case when a graph $Y$ is a connected regular graph.

######  Theorem 3.2 (Cameron et al. [11], see [9, Theorem 3.12.2]).

Let $Y$ be a connected regular graph with $n\geq 29$ vertices and smallest
eigenvalue $\geq-2$. Then $Y$ is a line graph of a regular connected graph or
of a bipartite semiregular connected graph.

Next, we use the results of Hoffman, Bussemaker and Neumaier, which assert
that for a small enough $\delta$ the smallest eigenvalue of a graph is never
in the interval $(-2-\delta,-2)$.

######  Definition 3.3.

Define $\vartheta_{k}$ to be the supremum of the smallest eigenvalues of
graphs with minimal valency $k$ and smallest eigenvalue $<-2$.

######  Theorem 3.4 (Hoffman [21], see [9, Theorem 3.12.5]).

The sequence $(\vartheta_{k})_{k}$ forms a monotone decreasing sequence with
limit $-1-\sqrt{2}$.

######  Theorem 3.5 (Bussemaker, Neumaier [10], see [9, Theorem 3.12.5]).

$\vartheta_{1}\approx-2.006594$ is the smallest root of the equation

$\theta^{2}(\theta^{2}-1)^{2}(\theta^{2}-3)(\theta^{2}-4)=1.$

The above discussion can be summarized in the following proposition.

######  Proposition 3.6.

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Assume that the
second largest eigenvalue of $X$ satisfies
$\theta_{1}+1>(1-\varepsilon^{*})b_{1}$, for
$\displaystyle{0<\varepsilon^{*}=\frac{-2-\vartheta_{1}}{-1-\vartheta_{1}}}$.
Then for every vertex $v$ of $X$, the neighborhood graph $X(v)$ is a regular
graph with smallest eigenvalue at least $-2$.

Moreover, if $X(v)$ is connected, $\lambda>2$, and the vertex degree in $X$ is
at least $29$, then $X(v)$ is the line graph of a regular or of a bipartite
semiregular connected graph.

######  Remark 3.7.

One can compute that $\varepsilon^{*}\approx 0.006551$. Observe that, the
neighborhood graph $X(V)$ is regular of degree $\lambda$, and by Theorem 3.4,
$\lim\limits_{\lambda\rightarrow\infty}\vartheta_{\lambda}=-1-\sqrt{2}$. Thus,
we can replace $\varepsilon^{*}$ with any number less than
$1-1/\sqrt{2}\approx 0.29289$, if we additionally require $\lambda$ to be
sufficiently large.

Next we analyze the structure of the local graph $X(v)$ in the case when $X$
is geometric.

######  Lemma 3.8.

Let $X$ be a geometric distance distance-regular graph with smallest
eigenvalue $-m$. Suppose that $X(v)$ is the line graph of a regular or a
bipartite semiregular connected graph. Assume that vertex degree
$k\geq\max(m^{3},3)$. Then, $X(v)$ is the line graph of a complete bipartite
graph $K_{s,t}$ for each vertex $v$ of $X$, where $\\{s,t\\}=\\{m,k/m\\}$.

###### Proof.

Fix a Delsarte clique geometry $\mathcal{C}$ of $X$. Let
$C_{1},C_{2},\ldots,C_{m}\in\mathcal{C}$ be the cliques that contain a vertex
$v$. Since every edge of $X$ is contained in precisely one clique, every
vertex of $N(v)$ is contained in precisely one of $C_{1},C_{2},\ldots,C_{m}$.
Let $u\in C_{1}\setminus\\{v\\}$, by the definition of $\psi_{i}$ (see Section
2.3), $u$ is adjacent with precisely $\psi_{1}$ vertices of $C_{i}$ for all
$i=2,3,\ldots,m$. Therefore, the degree of every vertex $u$ in $X(v)$ equals
$k/m-1+(\psi_{1}-1)(m-1)$.

Assume that $Y$ is the line graph of a regular graph $Z$ with vertex degree
$t$. Then the degree of a vertex in $Y$ is equal $2(t-1)$. Moreover, the size
of a maximal clique in $Y$ is $t$, if $t\geq 3$. Since $Y$ contains a clique
of size $k/m$, we get $t\geq k/m$. Therefore, if $k/m\geq 3$ and
$(k/m-1)>(\psi_{1}-1)(m-1)$, then $X(v)$ is not a line graph of a regular
graph. In particular this is true, if $k\geq\max(m^{3},3)$, as
$\psi_{1}\leq\tau_{2}\leq m$ by the definition of $\tau_{2}$ and Lemma 2.17.

Hence, for every $v$, the neighborhood graph $X(v)$ is the line graph of a
complete bipartite graph $K_{s,t}$. The size of the maximal clique in the line
graph of $K_{s,t}$ is $\max(s,t)$. Thus, $\max(s,t)=k/m$. There are $k$
vertices in $X(v)$ and $st$ vertices in the line graph of $K_{s,t}$, so
$\\{s,t\\}=\\{m,k/m\\}$. ∎

In the case when $X(v)$ is the line graph of a complete bipartite graph
$K_{s,t}$ and $1+\theta_{1}\geq(1-\varepsilon)b_{1}$ we show that $X$ is a
Johnson graph. Our goal is to use the characterization of the Johnson graphs
by local structure stated in Theorem 2.21. The only condition we still need to
verify is $\mu\leq 4$. We prove that if $\mu>4$, then $X$ contains an induced
subgraph $K_{3,2}$ and so we can use the inequality provided by the theorem
below.

######  Theorem 3.9 ([9, Theorem 4.4.6]).

Let $X$ be a distance-regular graph of diameter $d\geq 2$ with eigenvalues
$k=\theta_{0}>\theta_{1}>\ldots>\theta_{d}$ and put
$b^{+}=b_{1}/(\theta_{1}+1)$. If $X$ contains a non-empty induced complete
bipartite subgraph $K_{s,t}$, then

$\frac{2st}{s+t}\leq b^{+}+1.$

######  Lemma 3.10.

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

  1. 1.

Assume that $\psi_{1}=1$, then $X$ contains an induced $K_{\tau_{2},2}$.

  2. 2.

Assume that $\mu\geq 2$, then $X$ contains an induced $K_{2,2}$ (a
quadrangle).

###### Proof.

Let $u$ and $v$ be two vertices at distance $2$ in $X$. By the definition of
$\tau_{2}$ there exist distinct cliques $C_{1},C_{2},\ldots,C_{\tau_{2}}$
which contain $u$ and have non-trivial intersection with $N(v)$.

  1. 1.

Each $C_{i}$ has precisely $\psi_{1}=1$ common vertices with $N(v)$. Denote
$w_{i}=C_{i}\cap N(v)$. Note that $w_{i}$ is at distance $1$ from $C_{j}$ for
$i\neq j$, moreover, $w_{i}$ is adjacent to $u$, while $u\in C_{j}$ and $u\neq
w_{j}$. Thus $w_{j}$ is not adjacent to $w_{i}$ for $i\neq j$. Therefore, $X$
contains an induced $K_{\tau_{2},2}$ (on vertices
$\\{w_{1},w_{2},\ldots,w_{\tau_{2}},u,v\\}$).

  2. 2.

By Lemma 2.17, $\tau_{2}\geq 2$, if $\mu\geq 2$. Take $w\in N(v)\cap C_{1}$.
Assume there are no induced $K_{2,2}$ in $X$. Then $w$ is adjacent to each
vertex in $T=C_{2}\cap N(v)$. Note that $|T|=\psi_{1}$, $u\notin T$ and $w$ is
adjacent to $u$, so $w$ has at least $\psi_{1}+1$ neighbors in $C_{2}$. This
gives a contradiction with the definition of $\psi_{1}$.

∎

Using the lemma above we obtain the following corollary to the Theorem 3.9.

######  Proposition 3.11.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$. Assume
that the neighborhood graphs of $X$ are disconnected. If $\mu\geq 3$, then the
second largest eigenvalue of $X$ satisfies
$\displaystyle{\theta_{1}+1\leq\frac{5}{7}b_{1}}$.

###### Proof.

Since $X$ is geometric and $X(v)$ is disconnected, by Lemma 2.19,
$\psi_{1}=1$. Moreover, if $\mu\geq 3$, by Lemma 3.10, there is an induced
$K_{3,2}$. Therefore, by Theorem 3.9,

$\frac{b_{1}}{\theta_{1}+1}\geq\frac{12}{5}-1=\frac{7}{5}.$

∎

In the next lemma we show the existence of an induced complete bipartite
subgraph $K_{\tau_{2},2}$ in the case when a neighborhood graph is the line
graph of a triangle-free graph.

######  Lemma 3.12.

Let $X$ be a geometric distance-regular graph. Assume that for each vertex $v$
of $X$ the induced subgraph $X(v)$ is the line graph of a triangle-free graph.
Then $\psi_{1}=2$ and $X$ contains induced $K_{\tau_{2},2}$.

###### Proof.

Observe that if the line graph $Y$ of a triangle-free graph $Y^{\prime}$
contains a triangle, then the corresponding edges (of the base graph
$Y^{\prime}$) of all three vertices of the triangle are incident to the same
vertex in $Y^{\prime}$.

Fix a Delsarte clique geometry $\mathcal{C}$ of $X$ . Let $v$ be a vertex of
$X$, and $C\in\mathcal{C}$ be a Delsarte clique which contains $v$, and let
$w\in N(v)\setminus C$. By Lemma 3.10, since $X(v)$ is connected,
$\psi_{1}\geq 2$. Assume that $\psi_{1}\geq 3$. Then $w$ is adjacent to at
least two vertices $v_{1}$ and $v_{2}$ in $C$ distinct from $v$. Since
$w,v_{1},v_{2}$ form a triangle in $X(v)$, the corresponding edges in the base
graph are incident to the same vertex. Similarly, for any vertex $x\in
C\setminus\\{v\\}$, the edges of the base graph that correspond to $x$,
$v_{1}$ and $v_{2}$ are incident to the same vertex. Therefore, $\\{w\\}\cup
C$ is a clique in $X$, which contradicts maximality of $C$. Therefore,
$\psi_{1}=2$.

Let $u$ and $v$ be two vertices at distance $2$ in $X$. There exist distinct
cliques $C_{1},C_{2},\ldots,C_{\tau_{2}}$ which contain $u$ and have non-
trivial intersection with $N(v)$, and distinct cliques
$C_{1}^{\prime},C_{2}^{\prime},\ldots,C_{\tau_{2}}^{\prime}$ which contain $v$
and have non-trivial intersection with $N(u)$.

Let $T=N(u)\cap N(v)$. Assume that $w_{1},w_{2}\in T$ are adjacent, but
$\\{w_{1},w_{2}\\}$ is not a subset of $C_{i}$ or $C_{i}^{\prime}$ for any
$i\in[\tau_{2}]$. Since $\psi_{1}=2$ there exists a vertex $w\in T$ such that
$\\{w,w_{1}\\}$ is a subset of some $C_{i}$. Similarly there is $w^{\prime}\in
T$ with $\\{w^{\prime},w_{1}\\}\subseteq C_{j}^{\prime}$ for some $j$. Assume
that $X(v)$ is a line graph of a triangle-free graph $Y$. Assume that edges of
$Y$ that correspond to $w_{1},w^{\prime}$ are incident with a vertex $x$ of
$Y$. If corresponding to $w_{2}$ edge is incident with $x$, then by the
argument as above, $w_{2}\in C_{j}^{\prime}$. This contradicts the choice of
$w_{2}$. Let $y$ be the vertex of $Y$ incident to the edges in $Y$
corresponding to $w_{2}$ and $w_{1}$. Since $|C_{i}\cap C_{j}^{\prime}|\leq
1$, we have $w\notin C_{j}^{\prime}$, so $w$ is not incident to $x$. Thus, $w$
is incident to $y$. Hence, $w$, $w_{1}$ and $w_{2}$ form a triangle.

Since $\\{w,w_{1}\\}\subseteq C_{i}$ and $X(u)$ is also the line graph of a
triangle-free graph we similarly get that $w_{2}\in C_{i}$. This gives a
contradiction with the choice of $w_{1},w_{2}$. Therefore, any two vertices in
$T$ are adjacent if and only if they share the same clique $C_{i}$ or
$C_{i}^{\prime}$.

We obtain that an edge between a pair of vertices in $T$ is between vertices
in $T\cap C_{i}$ or between vertices in $T\cap C_{j}^{\prime}$ for some $i,j$.
We refer to them as edges of type 1 and edges of type 2, respectively. Since
$|T\cap C_{i}|=|T\cap C_{i}^{\prime}|=\psi_{1}=2$, every vertex in $T$ is
incident with precisely one edge of type 1 and precisely one edge of type 2.
Therefore, the subgraph induced on $T$ is a union of even cycles. Hence, we
may choose an independent set $S\subseteq T$ of the size
$\frac{1}{2}|T|=\frac{1}{2}\psi_{1}\tau_{2}=\tau_{2}$ in $X$. The graph
induced on $S\cup\\{u,v\\}$ is $K_{2,\tau_{2}}$. ∎

Now we are ready to combine all the arguments into the proof of Theorem 1.2.

###### Proof of Theorem 1.2.

Denote $\displaystyle{b^{+}=\frac{b_{1}}{\theta_{1}+1}}$. Since
$\displaystyle{\varepsilon^{*}=\frac{-2-\vartheta_{1}}{-1-\vartheta_{1}}}$ the
assumptions of the theorem imply $b^{+}<-1-\vartheta_{1}$. Since $X$ is not
complete, by Lemma 2.14, $m\geq 2$. Thus $k\geq m^{3}$ and $\lambda\geq k/m-1$
implies $\lambda\geq 3$. Hence, by Proposition 3.6 and Lemma 3.8, either
$X(v)$ is a disconnected graph for some vertex $v$, or $X(v)$ is the line
graph of the complete bipartite graph $K_{s,t}$ for any vertex $v$ of $X$.

In the latter case, by Lemma 3.12, $X$ contains $K_{\tau_{2},2}$ and
$\psi_{1}=2$. Since we assumed that $b^{+}\leq-1-\vartheta_{1}<7/5$, by
Theorem 3.9, we get that $\tau_{2}\leq 2$ (as otherwise there is induced
$K_{2,3}$ subgraph). Hence, $\mu\leq 4$. By Theorem 2.21, we get that $X$ is a
Johnson graph $J(s,d)$, or a graph which can be double covered by $J(2d,d)$.
The later case is not possible as $k\geq m^{3}$.

∎

######  Remark 3.13.

We note that in the light of Remark 3.7, if we additionally assume that $k$ is
large enough, then we can replace $\varepsilon^{*}$ with $2/7$ in Theorem 1.2.
Indeed, since $\lambda\geq(k/m)-1$ and $k\geq m^{3}$, the assumption that $k$
is large enough guarantees that $\lambda$ is large enough. Hence, the proof
above will work as $b^{+}<7/5<\sqrt{2}$.

##  4 Spectral gap characterization of Hamming graphs

In this section we prove a characterization of Hamming graphs in terms of the
spectral gap and local parameters. As in the previous section, we assume that
the second largest eigenvalue of $X$ satisfies
$\theta_{1}\geq(1-\varepsilon)b_{1}$. We show that if additionally for each
vertex the neighborhood graph is a disjoint union of cliques, $\mu=2$, and
there is a dominant distance, then $X$ is a Hamming graph. Our proof strategy
relies on the following theorem.

######  Theorem 4.1 (Terwilliger [34]).

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Assume that the
second largest eigenvalue $\theta_{1}$ has multiplicity $f_{1}<k$. Then each
local graph $X(v)$ has eigenvalue $-1-b^{+}$ with multiplicity at least
$k-f_{1}$, where $\displaystyle{b^{+}=\frac{b_{1}}{\theta_{1}+1}}$.

We prove that if $X$ is not a Hamming graph, then the assumptions of Theorem
1.4 imply that the second largest eigenvalue has multiplicity at most $k-1$.
Therefore, by the theorem above, each neighborhood graph of $X$ has an
eigenvalue less than $-1$. This contradicts the assumption that each
neighborhood graph is a disjoint union of cliques.

We start by showing that for a geometric distance-regular graph the sequence
$(\tau_{i})_{i=1}^{t-1}$ is increasing if $\mu\geq 2$ and $c_{t}$ is
sufficiently small.

######  Lemma 4.2.

Let $X$ be a geometric distance-regular graph of diameter $d$, with smallest
eigenvalue $-m$. Assume that $\mu\geq 2$ and $c_{t}\leq\varepsilon k$, where
$t\leq d$ and $0<\varepsilon<1/m^{2}$. Then

$\tau_{i}<\tau_{i+1},\quad\text{for any }i=1,2,\ldots,t-2.$

###### Proof.

Recall, by Lemma 2.16,

$c_{i}=\tau_{i}\psi_{i-1},\quad\quad\displaystyle{b_{i}=(m-\tau_{i})\left(\frac{k}{m}+1-\psi_{i}\right)}.$

Hence, in particular, $\psi_{i-1}\leq c_{i}\leq c_{t}\leq\varepsilon k$, for
$i\leq t$. So for $i\leq t-1$

$(m-\tau_{i})\left(\frac{1}{m}-\varepsilon\right)k\leq
b_{i}\leq\frac{m-\tau_{i}}{m}k.$ (10)

By Lemma 3.10, a geometric distance-regular graph with $\mu\geq 2$ contains a
quadrangle. Thus, by the Terwilliger inequality (see Theorem 2.6) we have

$b_{i}\geq b_{i+1}+\lambda+2+c_{i}-c_{i+1},\text{ for }i=0,1,\ldots,d-1.$

Therefore, for $i\leq t-2$, using Eq. (10),

$\frac{m-\tau_{i}}{m}k\geq(m-\tau_{i+1})\left(\frac{1}{m}-\varepsilon\right)k+\lambda+2-\varepsilon
k.$

Since $\lambda\geq k/m-1$, for $i\leq t-2$, we get

$(m-\tau_{i})\geq(m-\tau_{i+1})-m^{2}\varepsilon+1\quad\Rightarrow\quad\tau_{i+1}\geq\tau_{i}+1-m^{2}\varepsilon.$

∎

######  Corollary 4.3.

If the assumptions of Lemma 4.2 hold for $t=d$, then $\tau_{i}<\tau_{i+1}$ for
$i\leq d-1$.

###### Proof.

By Lemma 4.2, $\tau_{i}<\tau_{i+1}$ for $i\leq d-2$. Observe, that by the
definition of $\tau_{i}$, we have $\tau_{d}=m$ and $\tau_{i}\leq m-1$ for any
$i\leq d-1$. ∎

######  Corollary 4.4.

If the assumptions of Lemma 4.2 hold for $t=d$, then

$(d-i)\left(\frac{1}{m}-\varepsilon\right)k\leq
b_{i}\leq\frac{m-i}{m}k,\quad\text{for }1\leq i\leq d-1.$

###### Proof.

Since $\tau_{1}=1$ and $\tau_{d-1}\leq m-1$, by Lemma 4.2, we have
$i\leq\tau_{i}\leq m-d+i$ for $i\leq d-1$. So the desired inequality directly
follows from Eq. (10). ∎

To get a bound on the multiplicity of the second largest eigenvalue
$\theta_{1}$ of $X$ we first prove lower bounds on the elements of the
standard sequence corresponding to $\theta_{1}$ (see Sec. 2.2).

######  Lemma 4.5.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ with
smallest eigenvalue $-m$. Let $\theta_{1}$ be its second largest eigenvalue
and $(u_{i})_{i=0}^{d}$ be the corresponding standard sequence. Assume that
$\mu\geq 2$, $\theta_{1}\geq(1-\varepsilon)b_{1}$, and $c_{t}\leq\varepsilon
k$ for some $2\leq t\leq d$, where $0<\varepsilon<1/(24m^{2})$.

Then, for $1\leq j\leq t-1$

$u_{j}\geq(1-3m^{2}\varepsilon)^{j-1}\left(\frac{m-\tau_{j}}{m-\tau_{j}+j-1}\right)\frac{\theta_{1}}{k}.$

###### Proof.

Recall that the standard sequence corresponding to the eigenvalue $\theta_{1}$
satisfies

$u_{0}=1,\qquad u_{1}=\frac{\theta_{1}}{k},\qquad
c_{i}u_{i-1}+a_{i}u_{i}+b_{i}u_{i+1}=\theta_{1}u_{i},\text{ for
}i=1,\ldots,d-1.$

We can rewrite this as

$u_{i+1}=u_{i}\frac{(\theta_{1}+b_{i}+c_{i}-k)}{b_{i}}-u_{i-1}\frac{c_{i}}{b_{i}}\geq
u_{i}\left(1-\frac{k-\theta_{1}}{b_{i}}\right)-u_{i-1}\frac{c_{i}}{b_{i}}.$
(11)

For $2\leq i\leq t$, by the assumptions of the lemma, $\psi_{i-1}\leq
c_{i}\leq c_{t}\leq\varepsilon k$. So, by Lemma 2.16,

$k-\theta_{1}\leq k-(1-\varepsilon)b_{1}\leq(k-b_{1})+\varepsilon
k\leq\frac{k}{m}+(m-1)\psi_{1}+\varepsilon k\leq\frac{k}{m}+m\varepsilon k;$
(12) $(m-\tau_{i})\left(\frac{1}{m}-\varepsilon\right)k\leq
b_{i},\quad\text{for }i\leq t-1.$ (13)

For the convenience of the future computations we first show that for $1\leq
i\leq t-2$, inequality $3u_{i+1}\geq u_{i}\geq 0$ holds. Indeed, by Eq. (12),
$u_{1}\geq\frac{1}{3}u_{0}$. Moreover, by Lemma 4.2,
$\tau_{i}\leq\tau_{t-1}-1\leq m-2$, so by Eq. (12) and Eq. (13),

$1-\frac{k-\theta_{1}}{b_{i}}\geq
1-\frac{1+m^{2}\varepsilon}{2-2m\varepsilon}\geq\frac{1}{2}-m^{2}\varepsilon.$

Thus, using $\tau_{i}\leq m-2$ for $i\leq t-2$, by induction, we get from Eq.
(11) and Eq. (13)

$u_{i+1}\geq\left(\frac{1}{2}-m^{2}\varepsilon\right)u_{i}-m\varepsilon
u_{i-1}\geq\left(\frac{1}{2}-4m^{2}\varepsilon\right)u_{i}\geq\frac{1}{3}u_{i}.$

Hence, for $i\leq t-2$, we can rewrite Eq. (11)

$u_{i+1}\geq
u_{i}\frac{(\theta_{1}+b_{i}+c_{i}-k)}{b_{i}}-3u_{i}\frac{c_{i}}{b_{i}}\geq
u_{i}\left(1-\frac{k-\theta_{1}+2\varepsilon k}{b_{i}}\right).$

Thus, using Eq. (12) and Eq. (13), for $i\leq t-2$,

$u_{i+1}\geq u_{i}\left(1-\frac{k+(m^{2}+2m)\varepsilon k}{mb_{i}}\right)\geq
u_{i}\left(1-\frac{1}{(m-\tau_{i})}\frac{(1+2m^{2}\varepsilon)}{(1-m\varepsilon)}\right)\geq
u_{i}\left(1-\frac{(1+3m^{2}\varepsilon)}{m-\tau_{i}}\right).$

By Lemma 4.2, $\tau_{i}\leq\tau_{j}-(j-i)$ for $i\leq j\leq t-1$. Thus, for
$\delta=3m^{2}\varepsilon$ and $i+1\leq j\leq t-1$,

$u_{i+1}\geq(1-\delta)\left(1-\frac{1}{m-\tau_{i}}\right)u_{i}\geq(1-\delta)\frac{m-\tau_{j}+j-i-1}{m-\tau_{j}+j-i}u_{i}.$

Therefore, for any $1\leq j\leq t-1$,

$u_{j}\geq(1-\delta)^{j-1}\prod\limits_{i=1}^{j-1}\frac{m-\tau_{j}+j-i-1}{m-\tau_{j}+j-i}u_{1}=(1-\delta)^{j-1}\left(\frac{m-\tau_{j}}{m-\tau_{j}+j-1}\right)\frac{\theta_{1}}{k}.$

∎

######  Proposition 4.6.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ with
smallest eigenvalue $-m$. Take $\displaystyle{0<\varepsilon<1/(6m^{4}d)}$.
Suppose that $\mu\geq 2$, $c_{t}\leq\varepsilon k$ and $b_{t}\leq\varepsilon
k$ for some $2\leq t\leq d$. Assume, moreover, that the second largest
eigenvalue of $X$ satisfies $\theta_{1}\geq(1-\varepsilon)b_{1}$.

Then either the multiplicity $f_{1}$ of $\theta_{1}$ satisfies $f_{1}\leq
k-1$, or $m=d$, $t=d$ and $c_{d}=d$.

###### Proof.

Let $(u_{i})_{i=0}^{d}$ be the standard sequence of $X$ corresponding to
$\theta_{1}$. Then, by the Biggs formula, multiplicity of an eigenvalue
$\theta_{1}$ can be computed as

$f_{1}=\frac{n}{\left(\sum\limits_{i=0}^{d}k_{i}u_{i}^{2}\right)}.$

Note, as in Eq. (10), $\displaystyle{b_{i-1}\geq
b_{t-1}\geq\left(\frac{1}{m}-\varepsilon\right)k}\geq\frac{1}{2m}k$ and
$c_{i}\leq c_{t}$ for any $1\leq i\leq t$. So

$k_{i-1}=\frac{c_{i}}{b_{i-1}}k_{i}\leq\frac{c_{t}}{b_{t-1}}k_{i}\leq
2m\varepsilon k_{i},\quad\text{for }i\leq t.$ (14)

For $d-1\geq i\geq t$, by Lemma 2.16, $b_{i}\leq b_{t}\leq\varepsilon k$
implies

$\displaystyle{\psi_{i}\geq\left(\frac{1}{m}-\varepsilon\right)k\geq\frac{1}{2m}k},\qquad\text{so}\qquad\displaystyle{c_{i+1}=\tau_{i+1}\psi_{i}\geq\frac{1}{2m}k}.$

Hence, for $t\leq i\leq d-1$ we deduce,

$k_{i+1}=\frac{b_{i}}{c_{i+1}}k_{i}\leq\frac{\varepsilon
k}{k/(2m)}k_{i}=2m\varepsilon k_{i}.$ (15)

Combining Eq. (14) and Eq. (15) we obtain

$n=\sum\limits_{i=0}^{d}k_{i}\leq
k_{t}\left(\sum\limits_{i=0}^{t}(2m\varepsilon)^{i}+\sum\limits_{i=1}^{d-t}(2m\varepsilon)^{i}\right)\leq\frac{1}{1-4m\varepsilon}k_{t}\qquad\Rightarrow\qquad
k_{t}\geq(1-4m\varepsilon)n.$

As in Eq. (12), $\theta_{1}/k\geq(m-1)/m-m\varepsilon$. So, by Lemma 4.5 and
Eq.(10), for $t\geq 2$,

$k_{t-1}u_{t-1}^{2}\geq
k_{t}\frac{c_{t}}{b_{t-1}}(1-3m^{2}\varepsilon)^{2t-4}\left(\frac{m-\tau_{t-1}}{m-\tau_{t-1}+t-2}\right)^{2}\left(\frac{\theta_{1}}{k}\right)^{2}\geq$
$\geq
k_{t}\frac{c_{t}}{b_{t-1}}(1-3m^{2}\varepsilon)^{2t-4}\left(\frac{m-\tau_{t-1}}{m-\tau_{t-1}+t-2}\right)^{2}(1-2m\varepsilon)^{2}\left(\frac{m-1}{m}\right)^{2}\geq$
$\geq(1-4m\varepsilon)n\cdot\frac{mc_{t}}{(m-\tau_{t-1})k}\cdot(1-3m^{2}\varepsilon)^{2d-1}\left(\frac{m-\tau_{t-1}}{m-\tau_{t-1}+t-2}\right)^{2}\left(\frac{m-1}{m}\right)^{2}\geq$
$\geq\frac{n}{k}\cdot(1-3m^{2}\varepsilon)^{2d}\cdot\frac{c_{t}}{m}\cdot\frac{(m-\tau_{t-1})(m-1)^{2}}{(m-\tau_{t-1}+t-2)^{2}}.$

Our goal is to deduce from this inequality that $k_{t-1}u_{t-1}^{2}>n/k$,
unless $c_{t}=t=m=d$. We start by giving a bound on $c_{t}$. Observe that
$\psi_{t-2}\geq 1$, and $\tau_{t-1}\geq t-1$, by Lemma 4.2. So we obtain

$c_{t}\geq c_{t-1}\geq\tau_{t-1}\psi_{t-2}\geq t-1.$ (16)

Case 1. First, assume that $c_{t}=t-1$.
Then, Eq. (16) implies $\tau_{t-1}=t-1$ and $c_{t}=c_{t-1}$. Thus, in
particular, we can simplify

$\frac{c_{t}}{m}\cdot\frac{(m-\tau_{t-1})(m-1)^{2}}{(m-\tau_{t-1}+t-2)^{2}}=\frac{t-1}{m}\cdot\frac{(m-t+1)(m-1)^{2}}{(m-1)^{2}}=\frac{(t-1)(m-t+1)}{m}.$

Also, observe that the constraint $c_{t}=c_{t-1}$ implies $t>2$ as
$1=c_{1}<2\leq\mu=c_{2}$. Moreover, by Corollary 2.8, $c_{3}>c_{2}$ for
$\mu\geq 2$, so we should have $t\geq 4$ in this case.

At the same time, $c_{t}=c_{t-1}$, using Terwilliger’s inequality (see Theorem
2.6), implies

$b_{t-1}\geq c_{t-1}-c_{t}+b_{t}+\lambda+2\geq\lambda+2\geq\frac{k}{m}+1.$

Since

$b_{t-1}=(m-\tau_{t-1})\left(\frac{k}{m}+1-\psi_{t-1}\right)\leq(m-\tau_{t-1})\frac{k}{m},$

we deduce $\tau_{t-1}\leq m-2$. So $t\leq m-1$, as $\tau_{t-1}=t-1$.

Thus $4\leq t\leq m-1$, which implies $m\geq 5$, and we get

$\frac{c_{t}}{m}\cdot\frac{(m-\tau_{t-1})(m-1)^{2}}{(m-\tau_{t-1}+t-2)^{2}}=\frac{(t-1)(m-t+1)}{m}\geq\frac{2(m-2)}{m}\geq
2-\frac{4}{m}\geq\frac{6}{5}.$

Since, $3m^{2}\varepsilon<1$, by Bernoulli’s inequality

$(1-3m^{2}\varepsilon)^{2d}\geq(1-6dm^{2}\varepsilon)>\frac{5}{6}.$

Therefore, in this case,

$k_{t-1}u_{t-1}^{2}>\frac{n}{k}\quad\Rightarrow\quad
f_{1}\leq\frac{n}{k_{t-1}u_{t-1}^{2}}<k\qquad\Rightarrow\qquad f_{1}\leq k-1.$

Case 2. Else we have $c_{t}\geq t$.
Lemma 4.2 implies $t\leq\tau_{t-1}+1\leq m$. It is not hard to check (see
Appendix A), that

$\frac{(m-\tau_{t-1})(m-1)^{2}}{(m-\tau_{t-1}+t-2)^{2}}\geq\frac{m-1}{t-1}.$
(17)

Hence, applying inequality from Eq. (17),

$k_{t-1}u_{t-1}^{2}\geq\frac{n}{k}(1-3m^{2}\varepsilon)^{2d}\frac{c_{t}}{m}\left(\frac{m-1}{t-1}\right)\geq\frac{n}{k}(1-3m^{2}\varepsilon)^{2d}\left(\frac{t}{t-1}\right)\left(\frac{m-1}{m}\right).$

If $2\leq t<m$, then

$\displaystyle{\left(\frac{t}{t-1}\right)\left(\frac{m-1}{m}\right)\geq\left(\frac{m-1}{m-2}\right)\left(\frac{m-1}{m}\right)=1+\frac{1}{m^{2}-2m}\geq
1+\frac{1}{m^{2}-1}}.$

If $2\leq t=m$, and $c_{t}>t$, then

$\displaystyle{\left(\frac{c_{t}}{t-1}\right)\left(\frac{m-1}{m}\right)\geq\left(\frac{t+1}{t-1}\right)\left(\frac{m-1}{m}\right)=\frac{m+1}{m}\geq
1+\frac{1}{m^{2}-1}}.$

In each of these two cases, we get

$k_{t-1}u_{t-1}^{2}\geq\frac{n}{k}\cdot(1-3m^{2}\varepsilon)^{2d}\left(1+\frac{1}{m^{2}-1}\right).$

By Bernoulli’s inequality, since $3m^{2}\varepsilon<1$,

$(1-3m^{2}\varepsilon)^{2d}\geq(1-6dm^{2}\varepsilon)>1-\frac{1}{m^{2}}=\left(1+\frac{1}{m^{2}-1}\right)^{-1}.$

Therefore, if $c_{t}>t$ or $m>t$, then $k_{t-1}u_{t-1}^{2}>n/k$ and so

$f_{1}\leq\frac{n}{k_{t-1}u_{t-1}^{2}}<k\qquad\Rightarrow\qquad f_{1}\leq
k-1.$

Finally, assume $\tau_{t}\psi_{t-1}=c_{t}=t$ and $m=t$. We know from Lemma 4.2
that $\tau_{t-1}\geq t-1$. If $t<d$, then $b_{t}\geq 1$. So, by Terwilliger’s
inequality and Lemma 2.16,

$\frac{k}{m}\geq(m-\tau_{t-1})\left(\frac{k}{m}+1-\psi_{t-1}\right)=b_{t-1}\geq
c_{t-1}-c_{t}+b_{t}+\lambda+2\geq\lambda+2\geq\frac{k}{m}+1,$

which gives a contradiction with the assumption $t<d$. Therefore, $t=d$ and
$c_{d}=d$, $m=d$. ∎

Now we are ready to prove Theorem 1.4 in the following equivalent form (see
Lemma 2.19).

######  Theorem 4.7.

Let $X$ be a distance-regular graph of diameter $d\geq 2$. Suppose that every
neighborhood graph $X(v)$ is a disjoint union of $m$ cliques. Moreover, assume
$\mu\geq 2$, $c_{t}\leq\varepsilon k$ and $b_{t}\leq\varepsilon k$ for some
$t\leq d$ and $\theta_{1}\geq(1-\varepsilon)b_{1}$, where
$0<\varepsilon<1/(6m^{4}d)$.

Then $X$ is a Hamming graph $H(d,s)$, for $s=1+k/d$.

###### Proof.

Pick some vertex $v$ and let $X(v)=\bigcup_{i=1}^{m}C_{i}$, where $C_{i}$ is a
clique for every $i$. Since $X$ is distance-regular, all $C_{i}$ are of the
same size $\lambda+1$. Note that $\\{v\\}\cup C_{i}$ is a maximal clique in
$X$ of the size $k/m+1$. Since $k\geq 1/\varepsilon>m^{2}$, by Proposition
2.13, $X$ is geometric with smallest eigenvalue $-m$.

Hence, by Proposition 4.6, either we have $f_{1}\leq k-1$, or $c_{d}=m=d$. If
$f_{1}\leq k-1$, by Theorem 4.1,
$\displaystyle{-1-\frac{b_{1}}{\theta_{1}+1}}$ is an eigenvalue of $X(v)$.
However, $b_{1}>0$ and $\theta_{1}>0$, so $X(v)$ has an eigenvalue less than
$-1$. This gives a contradiction with the assumption that $X(v)$ is a disjoint
union of cliques.

Therefore, $c_{d}=m=d$. By Lemma 4.2, we get $\tau_{i}\geq i$ for any
$i\in[d]$. At the same time, $d=c_{d}=\tau_{d}\psi_{d-1}$, so $\tau_{d}=d$ and
$\psi_{d-1}=1$. We immediately deduce $\tau_{i}=i$ for all $i\in[d]$. Assume
that $\psi_{i-1}\geq 2$, while $\psi_{i}=1$ for some $2\leq i\leq d-1$. Then
we get a contradiction with

$i+1=\psi_{i}\tau_{i+1}=c_{i+1}\geq c_{i}=\psi_{i-1}\tau_{i}\geq 2i.$

Thus, $\psi_{i}=1$ for every $i$. This means, that the intersection array of
$X$ coincides with the intersection array of the Hamming graph $H(d,1+k/d)$,
as

$c_{i}=i\qquad\text{and}\qquad b_{i}=(d-i)\frac{k}{d}.$

Using characterization of Hamming graphs by their intersection array (Theorem
2.24), $X$ is a Hamming graph or a Doob graph. Note that $X$ may be a Doob
graph, only if $1+k/d=4$, which is not possible as $k\geq 1/\varepsilon\geq
6d$. Therefore, $X$ is a Hamming graph. ∎

######  Corollary 4.8.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$. Suppose
that $X$ has $\mu=2$ and smallest eigenvalue $-m$. Take
$0<\varepsilon<1/(6m^{4}d)$. Assume, $c_{t}\leq\varepsilon k$ and
$b_{t}\leq\varepsilon k$ for some $t\in[d]$, and
$\theta_{1}\geq(1-\varepsilon)b_{1}$. Then $X$ is a Hamming graph $H(d,s)$.

###### Proof.

By Lemma 2.16, $\mu=\tau_{2}\psi_{1}$, and by Lemma 2.17,
$\tau_{2}\geq\psi_{1}$, so $\mu=2$ implies $\tau_{2}=2$ and $\psi_{1}=1$. This
means that a neighborhood graph of $X$ is a disjoint union of $-\theta_{d}=m$
cliques (Lemma 2.19). Therefore, the statement follows from the theorem above.

∎

##  5 Proof of Babai’s conjecture

In this section we prove Babai’s conjecture on the motion of distance-regular
graphs. We start our discussion with the elusive case $\mu=1$.

###  5.1 Geometric distance-regular graphs with $\mu=1$

In the case of $\mu=1$ our strategy is to show that the dual graph of $X$ has
linear motion and then to deduce that $X$ itself has linear motion. We use the
following Spectral tool for obtaining motion lower bounds, proved by Babai in
[3].

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$. We call quantity
$\xi=\xi(X)=\max\\{|\xi_{i}|:2\leq i\leq n\\}$ the zero-weight spectral radius
of $X$.

######  Lemma 5.1 (Babai, [3, Proposition 12]).

Let $X$ be a regular graph of degree $k$ on $n$ vertices with the 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}.$

Let $X$ be a geometric distance-regular graph with $\mu=1$ and let
$\widetilde{X}$ be its dual graph. By Lemma 2.26, every vertex in
$\widetilde{X}$ has degree $\displaystyle{\widetilde{k}=k\frac{m-1}{m}+(m-1)}$
and every pair of adjacent vertices in $\widetilde{X}$ has
$\widetilde{\lambda}=m-2$ common neighbors. Every pair of vertices at distance
two in $\widetilde{X}$ has $\widetilde{\mu}=1$ common neighbours. Indeed, if
there are at least two edges between a pair of cliques $C_{1}$ and $C_{2}$,
that do not share a vertex, then either $\psi_{1}\geq 2$ in $X$, or there is
an induced quadrangle. In both cases we get $\mu\geq 2$ and we reach a
contradiction.

Since $q(\widetilde{X})=\max(\widetilde{\mu},\widetilde{\lambda})$ is small,
we are going to show that Lemma 5.1 can be applied. For this, it is sufficient
to show that $\widetilde{X}$ has a linear in $k$ spectral gap. First, we bound
the zero-weight spectral radius of a geometric distance-regular graph using
the following lemma proven in [23].

######  Theorem 5.2 ([23, Theorem 3.11]).

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)$.

Using the relationship between the spectrum of the geometric graph $X$ and its
dual graph $\widetilde{X}$ we get the following corollary.

######  Lemma 5.3.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ with
smallest eigenvalue $-m$, where $m\geq 3$. Let $\widetilde{X}$ be its dual
graph. Let $\varepsilon=\varepsilon(d)$ and $\eta=\eta(d)\leq 1/2$ be
constants provided by Theorem 5.2. Assume $k\geq m^{2}$, $c_{t}\leq\varepsilon
k$ and $b_{t}\leq\varepsilon k$ for some $t\in[d]$. Then the zero-weight
spectral radius of $\widetilde{X}$ satisfies

$\xi(\widetilde{X})\leq\widetilde{k}(1-\eta).$

###### Proof.

Assumption $k\geq m^{2}$ implies $\widetilde{k}<k$. Let
$\widetilde{\theta}_{1}$ and $\widetilde{\theta}_{\min}$ denote the second
largest and the smallest eigenvalues of $\widetilde{X}$. Then the statement of
the lemma follows from the following two inequalities implied by Theorem 5.2
and Lemma 2.27,

$\widetilde{\theta}_{1}\leq(1-\eta)k-\frac{k}{m}+m-1=\widetilde{k}-\eta
k\leq\widetilde{k}(1-\eta),$
$\widetilde{\theta}_{\min}\geq-m-\frac{k}{m}+m-1=-\frac{k}{m}-1=-\frac{\widetilde{k}}{m-1}\geq-\widetilde{k}(1-\eta).$

∎

Thus, using Lemma 5.1 we get a linear lower bound on the motion of
$\widetilde{X}$.

######  Proposition 5.4.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ with
$\mu=1$ and smallest eigenvalue $-m$, where $m\geq 3$. Let
$\varepsilon=\varepsilon(d)$ and $\eta=\eta(d)\leq 1/2$ be constants provided
by Theorem 5.2. Assume $c_{t}\leq\varepsilon k$ and $b_{t}\leq\varepsilon k$
for some $t\in[d]$, and $k\geq\max(4m/\eta,m^{2})$. Let $\widetilde{X}$ be the
dual graph of $X$. Then

$\operatorname{motion}(\widetilde{X})\geq\frac{\eta}{2}|V(\widetilde{X})|.$

###### Proof.

Since $\mu=1$, by the discussion after Lemma 5.1, the maximal number of common
neighbors of a pair of distinct vertices is equal
$q(\widetilde{X})=\max(\widetilde{\lambda},\widetilde{\mu})=\max(m-2,1)$. Note
that $\displaystyle{\widetilde{k}\geq\frac{m-1}{m}k\geq\frac{k}{2}}$. So
$\eta\widetilde{k}\geq 2m\geq 2q(\widetilde{X})$. Hence,

$\xi(\widetilde{X})+q(\widetilde{X})\leq(1-\eta)\widetilde{k}+\frac{\eta}{2}\widetilde{k}=\left(1-\frac{\eta}{2}\right)\widetilde{k}.$

Therefore, the statement of the proposition follows from Lemma 5.1. ∎

We show that this implies that $\operatorname{motion}(X)$ is linear in
$n=|V(X)|$.

######  Lemma 5.5.

Let $\mathcal{F}$ be a collection of size-$s$ subsets of the set $\Omega$ such
that every element of $\Omega$ is in $m$ sets from $\mathcal{F}$ and any two
distinct sets in $\mathcal{F}$ intersect in precisely one element of $\Omega$.
Let $\sigma$ be a permutation of $\Omega$ which respects $\mathcal{F}$, namely
for every $C\in\mathcal{F}$ its image $\sigma(C)$ is in $\mathcal{F}$, too.
Assume that at most $\alpha|\mathcal{F}|$ sets $C\in\mathcal{F}$ are fixed by
$\sigma$, then at most
$\displaystyle{\left(\alpha+\frac{1-\alpha}{s}\right)|\Omega|}$ elements of
$\Omega$ are fixed by $\sigma$.

###### Proof.

Note that if $C\in\mathcal{F}$ is not fixed as set by $\sigma$, then
$|\sigma(C)\cap C|\leq 1$, as $\sigma(C)\in\mathcal{F}$ too. Hence, at most
one element $x\in\Omega$ of $C$ is fixed by $\sigma$.

Now let us count the number of pairs $(C,v)$, such that $v\in C$ and
$\sigma(v)\neq v$. We just argued that each of at least
$(1-\alpha)|\mathcal{F}|$ sets in $\mathcal{F}$ have $(s-1)$ elements that are
not fixed by $\sigma$. Therefore, the number of pairs we count is at least
$(1-\alpha)|\mathcal{F}|(s-1)$. Note that every element of $\Omega$ belongs to
$m$ sets in $\mathcal{F}$. Therefore, the number of elements of $\Omega$ not
fixed by $\sigma$ is at least $(1-\alpha)|\mathcal{F}|(s-1)/m$.

Using that every set in $\mathcal{F}$ has $s$ elements and every element
belongs to $m$ sets in $\mathcal{F}$, we deduce that
$s|\mathcal{F}|=m|\Omega|$. Therefore, the number of elements of $\Omega$ not
fixed by $\sigma$ is at least
$\displaystyle{(1-\alpha)\frac{(s-1)}{s}|\Omega|}$. ∎

######  Corollary 5.6.

Let $X$ be a non-complete geometric distance-regular graph on $n$ vertices and
let $\widetilde{X}$ be its dual graph on $\widetilde{n}$ vertices. Assume that
$\displaystyle{\operatorname{motion}(\widetilde{X})\geq\gamma\widetilde{n}}$,
then $\displaystyle{\operatorname{motion}(X)\geq\frac{\gamma}{2}n}$.

###### Proof.

Let $\sigma$ be a non-identity element of $\operatorname{Aut}(X)$. Then
$\sigma$ maps Delsarte cliques to Delsarte cliques. Thus $\sigma$ induces an
automorphism $\widetilde{\sigma}$ of $\widetilde{X}$. Note that if $X$ is non-
complete and geometric, then every vertex in $X$ is uniquely determined by the
set of Delsarte cliques that contain it. Hence, if $\sigma$ is non-identity,
then $\widetilde{\sigma}$ is non-identity as well. So by assumptions of the
corollary, $\widetilde{\sigma}$ fixes at most $(1-\gamma)\widetilde{n}$
vertices of $\widetilde{X}$. Using that every Delsarte clique is of size at
least 2, we get from the previous lemma that $\sigma$ fixes at most
$(1-\gamma/2)n$ vertices. ∎

We summarize the discussion of this section in the following theorem.

######  Theorem 5.7.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ on $n$
vertices. Suppose $\mu=1$ and the smallest eigenvalue of $X$ is $-m$, where
$m\geq 3$. Let $\varepsilon=\varepsilon(d)$ and $\eta=\eta(d)<1/2$ be
constants provided by Theorem 5.2. Assume $c_{t}\leq\varepsilon k$ and
$b_{t}\leq\varepsilon k$ for some $t\in[d]$, and $k\geq\max(4m/\eta,m^{2})$.
Then

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

###### Proof.

Let $\widetilde{X}$ be a dual graph of $X$ on $\widetilde{n}$ vertices. Then,
Proposition 5.4 implies
$\operatorname{motion}(\widetilde{X})\geq(\eta/2)\cdot\widetilde{n}$.
Therefore, the statement of the theorem follows from Corollary 5.6. ∎

###  5.2 Distance-regular line graphs with $\mu=1$

Note that, by Lemma 2.15, geometric distance-regular graphs with smallest
eigenvalue $-2$ are line graphs. Thus, we can use the following result of
Mohar and Shawe-Taylor [29].

######  Definition 5.8.

A distance-regular graph of diameter $d$ with parameters

$k=s(t+1),\ \lambda=s-1,\ c_{i}=1\text{ and }b_{i}=k-s\text{ (for\
$i=1,\ldots,d-1$), }c_{d}=t+1$

is called a generalized $2d$-gon of order $(s,t)$.

######  Theorem 5.9 (Mohar, Shawe-Taylor[29, Theorem 3.4]).

Suppose the line graph $L(Y)$ of a graph $Y$ is distance-regular. Then, either
$Y$ is a Moore graph, or $Y$ is a generalized $2d$-gon of order $(1,s)$ for
some $s\geq 1$, or $Y=K_{1,s}$ for $s\geq 1$.

By the Hoffman-Singleton theorem, it is known that a Moore graph is either a
complete graph, a polygon, or it is the Peterson graph ($k=3$), the Hoffman-
Singleton graph ($k=7$), or it has degree $k=57$ and diameter $d=2$.

Note that a generalized $2d$-gon of order $(1,s)$ has intersection numbers
$a_{i}=0$ for any $i\in[d]$. Thus it is bipartite. Recall, that each of two
connected components of the distance-2 graph $X_{2}$ of a bipartite distance-
regular graph $X$ is called a halved graph.

######  Fact 5.10 (see [9, Theorem. 6.5.1]).

If $X$ is a generalized $2d$-gon of order $(1,s)$, then $d$ is even and its
halved graph is a generalized $d$-gon of order $(s,s)$.

A celebrated theorem of W. Feit and G. Higman [18] asserts that apart from
polygons, generalized $2d$-gons exist only for $2d\in\\{4,6,8,12\\}$.

######  Theorem 5.11 (W. Feit, G. Higman).

A generalized $2d$-gon of order $(s,t)$ exists only for $2d\in\\{4,6,8,12\\}$
unless $s=t=1$. If $s>1$, then $2d\neq 12$.

Finally, we use the following bound on the zero-weight spectral radius of
generalized $2d$-gon of order $(s,s)$ for $2d\leq 6$.

######  Fact 5.12 ([9, Table 6.4]).

Let $X$ be a generalized $2d$-gon of order $(s,s)$ for $2d\leq 6$, $s>1$. Then
the zero-weight spectral radius of $X$ satisfies $\xi(X)\leq 2s$.

######  Proposition 5.13.

Let $X$ be a geometric distance-regular graph of diameter $d\geq 2$ on $n$
vertices. Suppose $\mu=1$, $k>4$ and the smallest eigenvalue of $X$ is $-2$.
Then

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

###### Proof.

By Lemma 2.15, $X$ is a line graph. Let $\widetilde{X}$ be the dual graph of
$X$. Thus, by Theorem 5.9, $\widetilde{X}$ is a Moore graph or a generalized
$2d$-gon of order $(1,s)$ for $s=k/2>2$. If $\widetilde{X}$ is a Moore graph,
then $\mu=1$ implies that $\widetilde{X}$ is not complete, and $k>4$ implies
$\widetilde{X}$ is not a polygon. Thus $\widetilde{X}$ is a strongly regular
graph. Hence, Theorem 1.9 implies that
$\operatorname{motion}(\widetilde{X})\geq n/8$ and the desired bound on the
motion of $X$ follows from Corollary 5.6.

Therefore, we may assume that $\widetilde{X}$ is a generalized $2d$-gon of
order $(1,s)$ for $s>2$. Then, by Fact 5.10, a halved graph $Y$ of
$\widetilde{X}$ is a generalized $d$-gon of order $(s,s)$ (and $d$ is even).
Moreover, by Theorem 5.11, $d\leq 6$ and by Fact 5.12, $\xi(Y)\leq 2s$. Note
that any pair of vertices in $Y$ has at most $q(Y)=s-1$ common neighbors.
Therefore, by Lemma 5.1,

$\operatorname{motion}(Y)\geq\frac{s(s+1)-3s}{s(s+1)}|V(Y)|\geq\frac{s-2}{s+1}|V(Y)|\geq\frac{1}{4}|V(Y)|.$

We note that $|V(\widetilde{X})|=2|V(Y)|$ and
$\operatorname{motion}(\widetilde{X})\geq\operatorname{motion}(Y)$ (see [23,
Prop. 5.5]). Therefore, the statement of the proposition follows from
Corollary 5.6. ∎

######  Remark 5.14.

We note that one can show a linear lower bound (with a worse constant) on
motion in this case without using the Feit-Higman classification theorem.
Since a dual graph $\widetilde{X}$ is bipartite or of diameter 2, one can use
Theorem 1.9 and the bounds on the motion of bipartite graphs, which we proved
in [23, Theorem 5.6 and Prop. 5.11].

###  5.3 Combining all pieces together

Finally, we combine the results of this paper and of [23] to get the proof of
Babai’s conjecture (Conjecture 1.10). From [23], in addition to Theorems 1.12
and 5.2, we need the following observation.

######  Proposition 5.15 ([23, Proposition 4.9]).

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

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

######  Theorem 5.16.

For any $d\geq 3$ there exists $\gamma_{d}>0$, such that for any primitive
distance-regular graph $X$ of diameter $d$ on $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)$.

###### Proof.

Recall, Theorem 1.12 implies that either
$\operatorname{motion}(X)\geq\gamma_{d}^{\prime}n$ for some
$\gamma_{d}^{\prime}>0$, or $X$ is geometric with smallest eigenvalue $\geq-
m_{d}$, for some $m_{d}\geq 2$.

Let $\varepsilon^{\prime}=\varepsilon(d)$ and $\eta_{d}=\eta(d)$ be the
constants provided by Theorem 5.2. Set

$0<\varepsilon=\frac{1}{2}\min\left(\frac{1}{6m_{d}^{4}d},\varepsilon^{\prime}\right)<1/200.$

Case A.

$X$ is not geometric or the smallest eigenvalue of $X$ is less than $-m_{d}$.
Then, by Theorem 1.12, $\operatorname{motion}(X)\geq\gamma_{d}^{\prime}n$.

Case B.

There exists $t\in[d]$ such that $c_{t+1}\geq\varepsilon k$ and
$b_{t}\geq\varepsilon k$.
Then, by Proposition 5.15, $\operatorname{motion}(X)\geq\varepsilon n/d$.

Case C.

$X$ is geometric with smallest eigenvalue at least $-m_{d}$ and there exists
$t\in[d]$ such that $c_{t}\leq\varepsilon k$ and $b_{t}\leq\varepsilon k$.
By Theorem 5.2, the zero-weight spectral radius of $X$ satisfies
$\xi(X)\leq(1-\eta_{d})k$.

Case C.1.

$k<\max(29,2m_{d}^{3},4m_{d}/\eta_{d})$.
Then $X$ has at most $N_{d}=\max(29,2m_{d}^{3},4m_{d}/\eta_{d})^{d}+1$
vertices. Moreover, every non-trivial automorphism moves at least 2 points, so
$\displaystyle{\operatorname{motion}(X)\geq\frac{2}{N_{d}}n}$.

Case C.2.

$k\geq\max(2m_{d}^{3},29)$ and $\mu\geq 2$.

Case C.2.i. $\theta_{1}<(1-\varepsilon)b_{1}$.
Using Corollary 2.18 we obtain,
$\displaystyle{\lambda\geq\frac{k}{m_{d}}-1\geq m_{d}^{2}\geq\mu}$. By Lemma
2.5, we have $2\lambda\leq\mu+k$, so $b_{1}\geq(k-\mu)/2\geq k/4$. Thus

$\xi(X)+q(X)\leq k-\varepsilon
b_{1}\leq\left(1-\frac{\varepsilon}{4}\right)k.$

Hence, by Lemma 5.1,
$\displaystyle{\operatorname{motion}(X)\geq\frac{\varepsilon}{4}n}$.

Case C.2.ii. $\theta_{1}\geq(1-\varepsilon)b_{1}$ and $\mu\geq 3$.
Since $\varepsilon<\frac{1}{200}<\varepsilon^{*}$, by Theorem 1.2 and
Proposition 3.11, $X$ is a Johnson graph.

Case C.2.iii. $\theta_{1}\geq(1-\varepsilon)b_{1}$ and $\mu=2$.
By Corollary 4.8, $X$ is a Hamming graph.

Case C.3.

$\mu=1$ and $k\geq\max(4m_{d}/\eta_{d},m_{d}^{2})$.

Case C.3.i. The smallest eigenvalue $-m$ of $X$ satisfies $-m\leq-3$.
Then by Theorem 5.7,
$\displaystyle{\operatorname{motion}(X)\geq\frac{\eta_{d}}{4}n}$.

Case C.3.ii. The smallest eigenvalue $-m$ of $X$ satisfies $-m>-3$.
Since, by Lemma 2.14, $m$ is integer, we get that $m\leq 2$. Hence, $m=2$, and
by Proposition 5.13 $\operatorname{motion}(X)\geq n/16$.

Therefore, the statement of the theorem holds with
$\displaystyle{\gamma_{d}=\min\left(\frac{\eta_{d}}{4},\frac{\varepsilon}{d},\frac{2}{N_{d}},\gamma_{d}^{\prime},\frac{1}{16}\right)}$.
∎

Finally, our main result on the motion, Theorem 1.11, follows from the theorem
above and the following result we proved in [23].

######  Theorem 5.17 ([23, Theorem 1.7]).

Assume Conjecture 1.10 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.

##  6 Outlook: Minimal degree of permutation groups. Coherent configurations

The study of the minimal degree of permutation groups started in the 19th
century and experienced a revival in the post-classification222We refer here
to the Classification of the Finite Simple Groups (CFSG) era.

##### Elementary results.

It seems that the minimal degree was first studied in the 1871 paper [22] by
Jordan, who proved that there are only finitely many primitive groups with any
given minimal degree $m>3$. A remarkable result of Bochert [7] (1894) asserts
that a doubly transitive permutation group of degree $n$, other than $A_{n}$
and $S_{n}$, has minimal degree at least $n/4-1$.

Lower bounds on the minimal degree impose strong structural constraints on the
group. For a group $G$, following Babai [3], by the thickness $\theta(G)$ we
mean the maximal $t$ for which the alternating group $A_{t}$ is involved in
$G$ as a quotient of a subgroup. A classical result of Wielandt [37] shows
that a linear lower bound on the minimal degree of a permutation group implies
a logarithmic upper bound on the thickness of the group.

######  Theorem 6.1 (Wielandt [37], see [2, Theorem 6.1]).

Let $n>k>\ell$ be positive integers, $k\geq 7$, and let $0<\alpha<1$. Suppose
that $G$ is a permutation group of degree $n$ and minimal degree at least
$\alpha n$. If

$\ell(\ell-1)(\ell-2)\geq(1-\alpha)k(k-1)(k-2),$

and $\theta(G)\geq k$, then $n\geq\binom{k}{\ell}$.

######  Corollary 6.2.

Let $G$ be a permutation group of degree $n$. Suppose
$\operatorname{mindeg}(G)\geq\alpha n$. Then the thickness $\theta(G)$ of $G$
satisfies $\displaystyle{\theta(G)\leq\frac{3}{\alpha}\ln(n)}$.

It is known, as a corollary of CFSG, that doubly transitive groups $G\leq
S_{n}$, other than $A_{n}$ and $S_{n}$, have order at most $n^{1+\log(n)}$
[13]. An elementary proof of a slightly weaker result was obtained by Babai
and Pyber [2], [30] using Corollary 6.2 and Bochert’s bound on minimal degree.

In light of Wielandt’s result, an immediate corollary of our Theorem 1.11 is
the following.

######  Theorem 6.3.

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

$\theta(\operatorname{Aut}(X))\leq\alpha_{d}\log n,$

or $X$ is a Johnson graph, or a Hamming graph, or a cocktail-party graph.

##### Post-classification results.

For a permutation group $G\leq\operatorname{Sym}(\Omega)$ define $G^{(k)}$ to
be the permutation group acting on the set of $k$-tuples $\binom{\Omega}{k}$
via the induced action. Using the CFSG, Liebeck and Saxl [26], [27]
characterized all primitive permutation groups with minimal degree less than
$n/3$. They showed that a group $G$ with $\operatorname{mindeg}(G)<n/3$ is of
the form $(A_{m}^{(k)})^{d}\leq G\leq S_{m}^{(k)}\wr S_{d}$, where
$S_{m}^{(k)}\wr S_{d}$ is represented in the product action on
$\binom{m}{k}^{d}$ elements. These groups are called Cameron groups, as
primitive groups of degree $n$ and order at least $n^{1+\log n}$ are of this
form, by a result of Cameron [12] based on consequences of the CFSG.

Cameron groups act on “Cameron schemes” (see below). These structures can be
seen as hybrids between Hamming and Johnson graphs.

##### Coherent configurations.

Following Schur [32] (1933), one can relate the following combinatorial
structure with a permutation group $G\leq\operatorname{Sym}(\Omega)$. Let
$R_{1},R_{2},\ldots,R_{k}$ be the orbits of the $G$-action on
$\Omega\times\Omega$ (the orbitals of $G$). The tuple
$\mathfrak{X}(G)=(\Omega,\\{R_{1},R_{2},\ldots,R_{k}\\})$ is called the
orbital configuration of $G$. The orbital configurations are a special case of
more general combinatorial structures, called coherent configurations, which
were also essentially defined in the paper of Schur and were reintroduced
later in various contexts [8], [35] (see [36]). The term “coherent
configuration” was introduced by Higman [20], who revived Schur’s program and
developed a representation theory of coherent configurations. A graph-
theoretic study of coherent configurations was initiated by Babai [1].

######  Definition 6.4.

Let $\Omega$ be a set and $\mathfrak{R}=\\{R_{1},R_{2},\ldots,R_{d}\\}$ be a
partition of $\Omega\times\Omega$ ($R_{i}\neq\emptyset$). The pair
$\mathfrak{X}=(\Omega,\mathfrak{R})$ is called a coherent configuration if the
following properties hold.

  1. 1.

For every $i\in[d]$, if $(x,x)\in R_{i}$ for some $x\in\Omega$, then
$(y,z)\notin R_{i}$ for any $y\neq z\in\Omega$.

  2. 2.

For every $i\in[d]$ there exists $i^{*}$ such that, if $(x,y)\in R_{i}$, then
$(y,x)\in R_{i^{*}}$.

  3. 3.

For every $i,j,t\in[d]$ there exists a number $p_{i,j}^{t}$, such that for any
pair $(x,y)\in R_{t}$ there exist exactly $p_{i,j}^{t}$ vertices $z\in\Omega$
such that $(x,z)\in R_{i}$ and $(z,y)\in R_{j}$.

The number $d$ of classes in the partition $\mathfrak{R}$ is called the rank
of $\mathfrak{X}$.

The Cameron schemes are the orbital configurations of the Cameron groups.
Babai conjectured that the following combinatorial analog of the Liebeck-Saxl
classification should be true.

######  Conjecture 6.5 (Babai).

There exists an $\alpha>0$ such that for any primitive coherent configuration
$\mathfrak{X}$ on the set of $n$ vertices either

$\operatorname{motion}(\mathfrak{X})\geq\alpha n,$

or $\mathfrak{X}$ is a Cameron scheme.

In the case of rank 3, this conjecture follows from Babai’s motion bound for
strongly regular graphs [3] (see Theorem 1.9) and strongly regular tournaments
[1]. We confirm this conjecture in the case of rank 4 in [24].

Distance-regular graphs give rise to a special class of coherent
configurations, in which relations are induced by the distance metric in the
graph. Specializing Conjecture 6.5 to the class of primitive distance-regular
graphs we obtain the following statement.

######  Conjecture 6.6 (Babai).

There exists an $\alpha>0$ such that for any primitive distance-regular graph
$X$ of diameter $d\geq 3$ on $n$ vertices, either

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

or $X$ is a Hamming graph, or a Johnson graph.

This conjecture is a stronger version of Conjecture 1.10 and remains open.

##  A Appendix

Below we prove the inequality used in the proof of Proposition 4.6.

######  Lemma A.1.

Let $2\leq t\leq x+1\leq m$ be integers, then

$\frac{(m-x)(m-1)^{2}}{(m-x+t-2)^{2}}\geq\frac{m-1}{t-1}.$ (18)

###### Proof.

Note that when $x=m-1$ the inequality is true, as $m-1\geq t-1$. We can
rewrite inequality (18) as

$(m-x)(m-1)(t-1)\geq(m-x+t-2)^{2},$ $m(m-1)(t-1)-x(m-1)(t-1)\geq
x^{2}-2x(m+t-2)+(m+t-2)^{2},$ $m(m-1)(t-1)-(m+t-2)^{2}\geq x(x+m(t-3)-3t+5)$
(19)

If $t\geq 4$, then $x\geq 3t-5-m(t-3)$. Indeed, for $t\geq 5$ this is true as

$x\geq t-1\geq 3t-5-2m\geq 3t-5-m(t-3),$

and for $t=4$ this holds as $x\geq t-1=3\geq 7-m$. Thus, for $t\geq 4$ the
maximal value of the RHS of inequality (19) is achieved at maximal value of
$x$, i.e., when $x=m-1$. But as noted above, inequality (18) holds for
$x=m-1$, and inequality (19) is equivalent to it.

The statement of the lemma is obvious if $t=2$. Therefore, the only case we
still need to check is $t=3$. Since the desired inequality holds for $x=m-1$,
we can assume $x\leq m-2$. In this case inequality (19) follows from

$2m(m-1)-(m+1)^{2}=m^{2}-4m+1>(m-2)^{2}-4\geq x^{2}-4\geq x^{2}-4x.$

∎

## References

  * [1] László Babai. “On the order of uniprimitive permutation groups.” Ann. Math. 113.3 (1981): 553-568.
  * [2] László Babai. “On the order of doubly transitive permutation groups.” Invent. Math 65.3 (1982): 473-484.
  * [3] 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.
  * [4] László Babai. “On the automorphism groups of strongly regular graphs II.” J. Algebra 421 (2015): 560-578.
  * [5] Sejeong Bang, Akira Hiraki, and Jacobus H. Koolen. “Delsarte clique graphs.” European J. of Combin. 28.2 (2007): 501-516.
  * [6] Norman L. Biggs “Intersection matrices for graphs.” Comb. Mathematics and its applications, Acad. Press, (1971): 15-23.
  * [7] Alfred Bochert.“Ueber die Classe der transitiven Substitutionengruppen.” Mathematische Annalen 40.2 (1892): 176-193.
  * [8] Ray C. Bose, and T. Shimamoto. “Classification and analysis of partially balanced incomplete block designs with two associate classes.” J. Amer. Statistical Assoc. 47.258 (1952): 151-184.
  * [9] Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier. “Distance-Regular Graphs.” Springer, 1989.
  * [10] Frans C. Bussemaker, and Arnold Neumaier “Exceptional graphs with smallest eigenvalue-2 and related problems.” Math. of Computation 59.200 (1992): 583-608.
  * [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] Peter J. Cameron.“Finite permutation groups and finite simple groups.” Bull. London Math. Soc. 13.1 (1981): 1-22.
  * [13] Charles W. Curtis, William M. Kantor, and Gary M. Seitz. “The 2-transitive permutation representations of the finite Chevalley groups.” Transactions of the AMS (1976): 1-59.
  * [14] Edwin R. van Dam, Jack H. Koolen, and Hajime Tanaka. “Distance-regular graphs.” Preprint arXiv:1410.6294 (2014).
  * [15] Philippe Delsarte. “An algebraic approach to the association schemes of coding theory.” Philips Res. Reports Suppls. 10 (1973): vi+-97.
  * [16] Yoshimi Egawa. “Characterization of $H(n,q)$ by the parameters.” J. Combin. Theory Ser. A  31 (1981): 108-125.
  * [17] Hikoe Enomoto. “Characterization of families of finite permutation groups by the subdegrees. II.” J. of the Faculty of Science, the Univ. of Tokyo. Sect. 1 A, 20.1 (1973): 2-11.
  * [18] Walter Feit, and Graham Higman. “The nonexistence of certain generalized polygons.” Journal of algebra 1.2 (1964): 114-131.
  * [19] Chris D. Godsil, “Algebraic Combinatorics.” Chapman and Hall Math. Ser., Chapman and Hall, New York, 1993.
  * [20] Donald G. Higman. “Coherent configurations I.” Rend. Sem. Mat. Univ. Padova 44 (1970): 1-25.
  * [21] Alan J. Hoffman. “On graphs whose least eigenvalue exceeds $-1-\sqrt{2}$.” Lin. Alg. Appl. 16 (1977): 153-166.
  * [22] Camille Jordan. “Theoremes sur les groupes primitifs.” J. Math Pures Appl. 17 (1871): 351-367.
  * [23] Bohdan Kivva. “On the spectral gap and the automorphism group of the distance-regular graphs.” Preprint arXiv:1912.10571 (2019).
  * [24] Bohdan Kivva. “On the automorphism groups of coherent configurations.” In preparation.
  * [25] Jacobus H. Koolen, and Sejeong Bang. “On distance-regular graphs with smallest eigenvalue at least $-m$.” J. of Combinatorial Theory, Ser. B 100 (2010): 573-584.
  * [26] Martin W. Liebeck. “On minimal degrees and base sizes of primitive permutation groups.” Archiv der Mathematik 43.1 (1984): 11-15.
  * [27] 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.
  * [28] Klaus Metsch. “A characterization of Grassmann graphs.” European J. Combin. 16 (1995): 639-644.
  * [29] Bojan Mohar, John Shawe-Taylor. “Distance-biregular graphs with 2-valent vertices and distance-regular line graphs.” J. Combin. Theory, Ser. B 38.3 (1985): 193-203.
  * [30] László Pyber. “On the orders of doubly transitive permutation groups, elementary estimates.” J. Combin. Theory, Ser. A 62.2 (1993): 361-366.
  * [31] Alexander Russell, and Ravi Sundaram. “A note on the asymptotics and computational complexity of graph distinguishability.” Electronic J. Combin. 5.1 (1998): 23-30.
  * [32] Issai Schur. “Zur Theorie der einfach transitiven Permutationsgruppen.” _Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-Mathematische Klasse_ , (1933): 598-623.
  * [33] Paul Terwilliger. “Distance-regular graphs with girth 3 or 4, I.” J. Combin. Theory, Ser. B, 39 (1985): 265-281.
  * [34] Paul Terwilliger. “A new feasibility condition for distance-regular graphs.” Discrete Math. 61 (1986): 311-315.
  * [35] Boris Weisfeiler, and Andrey A. Leman.“A reduction of a graph to a canonical form and an algebra arising during this reduction.” Nauchno-Technicheskaya Informatsia 2.9 (1968): 12-16.
  * [36] Boris Weisfeiler, ed. “On construction and identification of graphs.” Springer, 1976.
  * [37] 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.