\section{Introduction}

Let $\mathbb{F}_q$ be the field with $q$ elements.
For integers $e\geq d\geq 2$, define the {\it bilinear forms} graph 
$Bil_q(e\times d)$, whose vertices are all $(e\times d)$-matrices 
over $\mathbb{F}_q$ with two matrices being adjacent if and only if 
the rank of their difference is equal to $1$.

It is well known that $Bil_q(e\times d)$ is a $Q$-polynomial distance-regular 
graph with diameter $d$. (For definitions and notations see Section \ref{SectDefinitions}.) 
\smallskip

Much attention has been paid to the problem of classification 
of all $Q$-polynomial distance-regular graphs with large diameter, 
which was suggested in the fundamental monograph by Bannai and Ito \cite{BI}.
One of the steps towards the solution of this problem is a characterization of 
the known $Q$-polynomial distance-regular graphs by their intersection arrays.
(The current status of the project can be found in the survey paper \cite{SurveyDRG} 
by Van Dam, Koolen and Tanaka.) 
\smallskip

As for the bilinear forms graphs, these graphs have been characterized, 
under some additional assumption (the so-called weak 4-vertex condition), 
for $e\geq 2d\geq 6$ and $q\geq 4$ by Huang \cite{Huang}, see also \cite{FuHuangUnified},
and for $e\geq 2d+2\geq 8$ and $q\geq 2$ by Cuypers \cite{Cuypers}, 
while the strongest result was obtained by Metsch in 1999 \cite{Metsch99}, 
who showed that the bilinear forms graph $Bil_q(e\times d)$, $d\geq 3$, 
can be uniquely determined as a distance-regular graph by its intersection array 
unless one of the following cases holds: 
\begin{itemize}
\item[-] $q=2$ and $e\in \{d,d+1,d+2,d+3\}$,
\item[-] $q\geq 3$ and $e\in \{d,d+1,d+2\}$.
\end{itemize}

In this work, we show that the graph of bilinear $(d\times d)$-forms, where $d\geq 3$, 
defined over the binary field is also characterized by its intersection array 
(see Theorem \ref{theo-main}).

We remark that in the diameter two case there exist many non-isomorphic 
strongly regular graphs with the same parameters as $Bil_q(e\times 2)$. 
Indeed, the graph $Bil_q(e\times 2)$ has parameters 
\begin{equation}\label{pseudo-Latin-param}
(v,k,\lambda,\mu)=(m^2,(m-1)t,m-2+(t-1)(t-2),t(t-1)),
\end{equation}
where $m=q^e$ and $t=q+1$. 

A strongly regular graph with parameters given by Eq. (\ref{pseudo-Latin-param}) 
is usually called a pseudo Latin square graph (see \cite[Ch.~9.1.12]{BH}).
A strongly regular Latin square graph can be constructed 
from $t-2$ mutually orthogonal Latin $m\times m$-squares, 
and thus there exist exponentially many non-isomorphic strongly regular graphs with 
the same parameters given by Eq. (\ref{pseudo-Latin-param}), 
see \cite{CameronSRG} for the details.

Let us also briefly recall an idea, which was exploited in Metsch's proof \cite{Metsch99}. 
An {\it incidence structure} is a triple $(P,L,I)$ where $P$ and $L$ are sets (whose elements are 
called {\it points} and {\it lines}, respectively) and $I\subseteq P\times L$ is the 
{\it incidence relation}. 
We also assume that every line is incident with at least two points. An incidence structure 
is called {\it semilinear} (or a {\it partial linear space}) 
if there exists at most one line through any two points.
The {\it point} graph 
of the incidence structure $(P,L,I)$ is a graph defined on $P$ as the vertex set, 
with two points being adjacent if they belong to the same line.

A semilinear incidence structure can be naturally derived from the bilinear forms graph $Bil_q(e\times d)$. 
For this purpose, we recall an alternative definition of $Bil_q(e\times d)$ \cite[Chapter~9.5.A]{BCN}. 
Let $V$ be a vector space of dimension $e+d$ over $\mathbb{F}_q$, 
$W$ be a fixed $e$-subspace of $V$. 
For an integer $i\in \{d-1,d\}$, define 
\[
\mathcal{A}_i = \{U\subseteq V \mid {\rm dim}(U)=i,~ {\rm dim}(U\cap W)=0\}.
\]

Then $(\mathcal{A}_d,\mathcal{A}_{d-1},\supseteq)$ is a semilinear incidence structure 
called the $(e,q,d)$-{\it attenuated space}, while 
its point graph is isomorphic to $Bil_q(e\times d)$. 
In other words, the vertices of $Bil_q(e\times d)$ are the subspaces of $\mathcal{A}_d$, 
with two subspaces from $\mathcal{A}_d$ adjacent if and only if their intersection 
has dimension $d-1$.

Now it is easily seen that $Bil_q(e\times d)$ has two types of maximal cliques. The maximal cliques of 
the first type are the collections of subspaces of $\mathcal{A}_d$ containing a fixed subspace 
of dimension $d-1$, and each of them contains 
$\left[
\begin{matrix} 
e+1 \\ 
1
\end{matrix}
\right]_q-
\left[
\begin{matrix} 
e \\ 
1
\end{matrix}
\right]_q
=q^e$ vertices,
while the maximal cliques of the other type are the collections of subspaces of $\mathcal{A}_d$ 
contained in a fixed subspace of dimension $d+1$, and each of them contains 
$\left[
\begin{matrix} 
d+1 \\ 
1
\end{matrix}
\right]_q-
\left[
\begin{matrix} 
d \\ 
1
\end{matrix}
\right]_q
=q^d$ vertices, 
where $\left[
\begin{matrix} 
n \\ 
m
\end{matrix}
\right]_q$ denotes the $q$-ary Gaussian binomial coefficient.
Note that the maximal cliques of the first type correspond to the lines of the semilinear 
incidence structure $(\mathcal{A}_d,\mathcal{A}_{d-1},\supseteq)$.

Suppose now that a graph $\Gamma$ is distance-regular with the same intersection array as $Bil_q(e\times d)$. 
A key idea of the works by Huang \cite{Huang} and Metsch \cite{Metsch99} was as follows.
Under certain conditions on $e,d$, and $q$, it is possible to show that every edge of $\Gamma$ 
is contained in a unique clique of size $\sim q^e$, called a {\it grand} clique of $\Gamma$.
Hence $(V(\Gamma),\mathcal{L},\in)$ is a semilinear incidence structure, where 
$\mathcal{L}$ is the set of all grand cliques of $\Gamma$.
In order to show the existence of grand cliques, Huang used the so-called Bose-Laskar argument, 
which was valid for $e\geq 2d\geq 6$, and Metsch applied its improved version \cite{Metsch91}, 
which was valid under weaker assumptions on $e,q$, and $d$.
One can then show that the semilinear incidence structure 
$(V(\Gamma),\mathcal{L},\in)$ satisfies some additional properties, 
and, in fact, it is a so-called $d$-net (see \cite{Huang}).
Finally, the result by Sprague \cite{Sprague} shows, for an integer $d\geq 3$, 
every finite $d$-net is the $(e,q,d)$-attenuated space for some prime power $q$ 
and positive integer $e$, and therefore $\Gamma$ is isomorphic to $Bil_q(e\times d)$.

For the cases remained open after the Metsch result, 
it seems that the Bose-Laskar type argument cannot be applied. 
Moreover, when $e=d$, the maximal cliques of both families have the same size $q^e=q^d$. 
Therefore, even if one can show that $\Gamma$ contains such cliques, every edge is contained 
in two grand cliques. Thus, one has to prove that it is still possible to select a family of grand 
cliques that form lines of a semilinear incidence structure (when $e\neq d$, 
we can easily distinguish between families of maximal cliques by their sizes). 
However, it is not possible in general, as for example, 
it is the case for the quotient of the Johnson graph $J(2d,d)$, 
which has two families of maximal cliques of the same size, 
not being the point graph of any semilinear incidence structure, 
see \cite[Proposition~2.7,~Remark~2.8]{Cuypers92}).
\smallskip

In the present work, we will make use of a completely different approach, 
exploiting the $Q$-polynomiality of the bilinear forms graph.
Namely, suppose that $\Gamma$ is a $Q$-polynomial distance-regular graph with diameter $D\geq 3$. 
In 1993, Terwilliger (see 'Lecture note on Terwilliger algebra' edited by Suzuki, \cite{SN}) 
showed that, for $i=2,3,\ldots,D-1$, there exists 
a polynomial $T_i(\lambda)\in \mathbb{C}[\lambda]$ of degree $4$ such that for any $i$, 
any vertex $x\in \Gamma$, and any non-principal eigenvalue $\eta$ 
of the local graph $\Gamma(x)$, one has 
\begin{equation*}
T_i(\eta)\geq 0.
\end{equation*}

We call $T_i(\lambda)$ the Terwilliger polynomial of $\Gamma$.
In \cite{GavrKoolen}, the authors gave an explicit formula for this polynomial, 
and applied it to complete the classification of pseudo-partition graphs.

The Terwilliger polynomial depends only on the intersection array of $\Gamma$ 
and its $Q$-polynomial ordering (note that the property 'being $Q$-polynomial' 
is determined by the intersection array). Thus, any two $Q$-polynomial distance-regular 
graphs with the same intersection array and $Q$-polynomial ordering 
have the same Terwilliger polynomial.
\smallskip

Using this fact, we first prove the following.

\begin{res}\label{theo-localspec}
Let $\Gamma$ be a distance-regular graph with the same intersection array 
as $Bil_q(e\times d)$, $e\geq d\geq 3$.
Let $\eta$ be a non-principal eigenvalue of the local graph of a vertex $x\in \Gamma$.
Then $\eta$ satisfies
\[
-q-1\leq \eta\leq -1,\text{~or~} q^d-q-1\leq \eta\leq q^e-q-1.
\]
\end{res}

For $q=2$ and $e=d$, we prove that this information is enough to show that 
the local graphs of $\Gamma$ are the $(2^{e}-1)\times (2^{e}-1)$-grids 
(see Lemma \ref{lemma-locev-q=2}).
Thus, $\Gamma$ contains two families of maximal cliques of size $2^e$.
By the remark above, we cannot immediately derive a semilinear incidence structure from $\Gamma$.

Instead of this, applying a beautiful theorem by Munemasa and Shpectorov \cite{MunemasaShpectorov}, 
we prove a more general result (Theorem \ref{theo-main-1}), which requires distance-regularity 
of $\Gamma$ up to distance $2$ only.

\begin{theo}\label{theo-main-1}
Suppose that $\Gamma$ is a graph with diameter $d\geq 2$ and with the following intersection numbers
well-defined:
\[
b_0=nm,~b_1=(n-1)(m-1),~b_2=(n-3)(m-3),\text{~and~}c_2=6,
\]
for some integers $n,m$, $n\geq m\geq 3$, 
and such that, for every vertex $x\in \Gamma$, its local graph $\Gamma(x)$ is the $(n\times m)$-grid.
Then $\Gamma$ is isomorphic to the graph of bilinear $(e\times d)$-forms over $\mathbb{F}_2$, 
where $(n,m)=(2^e-1,2^d-1)$.
\end{theo}

We recall that the problem of characterization of all locally grid graphs is the 
well known and rather difficult one, see \cite{BBlocally4by4}. In this context, 
we believe that Theorem \ref{theo-main-1} is of independent interest.

Finally, combining Lemma \ref{lemma-locev-q=2} and Theorem \ref{theo-main-1} gives 
our main result.

\begin{theo}\label{theo-main}
Suppose that $\Gamma$ is a distance-regular graph with the same intersection array as 
$Bil_2(d\times d)$, $d\geq 3$. Then $\Gamma$ is isomorphic to $Bil_2(d\times d)$.
\end{theo}






\section{Definitions and preliminaries}\label{SectDefinitions}

In this section we recall some basic theory of distance-regular graphs.
For more comprehensive background on distance-regular graphs and association
schemes, we refer the reader to \cite{BI}, \cite{BCN}, \cite{SurveyDRG}, and \cite{SubAlgPaper}.


\subsection{Distance-regular graphs}

All graphs considered in this paper are finite, undirected and simple. 
Suppose that $\Gamma$ is a connected graph with vertex set $V(\Gamma)$ and 
edge set $E(\Gamma)$, where $E(\Gamma)$ consists of unordered pairs of  
adjacent vertices. The distance $d(x,y):=d_{\Gamma}(x,y)$ between any two vertices $x,y$ of
$\Gamma$ is the length of a shortest path connecting $x$ and $y$ in $\Gamma$. 

For a subset $X$ of the vertex set of $\Gamma$, we will also 
write $X$ for the subgraph of $\Gamma$ induced by $X$.
For a vertex $x\in \Gamma$, define $\Gamma_i(x)$ 
to be the set of vertices that are at distance precisely $i$ from $x$ ($0\leq i\leq D$),
where $D:={\rm max}\{d(x,y)\mid x,y\in \Gamma\}$ is the {\it diameter} of $\Gamma$. 
In addition, define $\Gamma_{-1}(x)=\Gamma_{D+1}(x)=\emptyset$. 
The subgraph induced by $\Gamma_1(x)$ is called the {\it neighborhood} or 
the {\it local graph} of a vertex $x$.
We often write $\Gamma(x)$ instead of $\Gamma_1(x)$ for short, and we denote $x\sim_{\Gamma} y$ 
or simply $x\sim y$ if two vertices $x$ and $y$ are adjacent in $\Gamma$. 
For a set of vertices $\{x_1,x_2,\ldots,x_s\}$ of $\Gamma$, let 
$\Gamma(x_1,x_2,\ldots,x_s)$ denote $\cap_{i=1}^s \Gamma(x_i)$.
In particular, for a pair of vertices $x,y$ of $\Gamma$ with $d(x,y)=2$, 
the graph induced on $\Gamma(x,y)$ is called the $\mu$-{\it graph} (of $x$ and $y$).

For a graph $\Delta$, a graph $\Gamma$ is called {\it locally} $\Delta$ graph 
if the local graph $\Gamma(x)$ is isomorphic to $\Delta$ for all $x\in \Gamma$.
A graph $\Gamma$ is {\it regular} with valency $k$ if 
the local graph $\Gamma(x)$ contains precisely $k$ vertices for all $x\in \Gamma$.

The {\it eigenvalues} of a graph $\Gamma$ are the eigenvalues of its adjacency matrix.
If, for some eigenvalue $\eta$ of $\Gamma$, its eigenspace contains 
a vector orthogonal to the all ones vector, we say the eigenvalue $\eta$ is {\it non-principal}.
If $\Gamma$ is regular with valency $k$, then all its eigenvalues are non-principal 
unless the graph is connected and then the only eigenvalue that is principal 
is its valency $k$.

Let $m_i$ denote the multiplicity of eigenvalue $\theta_i$, $0 \leq i\leq t$, 
of the adjacency matrix $A$ of a graph $\Gamma$, where $t$ is the number 
of distinct eigenvalues of $\Gamma$. 
Then, for a natural number $\ell$,
\begin{equation}\label{trace}
\sum_{i=0}^{t}m_i \theta_i^{\ell}= tr(A^{\ell}) = \mbox{~the~number~of~closed~walks~of~length~$\ell$~in~$\Gamma$}
\end{equation}
where $tr(A^{\ell})$ is the trace of matrix $A^{\ell}$.

Let $\Gamma$ be a graph with diameter $D$. For a pair of vertices $x,y\in \Gamma$ 
at distance $i=d(x,y)$, define 
\[
c_i(x,y):=|\Gamma(y)\cap \Gamma_{i-1}(x)|,~~ 
a_i(x,y):=|\Gamma(y)\cap \Gamma_{i}(x)|,~~ 
b_i(x,y):=|\Gamma(y)\cap \Gamma_{i+1}(x)|,
\] 
and we say that the {\it intersection numbers} $c_i$, $a_i$, or $b_i$ are {\it well-defined}, 
if $c_i(x,y)$, $a_i(x,y)$, or $b_i(x,y)$ respectively do not depend on the particular choice 
of vertices $x,y$ at distance $i$.

A connected graph $\Gamma$ with diameter $D$ is called {\it distance-regular}, 
if the intersection numbers $c_{i}$, $a_i$, and $b_{i-1}$ are well-defined 
for all $1\leq i\leq D$.
In particular, any distance-regular graph is regular with valency $k:=b_0=c_i+a_i+b_i$. 
We also define $k_i:=\frac{b_0\cdots b_{i-1}}{c_1\cdots c_i}$, $1\leq i\leq D$, 
and note that $k_i=|\Gamma_i(x)|$ for all $x\in \Gamma$ (so that $k=k_1$).
The array $\{b_0,b_1,\ldots,b_{D-1};c_1,c_2,\ldots,c_D\}$ is 
called the {\it intersection array} of the distance-regular graph $\Gamma$.

A graph $\Gamma$ is distance-regular if and only if, for all integers $h,i,j$ 
($0\leq h,i,j\leq D$), and all vertices $x,y\in \Gamma$ with $d(x,y)=h$, 
the number 
\[
p^h_{ij}:=|\{z\in \Gamma\mid d(x,z)=i,~d(y,z)=j\}|=|\Gamma_i(x)\cap \Gamma_j(y)|
\]
does not depend on the choice of $x,y$. The numbers $p^h_{ij}$ 
are called the {\it intersection numbers} of $\Gamma$.
Note that $k_i=p^0_{ii}$, $c_i=p^i_{1i-1}$, $a_i=p^i_{1i}$ ($1\leq i\leq D$), and $b_i=p^i_{1i+1}$ 
($0\leq i\leq D-1$).

Recall that the $q$-{\it ary Gaussian binomial coefficient} is defined by
\[
\left[
\begin{matrix} 
n \\ 
m
\end{matrix}
\right]_q=
\frac{(q^n-1)(q^{n-1}-1)\cdots (q^{n-m+1}-1)}{(q^m-1)(q^{m-1}-1)\cdots (q-1)}.
\]

With this notation, the following result holds, see \cite[Theorem~9.5.2]{BCN}.

\begin{res}\label{res-bil-param}
The bilinear forms graph $Bil_q(e\times d)$, $e\geq d$, is distance-regular with 
diameter $d$, $v=q^{de}$ vertices, and has intersection array given by (for $1\leq j \leq d$)
\begin{equation}\label{eq-bj-bil}
b_{j-1}=q^{2j-2}(q-1)
\left[
\begin{matrix} 
d-j+1 \\ 
1
\end{matrix}
\right]_q
\left[
\begin{matrix} 
e-j+1 \\ 
1
\end{matrix}
\right]_q,
\end{equation}
\begin{equation}\label{eq-cj-bil}
c_j=q^{j-1}
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q.
\end{equation}
\end{res}

A distance-regular graph with diameter 2 is called a {\it strongly regular} graph. 
We say that a strongly regular graph $\Gamma$ has parameters $(v,k,\lambda,\mu)$, 
if $v=|V(\Gamma)|$, $k:=b_0$, $\lambda:=a_1$, and $\mu:=c_2$.

It is well known that a strongly regular graph has the three distinct eigenvalues 
usually denoted by $k$ (the valency), and $r,s$, where $r>0>s$, 
and $r$ and $s$ are the solutions of the following quadratic equation:
\[
x^2+(\mu-\lambda)x+(\mu-k)=0.
\]

An $s$-\emph{clique} $L$ of $\Gamma$ is a complete subgraph 
(i.e., every two vertices of $L$ are adjacent) of $\Gamma$ with exactly $s$ vertices. 
We say that $L$ is a clique if it is an $s$-clique for certain $s$.

By the $(n\times m)$-{\it grid}, we mean the Cartesian product of two complete 
graphs on $n$ and $m$ vertices. The $(n\times n)$-grid is a strongly regular 
graph with parameters $(n^2,2(n-1),n-2,2)$. It is a well-known fact 
that the $(n\times n)$-grid has spectrum 
\[
[2(n-1)]^1, [n-2]^{2(n-1)}, [-2]^{(n-1)^2},
\]
where $[\theta]^m$ denotes that eigenvalue $\theta$ has multiplicity $m$.
Moreover, any graph with this spectrum is the $(n\times n)$-grid 
unless $n=4$, as the Shrikhande graph is strongly regular 
with the same parameters as the $(4\times 4)$-grid, see \cite{Shrikhande}.






\subsection{The Bose-Mesner algebra}

Let $\Gamma$ be a distance-regular graph with diameter $D$. 
For each integer $i$ ($0\leq i\leq D$), define the $i$th {\it distance matrix} $A_i$ 
of $\Gamma$ whose rows and columns are indexed by the vertex set of $\Gamma$, and, 
for any $x,y\in \Gamma$, 
\begin{equation*}
(A_i)_{x,y} = \left \{ \begin{aligned}
1\text{~if~}d(x,y)=i,\\
0\text{~if~}d(x,y)\ne i.
\end{aligned}\right.
\end{equation*}

Then $A:=A_1$ is just the {\it adjacency matrix} of $\Gamma$, 
$A_0=I$ (the identity matrix), $A_i^{\top}=A_i$ ($0\leq i\leq D$), and 
\begin{equation*}
A_iA_j=\sum_{h=0}^D p^h_{ij}A_h ~~~ (0\leq i,j\leq D),
\end{equation*}
in particular,
\begin{equation*}
AA_i=b_{i-1}A_{i-1}+a_{i}A_{i}+c_{i+1}A_{i+1} ~~~~ (1\leq i\leq D-1),
\end{equation*}
\begin{equation*}
AA_D=b_{D-1}A_{D-1}+a_{D}A_{D}, 
\end{equation*}
and this implies that $A_i=p_i(A)$ for certain polynomial $p_i$ of degree $i$. 

The {\it Bose-Mesner} algebra ${\cal M}$ of $\Gamma$ is a matrix algebra generated 
by $A$ over ${\mathbb R}$. It follows that ${\cal M}$ has dimension $D+1$, 
and it is spanned by the set of matrices $A_0=I,A_1,\ldots,A_D$, which form a basis of ${\cal M}$.

Since the algebra ${\cal M}$ is semi-simple and commutative, ${\cal M}$ also has 
a basis of pairwise orthogonal idempotents $E_0:=\frac{1}{|V(\Gamma)|}J,E_1,\ldots,E_D$ 
(the so-called {\it primitive idempotents} of ${\cal M}$) satisfying:
\begin{equation*}
E_iE_j=\delta_{ij}E_i~~(0\leq i,j\leq D),~~E_i=E_i^{\top}~~(0\leq i\leq D), 
\end{equation*}
\begin{equation*}
E_0+E_1+\cdots+E_D=I, 
\end{equation*}
where $J$ is the all ones matrix.
 
We recall that a distance-regular graph with diameter $D$ has $D+1$ distinct 
eigenvalues exactly, which can be calculated from its intersection array, see 
\cite[Section 4.1.B]{BCN}.
 
In fact, $E_j$ ($0\leq j\leq D$) is the matrix representing orthogonal projection onto 
the eigenspace of $A$ corresponding to some eigenvalue, say $\theta_j$, of $\Gamma$.
In other words, one can write
\begin{equation*}
A=\sum_{j=0}^D \theta_jE_j,
\end{equation*} 
where $\theta_j$ ($0\leq j\leq D$) are the real and pairwise distinct 
scalars, which are exactly the eigenvalues of $\Gamma$ as defined above.
We say that the eigenvalues (and the corresponding idempotents $E_0,E_1,\ldots,E_D$) 
are in {\it natural} order if $b_0=\theta_0>\theta_1>\ldots>\theta_D$.

The Bose-Mesner algebra ${\cal M}$ is also closed under entrywise (Hadamard or Schur) 
matrix multiplication, denoted by $\circ$. The matrices $A_0$, $A_1$, $\ldots$, $A_D$ 
are the primitive idempotents of ${\cal M}$ with respect to $\circ$, i.e., 
$A_i\circ A_j= \delta_{ij}A_i$, and $\sum_{i=0}^D A_i=J$. 
This implies that
\[
E_i\circ E_j=\sum_{h=0}^{D} q_{ij}^h E_h ~~~ (0\leq i,j\leq D)
\]
holds for some real numbers $q_{ij}^h$, known as the {\it Krein parameters} of $\Gamma$. 





\subsection{$Q$-polynomial distance-regular graphs}\label{intro-Qpoly}

Let $\Gamma$ be a distance-regular graph, and $E$ be one of the primitive idempotents of its Bose-Mesner algebra.
The graph $\Gamma$ is called {\it $Q$-polynomial} with respect to $E$ 
(or with respect to an eigenvalue $\theta$ of $A$ corresponding to $E$) 
if there exist real numbers $c_i^*$, $a_i^*$, $b_{i-1}^*$ ($1\leq i\leq D$) 
and an ordering of primitive idempotents 
such that $E_0=\frac{1}{|V(\Gamma)|}J$ and $E_1=E$, and
\[
E_1\circ E_i=b_{i-1}^*E_{i-1} + a_i^*E_i + c_{i+1}^*E_{i+1} ~~~ (1\leq i\leq D-1),
\]
\[
E_1\circ E_D=b_{D-1}^*E_{D-1} + a_D^*E_D.
\]

We call such an ordering of primitive idempotents (and the corresponding eigenvalues of $\Gamma$) 
$Q$-{\it polynomial}. Note that a $Q$-polynomial ordering of the eigenvalues/idempotents does not 
have to be the natural one.

Further, the {\it dual eigenvalues} of $\Gamma$ {\it associated with} $E$ 
(or with its eigenvalue $\theta$) 
are the real scalars $\theta_i^*$ ($0\leq i\leq D$) defined by 
\begin{equation*}
E=\frac{1}{|V(\Gamma)|}\sum_{i=0}^D \theta_i^* A_i.
\end{equation*} 

The Leonard theorem (\cite[Theorem~5.1]{BI}, \cite[Theorem~2.1]{SubAlgPaper}) says that 
the intersection numbers of a $Q$-polynomial distance-regular graph 
have at least one of seven possible types: $1$, $1A$, $2$, $2A$, $2B$, $2C$, or $3$.

We note that the bilinear forms graph $Bil_q(e\times d)$ is $Q$-polynomial (of type $1$)
with respect to the natural ordering of idempotents.





\subsection{Classical parameters}\label{intro-classicalparams}

We say that a distance-regular graph $\Gamma$ has {\it classical parameters} $(D,b,\alpha,\beta)$ 
if the diameter of $\Gamma$ is $D$, and the intersection numbers of $\Gamma$ 
satisfy 
\begin{equation}\label{classparamc_i}
c_i=\genfrac{[}{]}{0pt}{}{i}{1}\Big(1+\alpha\genfrac{[}{]}{0pt}{}{i-1}{1}\Big),
\end{equation}
so that, in particular, $c_2=(b+1)(\alpha+1)$, 
\begin{equation}\label{classparamb_i}
b_i=\Big(\genfrac{[}{]}{0pt}{}{D}{1}-\genfrac{[}{]}{0pt}{}{i}{1}\Big)\Big(\beta-\alpha\genfrac{[}{]}{0pt}{}{i}{1}\Big),
\end{equation}
where 
$$\genfrac{[}{]}{0pt}{}{j}{1}:=1+b+b^2+\cdots+b^{j-1}.$$

Note that a distance-regular graph with classical parameters is $Q$-polynomial, 
see \cite[Corollary 8.4.2]{BCN}. By \cite[Table~6.1]{BCN}, we have the following result.

\begin{res}\label{reslt-bilformclassparams}
The bilinear forms graph $Bil_q(e\times d)$, $e\geq d$, 
has classical parameters 
\[
(D,b,\alpha,\beta) = (d,q,q-1,q^e-1).
\]
\end{res}



\subsection{The Terwilliger polynomial}\label{Intr-terw}

In this section, we briefly recall the concept of the Terwilliger polynomial, which was 
introduced in 1993 (see 'Lecture note on Terwilliger algebra' edited by Suzuki, \cite{SN}), 
and recently studied in our paper \cite{GavrKoolen}. 
We refer the reader to \cite{GavrKoolen} for further details.

Let $\Gamma$ be a distance-regular graph. 
Let ${\mathbb V}={\mathbb R}^{V(\Gamma)}$ denote the vector space of columns, 
whose coordinates are indexed by the set $V(\Gamma)$, 
and endowed with the standard dot product
$\langle,\rangle$, where 
\begin{equation*}
\langle u,v \rangle = u^{\top}v~~~(u,v\in {\mathbb V}).
\end{equation*}

Fix any vertex $x\in \Gamma$.
For each integer $i$ ($0\leq i\leq D$), 
let $E_i^*:=E_i^*(x)$
denote a diagonal matrix with rows and columns indexed 
by $V(\Gamma)$, and defined by 
\[
(E_i^*)_{y,y}=(A_i)_{x,y
~~~ (y\in \Gamma).
\]

Note that $E_i^*E_j^*=\delta_{ij}E_i^*$, $\sum_{i=0}^DE_i^*=I$.
These matrices span the {\it dual Bose-Mesner} algebra ${\cal M}^* := {\cal M}^*(x)$ 
with respect to vertex $x$, which is called the {\it base} vertex. 
The {\it Terwilliger} (or {\it subconstituent}) algebra 
${\cal T}:={\cal T}(x)$ with respect to $x$ is the matrix algebra generated 
by ${\cal M}$ and ${\cal M}^*(x)$, see \cite{SubAlgPaper}. 
(Note that ${\cal T}(x)$ may depend on the base vertex $x$, as for example 
it is the case for the twisted Grassmann graphs, see \cite{TwistG}.)
That this algebra is semi-simple is a standard observation. 
 
Pick any 3-tuple $xyz$ of vertices of $\Gamma$ such that $y$ and $z$ are neighbours of $x$. 
We consider $x$ as a base vertex, 
and let ${\cal T}={\cal T}(x)$ denote the Terwilliger algebra with respect to $x$. 

Let $[\ell,m,n]:=[\ell,m,n]_{x,y,z}$ denote the number of vertices $u$ of $\Gamma$ 
such that $u$ is at distances $\ell$ from $x$, $m$ from $y$, and $n$ from $z$, 
respectively, i.e., $[\ell,m,n]$ denotes a {\it triple intersection number}. 
In general, $[\ell,m,n]$ depends on the choice of $x,y$, and $z$. 

It is known that vanishing of some of the Krein parameters often 
leads to non-trivial relations between triple intersection numbers, 
see, for example, \cite{JurisicCoolsaet,JurisicVidali,Urlep} and \cite[Section~6.3]{SurveyDRG}.

Most of the Krein parameters vanish when $\Gamma$ is $Q$-polynomial. 
Assuming that $\Gamma$ has a $Q$-polynomial structure and its diameter $D$ is at least $3$, 
Terwilliger \cite{KiteFree} and Dickie \cite{Dickie} showed that $[i,i-1,i-1]$ 
(also called the number of {\it kites} of length $i$ and width $j=d(y,z)\in \{1,2\}$)
can be expressed as a linear function in $[2,1,1]$ with some coefficients depending only 
on $i$, $j$, the dual eigenvalues and intersection numbers of $\Gamma$.

In the same manner, it is possible to show (see \cite[Section~3]{GavrKoolen}) 
that $[i,i+1,i+1]$ can be expressed as a linear function in $[1,2,2]$ with 
coefficients depending only on $i$, $j$, the dual eigenvalues and intersection numbers of $\Gamma$.

In terms of the Terwilliger algebra of $\Gamma$ with respect to the base vertex $x$, 
these results yield that $E_1^*A_{i-1}E_{i}^*A_{i-1}E_1^*$ and 
$E_1^*A_{i}E_{i-1}^*A_{i}E_1^*$ can be expressed as polynomials in $\widetilde{A}:=E_1^*A_1E_1^*$ 
and $\widetilde{J}:=E_1^*JE_1^*$, i.e., there exist polynomials 
$p_i^{\epsilon\delta}\in {\mathbb R}[\lambda]$, $\epsilon,\delta\in\{+,-\}$, 
which depend only on the intersection numbers of $\Gamma$ and its $Q$-polynomial ordering,  
such that 
\[
E_1^*A_{i\epsilon 1}E_i^*A_{i\delta 1}E_1^* = \alpha_{\epsilon\delta} {\widetilde{J}}+p_i^{\epsilon\delta}(\widetilde{A})
\]
for some $\alpha_{\epsilon\delta}\in {\mathbb R}$ (we also define $\widetilde{A}^0:=E_1^*$), 

With an appropriate ordering of the vertices of $\Gamma$, one can see that 
$$
\widetilde{A}=\left(
 \begin{tabular}{ll}
 $N$ & $O$\\
 $O$ & $O'$
 \end{tabular}
 \right), 
$$
where the principal submatrix $N$ is, in fact, the adjacency matrix of $\Gamma(x)$, the local graph of 
the base vertex $x$, and $O$, $O'$ are the all zeros blocks.

We now recall some facts about irreducible ${\cal T}$-modules, see \cite{SN}, cf. \cite{IH}.
A ${\cal T}$-module is a subspace $W\subset {\mathbb V}$ such that 
$Tw\in W$ for any $T\in {\cal T}$, $w\in W$.
A non-trivial ${\cal T}$-module is {\it irreducible} if it does not properly contain a non-zero 
${\cal T}$-module. Since ${\cal T}$ is semi-simple, each ${\cal T}$-module is a direct sum of 
irreducible ${\cal T}$-modules, and $\mathbb{V}$ decomposes into an orthogonal direct sum of 
irreducible ${\cal T}$-modules. 

Let $W$ be an irreducible ${\cal T}$-module. We define the {\it endpoint} 
of $W$ by ${\rm min}\{i:~E_i^*W\ne 0\}$.
An irreducible ${\cal T}$-module $W$ is called {\it thin} 
if ${\rm dim}(E_i^*W)\leq 1$ for all $i=0,1,\ldots,D$; 
the graph $\Gamma$ is called {\it thin} if, for any of its vertices $x$, 
each irreducible ${\cal T}(x)$-module is thin.  
There is a unique irreducible ${\cal T}$-module of endpoint $0$, called 
the {\it trivial} module; it is thin and has basis $\{E_i^*{\bf 1}\mid 0\leq i\leq D\}$, 
where ${\bf 1}$ is the all ones vector.

Let $U_1^*$ be the subspace of $E_1^*\mathbb{V}$, which is orthogonal to ${\bf 1}$ 
(so that $w^{\top}\widetilde{J}w=0$ for any $w\in U_1^*$).
Let $W$ be an irreducible ${\cal T}$-module of endpoint $1$. Then $E_1^*W$ 
is a one-dimensional subspace of $U_1^*$; in particular, any non-zero vector $w\in E_1^*W$ 
is an eigenvector of $\widetilde{A}$, and $W={\cal T}w$. Conversely, for an eigenvector 
$w\in U_1^*$ of $\widetilde{A}$, the subspace $W={\cal T}w$ is an irreducible ${\cal T}$-module 
of endpoint $1$. Let $a_0(W)$ denote the corresponding eigenvalue of $\widetilde{A}$. 
Note that $a_0(W)$ is a non-principal eigenvalue of the local graph of $x$.

Further, for a vector $w\in E_1^*W$, we define 
\begin{equation}\label{wi}
w_i^+=E_i^*A_{i-1}E_1^*w,~~w_i^-=E_i^*A_{i+1}E_1^*w~~(2\leq i\leq D-1).
\end{equation}

Consider the scalar product of $w_i^{\epsilon}$ and $w_i^{\delta}$, where $\epsilon,\delta\in\{+,-\}$:
\[
\langle w_i^{\epsilon},w_i^{\delta}\rangle=w^{\top}E_1^*A_{i\epsilon 1}E_i^*E_i^*A_{i\delta 1}E_1^*w=
w^{\top}E_1^*A_{i\epsilon 1}E_i^*A_{i\delta 1}E_1^*w,
\]
and hence
\begin{equation}\label{inner-prod-wi}
\langle w_i^{\epsilon},w_i^{\delta}\rangle = 
w^{\top}\big(\alpha_{\epsilon\delta} {\widetilde{J}}+p_i^{\epsilon\delta}(\widetilde{A})\big)w = 
\|w\|^2 p_i^{\epsilon\delta}(a_0(W)).
\end{equation}

The determinant of the Gram matrix of $w_i^+,w_i^-$ is non-negative:
\begin{equation}\label{DetP}
{\rm det}\left(
 \begin{tabular}{ll}
 $\langle w_i^+,w_i^+\rangle$ & $\langle w_i^+,w_i^-\rangle$\\
 $\langle w_i^+,w_i^-\rangle$ & $\langle w_i^-,w_i^-\rangle$
 \end{tabular}
 \right)\geq 0,
\end{equation}
and it follows from \cite[Lemma~63,~Lecture~34-4]{SN} that $W$ is thin if and only 
if $w_i^+,w_i^-$ are linearly dependent for every $i$, 
$2\leq i\leq D-1$. 

Define 
\begin{equation}\label{TerwPoly}
T_i(\lambda):=p_i^{++}(\lambda)p_i^{--}(\lambda)-p_i^{+-}(\lambda)^2
\end{equation}
so that, by Eq. (\ref{inner-prod-wi}), 
\begin{equation}\label{DetP2}
{\rm det}\left(
 \begin{tabular}{ll}
 $\langle w_i^+,w_i^+\rangle$ & $\langle w_i^+,w_i^-\rangle$\\
 $\langle w_i^+,w_i^-\rangle$ & $\langle w_i^-,w_i^-\rangle$
 \end{tabular}
 \right)=\|w\|^4 T_i(a_0(W)).
\end{equation}

Combining Eqs. (\ref{DetP}) and (\ref{DetP2}) gives the following result \cite[Theorem~4.2]{GavrKoolen}.

\begin{theo}\label{theo-terwpoly}
Let $\Gamma$ be a $Q$-polynomial distance-regular graph with diameter $D\geq 3$. 
Then, for any $i=2,3,\ldots,D-1$, for any vertex $x\in \Gamma$ and any non-principal eigenvalue $\eta$ 
of the local graph of $x$, $T_i(\eta)\geq 0$ holds, with equality if and only if 
$W:={\cal T}(x)w$ is a thin irreducible ${\cal T}(x)$-module of endpoint $1$, where
$w\in E_1^*\mathbb{V}$ is an eigenvector of $\widetilde{A}$ with eigenvalue $\eta=a_0(W)$.

The polynomial $T_i(\lambda)$ defined by Eq. $(\ref{TerwPoly})$ depends only on 
the intersection numbers of $\Gamma$ and its $Q$-polynomial ordering.
\end{theo}

We will call the polynomial $T_i(\lambda)$ the {\it Terwilliger polynomial} of $\Gamma$.

The following result (see \cite[Proposition~4.3]{GavrKoolen}) gives the roots of $T_i(\lambda)$ 
for distance-regular graphs with classical parameters.

\begin{prop}\label{prop-roots}
Let $\Gamma$ be a $Q$-polynomial distance-regular graph with 
classical parameters $(D,b,\alpha,\beta)$ and with diameter $D\geq 3$. 

Then the sign of the leading term coefficient of $T_i(\lambda)$ is equal to the sign of
\[
-\big(2\genfrac{[}{]}{0pt}{}{i+1}{1}-(1+b^i)\big)\big(2\genfrac{[}{]}{0pt}{}{i}{1}-(1+b^{i-1})\big),
\]
and the four roots of $T_i(\lambda)$ (for all $i=2,3,\ldots,D-1$) are
\[
\beta-\alpha-1,~~-1,~~-b-1,~~\alpha b\frac{b^{D-1}-1}{b-1}-1.
\]
\end{prop}



\subsection{The Munemasa-Shpectorov theorem}\label{sect-step-cover}

In this section, we recall the Munemasa-Shpectorov theorem (see Theorem \ref{theo-MS} below), 
which was shown in \cite[Section~7]{MunemasaShpectorov}. 

Let us recall some definitions from \cite{MunemasaShpectorov}. 
We define a {\it path} in a graph $\Gamma$ as a sequence of vertices 
$(x_0,x_1,\ldots,x_s)$ such that $x_i$ is adjacent to $x_{i+1}$ for $0\le i<s$, 
where $s$ is the length of the path. A subpath of the form $(y,x,y)$ is called a {\it return}. 
We do not distinguish paths, which can be obtained from each other by adding or removing returns. 
This gives an equivalence relation on the set of all paths of $\Gamma$. 
Equivalence classes of this relation are in a natural bijection with paths without returns.

A {\it closed path} or a {\it cycle} is a path with $x_0=x_s$. For cycles, 
we also do not distinguish the starting vertex, i.e., two cycles obtained 
from one another by a cyclic permutation of vertices are considered as equivalent.

Given two cycles $\hat{x}=(x_0,x_1,\ldots,x_s=x_0)$ and $\hat{y}=(y_0,y_1,\ldots,y_t=y_0)$ satisfying 
$x_0=y_0$, we define a cycle $\hat{x}\cdot \hat{y}=(x_0,x_1,\ldots,x_{s},y_1,\ldots,y_t)$.

Iterating this process, we say that a cycle $\hat{x}$ can be {\it decomposed} into a product 
of cycles $\hat{x}_1,\hat{x}_2,\ldots,\hat{x}_{\ell}$, whenever there are cycles $\hat{x}'$ and 
$\hat{x}_1',\hat{x}_2',\ldots,\hat{x}_{\ell}'$, 
equivalent to $\hat{x}$ and $\hat{x}_1,\hat{x}_2,\ldots,\hat{x}_{\ell}$, respectively, such that 
$\hat{x}'=\hat{x}_1'\cdot \hat{x}_2'\cdot \ldots \cdot \hat{x}_{\ell}'$.

A graph is called {\it triangulable}, if each of its cycles can be decomposed 
into a product of triangles (i.e., cycles of length $3$). 
The following lemma (see \cite[Lemma~6.2]{MunemasaShpectorov}) gives 
necessary conditions for a graph to be triangulable.

\begin{lemma}\label{lemma-triangl-necess-cond}
Let $\Gamma$ be a graph. Suppose that, for any vertex $x\in \Gamma$, 
and $y_1,y_2\in \Gamma_{j}(x)$, $j\geq 2$, the following holds.
\begin{itemize}
\item[(i)] The graph induced by $\Gamma_{j-1}(y_1)\cap \Gamma(x)$ is connected.
\item[(ii)] If $y_1$ and $y_2$ are adjacent, then 
$\Gamma_{j-1}(y_1)\cap \Gamma_{j-1}(y_2)\cap \Gamma(x)\neq \emptyset$.
\end{itemize}
Then $\Gamma$ is triangulable.
\end{lemma}

We show in Section \ref{sect-triangul} that the bilinear forms graph $Bil_q(e\times d)$ 
satisfies the conditions of Lemma \ref{lemma-triangl-necess-cond}, i.e., 
$Bil_q(e\times d)$ is triangulable.

Let $\Gamma$ and $\widetilde{\Gamma}$ be two graphs. 
Let $x$ and $\widetilde{x}$ be vertices of $\Gamma$ and $\widetilde{\Gamma}$, 
respectively. 
An isomorphism between the local graphs at $x$ and $\widetilde{x}$, say, 
\begin{equation}\label{eq-local-isomorph}
\varphi:~~\{\widetilde{x}\}\cup \widetilde{\Gamma}(\widetilde{x}) \rightarrow \{x\}\cup \Gamma(x)
\end{equation}
is called {\it extendable} if there is a bijection 
\[
\varphi':~~\{\widetilde{x}\}\cup \widetilde{\Gamma}(\widetilde{x})\cup \widetilde{\Gamma}_2(\widetilde{x}) 
\rightarrow \{x\}\cup \Gamma(x)\cup \Gamma_2(x),
\]
mapping edges to edges, such that 
$\varphi'\mid_{\{\widetilde{x}\}\cup \widetilde{\Gamma}(\widetilde{x})}=\varphi$.
In this case, $\varphi'$ is called the {\it extension} of $\varphi$. 

We say that $\Gamma$ {\it has distinct $\mu$-graphs} if $\Gamma(x,y_1)=\Gamma(x,y_2)$ 
for $y_1,y_2\in \Gamma_2(x)$ implies that $y_1=y_2$.

\begin{theo}\label{theo-MS}
Let $\Gamma$ and $\widetilde{\Gamma}$ be two graphs. 
Assume that $\Gamma$ has distinct $\mu$-graphs and the following holds.
\begin{itemize}
\item[(i)] There exists a vertex $x$ of $\Gamma$ and a vertex $\widetilde{x}$ 
of $\widetilde{\Gamma}$, and an extendable isomorphism $\varphi$ defined by Eq. (\ref{eq-local-isomorph}).
\item[(ii)] If $x,\widetilde{x}$ are vertices of $\Gamma$ and $\widetilde{\Gamma}$, respectively, 
$\varphi$ is an extendable isomorphism defined by Eq. (\ref{eq-local-isomorph}), 
$\varphi'$ its extension, and $\widetilde{y}\in \widetilde{\Gamma}(\widetilde{x})$, 
then 
\[
\varphi'\mid_{\{\widetilde{y}\}\cup \widetilde{\Gamma}(\widetilde{y})}:~~
\{\widetilde{y}\}\cup \widetilde{\Gamma}(\widetilde{y})
\rightarrow \varphi(\{\widetilde{y}\})\cup \Gamma(\varphi(\widetilde{y}))
\]
is an extendable isomorphism.
\item[(iii)] $\widetilde{\Gamma}$ is triangulable.
\end{itemize}
Then the graph $\Gamma$ is covered by $\widetilde{\Gamma}$.
\end{theo}

We will use Theorem \ref{theo-MS} in the proof of Theorem \ref{theo-main-1}.



\subsection{Semi-partial geometries}

In this section we briefly recall the notion of a semi-partial geometry 
and one characterization of a class of semi-partial geometries 
with certain parameters. For the details, we refer the reader to \cite{Debroey}.

A {\it semi-partial geometry} with parameters $(s,t,\alpha,\mu)$
is a finite incidence structure $S=(P,B,I)$ 
for which the following properties hold:
\begin{itemize}
\item[(SPG1)] if $x$ and $y$ are two distinct points, then 
there exists at most one line incident with $x$ and $y$;
\item[(SPG2)] any line is incident with $s+1$ points, $s\geq 1$;
\item[(SPG3)] any point is incident with $t+1$ lines, $t\geq 1$;
\item[(SPG4)] if a point $x$ and a line $L$ are not incident, then
there exist $0$ or $\alpha$ (with $\alpha\geq 1$) points $x_i$, and, 
respectively, $0$ or $\alpha$ lines $L_i$ such that 
$(x,L_i)\in I$, $(x_i,L_i)\in I$, $(x_i,L)\in I$ for all $i=1,\ldots,\alpha$;
\item[(SPG5)] if two points are not collinear, then there exist $\mu$ 
(with $\mu>0$) points collinear with both. 
\end{itemize}

If two points $x$ and $y$ are collinear, then we write $x\sim y$.
If $x$ and $y$ are two distinct collinear points of $S$,
then $L_{x,y}$ denotes the line of $S$, which is incident with $x$ and $y$. 

A semi-partial geometry $S=(P,B,I)$ satisfies the {\it diagonal axiom} 
if and only if, for any elements $x,y,z,u\in P$, with $x\ne y$, $x\sim y$, and $L:=L_{x,y}$, 
the following implication holds:
\[
\Big((z,L)\not\in I, (u,L)\not\in I, z\sim x, z\sim y, u\sim x, u\sim y\Big) 
\Rightarrow z\sim u.
\]

A semi-partial geometry is called {\it partial} if $\mu=(t+1)\alpha$ holds.

In Section \ref{sect-locally-grid}, we will make use of the following result 
proven in \cite[Section~10]{Debroey}.

\begin{theo}\label{theo-SPG}
Let $S=(P,B,I)$ be a semi-partial geometry with
parameters $(s,t,\alpha,\mu)$ with $\alpha>1$ and $\mu=\alpha(\alpha+1)$, 
which is not a partial geometry and which satisfies the diagonal axiom.

Then $S$ is isomorphic to the structure formed by:
\begin{itemize}
\item[-] the lines of an $n$-dimensional projective space $PG(n,q)$, 
$n\geq 4$, that have no point in common with a given 
$(n-2)$-dimensional subspace $PG(n-2,q)$ of $PG(n,q)$,
\item[-] the planes of $PG(n,q)$ that have exactly one point in common 
with $PG(n-2,q)$, 
\end{itemize}
and the natural incidence relation, so that 
\[
s=q^2-1,~~t=\frac{q^{n-1}-1}{q-1}-1,~~\alpha=q,~~\mu=q(q+1).
\]
\end{theo}

Recall that the bilinear forms graph $Bil_q(e\times d)$ can be defined (see \cite[Chapter~9.5.A]{BCN})
on the set of $d$-dimensional subspaces of the $(e+d)$-dimensional vector 
space over $\mathbb{F}_q$ that are skew to given $e$-dimensional subspace, with two 
such $d$-subspaces adjacent if their intersection has dimension $d-1$.
Taking into account this definition, we obtain the following direct consequence of Theorem \ref{theo-SPG}.

\begin{coro}\label{coro-SPG}
Let $S=(P,B,I)$ be a semi-partial geometry with
parameters $(s,t,\alpha,\mu)$ with $\alpha>1$ and $\mu=\alpha(\alpha+1)$, 
which is not a partial geometry and which satisfies the diagonal axiom.
Then $t=\frac{q^{e}-1}{q-1}-1$ holds for some prime power $q$ and natural number $e\geq 3$, 
and the point graph of $S$ is isomorphic to the bilinear forms graph $Bil_q(e\times 2)$.
\end{coro}







\section{Locally grid graphs with hexagons as $\mu$-graphs}\label{sect-locally-grid}

In this section, we prove Theorem \ref{theo-main-1}. 
For the rest of the section, we assume that $\Gamma$ is a graph satisfying 
Theorem \ref{theo-main-1}, i.e., $\Gamma$ has diameter $D\geq 2$ and the following 
intersection numbers are well-defined:
\begin{equation}\label{eq-assum-Gamma}
b_0=nm,~b_1=(n-1)(m-1),~b_2=(n-3)(m-3),\text{~and~}c_2=6,
\end{equation}
for some integers $n,m$, $n\geq m\geq 3$, 
and, for every vertex $x\in \Gamma$, the local graph $\Gamma(x)$ is the $(n\times m)$-grid.

We first need the following simple lemma, which explains the title of this section.

\begin{lemma}\label{lemma-hexmu}
For every pair of vertices $y,z\in \Gamma$ with $d(y,z)=2$, 
the graph induced on $\Gamma(y,z)$ is a $6$-gon.
\end{lemma}
{\it Proof}.\  Let $y,z\in \Gamma$ be a pair of vertices at distance 2.
Let $x\in \Gamma(y,z)$. As $\Delta:=\Gamma_1(x)$ is the $(n\times m)$-grid, 
we see that $\Delta(y,z)$ is a coclique of size 2. 
This means that $\Gamma(y,z)$ is a triangle-free graph with valency $2$, on $c_2=6$ vertices.
Thus, $\Gamma(y,z)$ is a hexagon.\hfill\vrule height .9ex width .8ex depth -.1ex



\subsection{Embedding of the bilinear forms graphs of diameter $2$ into $\Gamma$}\label{sect-step-local2}

Pick a vertex $x\in \Gamma$. 
According to the assumption of Theorem \ref{theo-main-1},
let $\{w_{ij}\}_{i=1,j=1}^{i=n,j=m}$ denote the vertex set of $\Gamma(x)$, 
where $w_{ij}\sim w_{i'j'}$ holds if and only if either $i=i'$ or $j=j'$.

Denote by $L_i$ the maximal $m$-clique of $\Gamma(x)$ 
that contains the vertices $w_{ij}$ for $j=1,\ldots,m$, 
and by $L_j^{\top}$ the maximal $n$-clique of $\Gamma(x)$ 
that contains the vertices $w_{ij}$ for $i=1,\ldots,n$.

Let $z\in \Gamma_2(x)$.
Without loss of generality, we may assume that
$\Gamma(x,z)\subset L_1\cup L_2\cup L_3$, say:
\begin{equation}\label{eq-gammaxz}
\Gamma(x,z)=\{w_{11},w_{12},w_{22},w_{23},w_{33},w_{31}\}\subset 
(\bigcup_{i=1}^3 L_i)\cap (\bigcup_{j=1}^3 L_j^{\top}).
\end{equation}

Define a subgraph $\Sigma$ of $\Gamma$ induced by the following set of vertices:
\begin{equation}\label{eq-rank2}
\{x\}\cup L_1\cup L_2\cup L_3\cup \{y\in \Gamma_2(x)\mid \Gamma(x,y)\subset 
L_1\cup L_2\cup L_3\},
\end{equation}
so that $z\in \Sigma$, $\Sigma(x)=L_1\cup L_2\cup L_3$, and 
the local graph induced on $\Sigma(x)$ is the $(3\times m)$-grid.

Similarly, one can define a subgraph $\Sigma^{\top}$ of $\Gamma$ induced on:
\begin{equation}\label{eq-rank2-top}
\{x\}\cup L_1^{\top}\cup L_2^{\top}\cup L_3^{\top}\cup \{y\in \Gamma_2(x)\mid \Gamma(x,y)\subset 
L_1^{\top}\cup L_2^{\top}\cup L_3^{\top}\}.
\end{equation}

The aim of this section is to show the following lemma.

\begin{lemma}\label{lemma-bil2} 
There exist natural numbers $e\geq 2$ and $d\geq 2$ such that:
\begin{itemize}
\item[$(1)$] $m=2^d-1$ holds, and the graph $\Sigma$ is isomorphic to 
the bilinear forms graph $Bil_2(d\times 2)$,
\item[$(2)$] $n=2^e-1$ holds, and the graph $\Sigma^{\top}$ is isomorphic to 
the bilinear forms graph $Bil_2(e\times 2)$.
\end{itemize}
\end{lemma}

We only prove the first statement of Lemma \ref{lemma-bil2}, 
since exactly the same argument shows the second one.
We first show some claims.

\begin{claim}\label{claim-1}
With vertices $x$ and $z$ chosen as above, the following holds:
\begin{equation}\label{eq-gamma2z}
\Gamma_2(z)\cap \Gamma(x)=\big(\bigcup_{i=1}^3 (L_i\cup L_i^{\top})\big)\setminus 
\Gamma(x,z),
\end{equation}
\begin{equation}\label{eq-gamma3z}
\Gamma_3(z)\cap \Gamma(x)=\Gamma(x)\setminus \big(\bigcup_{i=1}^3 (L_i\cup L_i^{\top})\big).
\end{equation}
\end{claim}
{\it Proof}.\  Clearly, we see that 
$\Gamma_3(z)\cap \Gamma(x)\subseteq \Gamma(x)\setminus \big(\bigcup_{i=1}^3 (L_i\cup L_i^{\top})\big)$.
Now Eqs. (\ref{eq-gamma2z}) and (\ref{eq-gamma3z}) follow as 
$|\Gamma(x)\setminus \big(\bigcup_{i=1}^3 (L_i\cup L_i^{\top})\big)|=(n-3)(m-3)$, 
and $b_2=(n-3)(m-3)$ holds by Eq. (\ref{eq-assum-Gamma})
\hfill\vrule height .9ex width .8ex depth -.1ex
\medskip

It is easily seen that each of the following sets of vertices:
\begin{align}
M_1&:=\{w_{11},w_{31}\}\cup \{y\in \Gamma(z)\cap \Gamma_2(x)\mid \{w_{11},w_{31}\}\subseteq \Gamma(x,y,z)\},\label{eq-cliquem1}
\\
M_2&:=\{w_{12},w_{22}\}\cup \{y\in \Gamma(z)\cap \Gamma_2(x)\mid \{w_{12},w_{22}\}\subseteq \Gamma(x,y,z)\},\label{eq-cliquem2}
\\
M_3&:=\{w_{23},w_{33}\}\cup \{y\in \Gamma(z)\cap \Gamma_2(x)\mid \{w_{23},w_{33}\}\subseteq \Gamma(x,y,z)\}\label{eq-cliquem3}
\end{align}
induces a maximal $m$-clique of $\Gamma(z)$.

\begin{claim}\label{claim-2}
Let $y$ be a vertex of $\Gamma(z)\cap \Gamma_2(x)$. 
Then $\Gamma(y,x)\subset L_1\cup L_2\cup L_3$ holds if and only if 
$y\in M_i\setminus \Gamma(x,z)$ for some $i\in \{1,2,3\}$.
\end{claim}
{\it Proof}.\  
We first prove the ``if'' part.
Suppose that $y$ is a vertex of $\Gamma(z)\cap \Gamma_2(x)$ such that, 
without loss of generality, $\{w_{11},w_{31}\}\subseteq \Gamma(x,y,z)$, i.e., 
$y\in M_1$ by Eq. (\ref{eq-cliquem1}). 
Note that the graph induced on $\Gamma(x,y,z)$ consists of an edge or of two disjoint edges.

Suppose that $\Gamma(x,y,z)=\{w_{11},w_{31}\}$. 
Then $y\sim w_{1j}$ for some $j>1$ and $j\ne 2$. 
If $j>3$ then $\Gamma(x,y)\subset L_1\cup L_2\cup L_3$ holds by 
$\Gamma(x,y)\subset \Gamma(z)\cup \Gamma_2(z)$ and Eq. (\ref{eq-gamma3z}).
If $j=3$ then $y\sim w_{i3}$ for some $i>3$, and, further, 
$y\sim w_{i2}$ and $y\sim w_{32}$. But then the subgraph induced by $\Gamma(y,w_{12})$ 
contains a 2-claw $\{w_{11}; z,w_{13}\}$ and an edge $\{w_{32},w_{i2}\}$, 
which is disjoint from the 2-claw. This contradicts the fact that 
$\Gamma(y,w_{12})$ induces a 6-gon by Lemma \ref{lemma-hexmu}.

The case when $\Gamma(x,y,z)$ consists of two disjoint edges 
can be considered in the same manner. (In this case we also have 
$\Gamma(x,y)\subset (\bigcup_{i=1}^3 L_i)\cap (\bigcup_{i=1}^3 L_i^{\top})$.)

Now the ``only if'' part is easily seen if we interchange $z$ and $x$, 
and assuming that $y\in \Gamma(x)\cap \Gamma_2(z)$. 
Then the assertion follows from Claim \ref{claim-1} and the argument 
proving the ``if'' part.\hfill\vrule height .9ex width .8ex depth -.1ex

\begin{claim}\label{claim-sigmaz}
The graph induced on $\Sigma(z)$ is the $(3\times m)$-grid.
\end{claim}
{\it Proof}.\  It follows immediately from Claim \ref{claim-2}.\hfill\vrule height .9ex width .8ex depth -.1ex

\begin{claim}\label{lemma-muzw}
The graph induced on $\Sigma(z,w)$ is a $6$-gon for all 
$w\in \Sigma(x)$ such that $w\not\sim z$.
\end{claim}
{\it Proof}.\  Suppose that $w\in L_i$ for some $i\in \{1,2,3\}$. 
Applying Claim \ref{claim-2} to the tuple $(w, z, x, L_i)$ in the role of $(y,x,z,M_i)$, 
we obtain that $\Gamma(w,z)\subset M_1\cup M_2\cup M_3=\Sigma(z)$, i.e., 
$\Gamma(w,z)=\Sigma(w,z)$, and the claim follows. \hfill\vrule height .9ex width .8ex depth -.1ex

\begin{claim}\label{claim-muyz}
The graph induced on $\Sigma(y,z)$ is a $6$-gon for all $y\in \Sigma$, $y\not\sim z$. 
\end{claim}
{\it Proof}.\  
By Claim \ref{lemma-muzw}, we may assume that $y\in \Sigma_2(x)$ and $y\not\sim z$.
Note that $\Gamma(x,y,z)$ consists of mutually non-adjacent vertices 
(as otherwise, for some vertex $w\in \Gamma(x,y,z)$, 
the subgraph induced by $\Gamma(w)$ contains a $3$-claw, 
which is impossible). 
Thus, $0\leq |\Gamma(x,y,z)|\leq 3$.

If $|\Gamma(x,y,z)|=3$, then it easily seen that $\Gamma(z,y)\subset M_1\cup M_2\cup M_3=\Sigma(z)$,
since $\Gamma(z,y)$ contains a vertex from each of cliques $M_1,M_2,M_3$.

Suppose that $|\Gamma(x,y,z)|\in \{0,1,2\}$.
Then there is an edge, say $\{w,w'\}\subset \Gamma(x,y)\setminus \Gamma(x,z)$ 
such that $w\in L_p$, $w'\in L_q$ for some distinct $p,q\in \{1,2,3\}$.

It follows from Claim \ref{lemma-muzw} that 
\begin{equation*}
\Gamma(z,w)=\Sigma(z,w)\subset M_1\cup M_2\cup M_3\text{~and~}
\Gamma(z,w')=\Sigma(z,w')\subset M_1\cup M_2\cup M_3.
\end{equation*}

Let $N_1,N_2,N_3$ be three maximal and pairwise disjoint $m$-cliques of $\Gamma(w)$ 
such that $\Gamma(z,w)\subset N_1\cup N_2\cup N_3$ and, say, 
$N_p=L_p\cup \{x\}\setminus \{w\}$, where $L_p\ni w$.

Applying Claim \ref{claim-2} to the tuple 
$(z,w,\{M_i\}_{i=1}^3,\{N_i\}_{i=1}^3,w')$ in 
the role of $(x,z,\{L_i\}_{i=1}^3,\{M_i\}_{i=1}^3,y)$ 
shows that $w'\in N_{\ell}$ for some $\ell\in \{1,2,3\}\setminus \{p\}$.



As the local graphs of $\Gamma$ are the $(n\times m)$-grids, 
the vertex $w'$ belongs to two maximal cliques of sizes $n$ and $m$ 
of the local graph $\Gamma(w)$, one of which contains $y$, and 
the other one contains $x$ (and has size $n$). 
The latter is distinct from $N_p$, and it intersects $N_p$ in $x$.
Hence the former is $N_{\ell}$, and thus $y\in N_{\ell}$.
Now applying Claim \ref{claim-2} to the tuple 
$(z,w,\{M_i\}_{i=1}^3,\{N_i\}_{i=1}^3,y)$ in 
the role of $(x,z,\{L_i\}_{i=1}^3,\{M_i\}_{i=1}^3,y)$ 
shows that $\Gamma(y,z)\subset M_1\cup M_2\cup M_3$ 
and $\Gamma(z,y)=\Sigma(z,y)$.
This proves the claim.\hfill\vrule height .9ex width .8ex depth -.1ex

{\it Proof of Lemma \ref{lemma-bil2}:}
Claims \ref{claim-2}, \ref{claim-sigmaz}, \ref{lemma-muzw}, \ref{claim-muyz}
show that $\Sigma$ is a geodetically closed subgraph of $\Gamma$ 
with diameter $2$, and $|\Sigma(y,z)|=6$ for every pair of non-adjacent vertices $y,z\in \Sigma$, 
and, for every vertex $z\in \Sigma$, the local graph $\Sigma(z)$ is the $(3\times m)$-grid.
Therefore $|\Sigma(y,z)|=m+1$ for every pair of adjacent vertices $y,z\in \Sigma$. 
This yields that $\Sigma$ is a strongly regular graph with parameters 
$(k,\lambda,\mu)=(3m,m+1,6)$.

If $m=3$, then $\Sigma$ has parameters $(16,9,4,6)$. There are only two graphs 
with this parameter set (see \cite{Shrikhande}), namely, the complement to 
the $(4\times 4)$-grid, and the complement to the Shrikhande graph. 
The latter one has $\mu$-graphs that are not hexagons. The former one is 
isomorphic to the bilinear forms graph $Bil_2(2\times 2)$. 
Hence, in this case, $\Sigma$ is isomorphic to $Bil_2(2\times 2)$.

Further, we assume that $m>3$.
Let $P$ denote the vertex set of $\Sigma$, $B$ denote the set of all maximal $4$-cliques of $\Sigma$. 
Then ${\cal G}=(P,B,\in)$ is a semi-partial geometry 
with parameters $(s,t,\alpha,\mu)=(3,m-1,2,6)$, 
which is not a partial geometry, as $m>3$. 
Moreover, one can see that ${\cal G}$ satisfies the diagonal axiom.
Therefore, by Theorem \ref{theo-SPG} and Corollary \ref{coro-SPG}, we have that 
\[
s=q^2-1,~~t=\frac{q^{d}-1}{q-1}-1~~(\text{for some~}d\geq 3),~~\alpha=q,~~\mu=q(q+1),
\]
thus, $q=2$, and the point graph of ${\cal G}$, i.e., the graph $\Sigma$, 
is isomorphic to the bilinear forms graph $Bil_2(d\times 2)$.
The lemma is proved.\hfill\vrule height .9ex width .8ex depth -.1ex		
\medskip





\subsection{Balls of radius $2$ in $\Gamma$}\label{sect-step3}

In this section, we follow the notation from Section \ref{sect-step-local2}.
Using Lemma \ref{lemma-bil2}, we shall show that any ball of radius $2$ in $\Gamma$ 
is isomorphic to a ball of radius $2$ in the bilinear forms graph 
$\widetilde{\Gamma}:=Bil_2(e\times d)$. 

\begin{lemma}\label{lemma-bil3}
The graphs induced on $\{x\}\cup \Gamma(x)\cup \Gamma_2(x)$ and on 
$\{\widetilde{x}\}\cup \widetilde{\Gamma}(\widetilde{x})\cup \widetilde{\Gamma}_2(\widetilde{x})$ 
are isomorphic, for any vertices $x\in \Gamma$ and $\widetilde{x}\in \widetilde{\Gamma}$.
\end{lemma}

We first prove some preliminary claims. 
By Lemma \ref{lemma-bil2}, we have that $m=2^d-1$ and $n=2^e-1$.
As in Section \ref{sect-step-local2}, we pick a vertex $x\in \Gamma$, 
and let $\{L_i\}_{i=1}^{2^e-1}$, $\{L_j^{\top}\}_{j=1}^{2^d-1}$ 
be the sets of the maximal cliques of $\Gamma(x)$, 
and $\Gamma(x)=\{w_{ij}\}_{i=1,j=1}^{i=2^e-1,j=2^d-1}$, where $\{w_{ij}\}=L_i\cap L_j^{\top}$. 

Recall that, by Lemma \ref{lemma-hexmu}, for a vertex $y\in \Gamma_2(x)$,
the subgraph induced by $\Gamma(x,y)$ is a 6-gon, say, 
$\Gamma(x,y)=\{w_{i_t,j_t}\mid t=1,2,\ldots,6\}$. 
Let $\mu_x(y)$ denote the set of pairs $(i,j)$ such that 
$\{w_{ij}\mid (i,j)\in \mu_x(y)\}=\Gamma(x,y)$.

We shall show that the adjacency between vertices in $\Gamma_2(x)$ is determined 
by the intersection of their images under the mapping $\mu_{x}$. We further show 
that, for any vertex $x\in \Gamma$ and any vertex $\widetilde{x}\in \widetilde{\Gamma}$, 
the mappings $\mu_{x}$ and $\mu_{\widetilde{x}}$ can be chosen 
in such a way that the sets of their images coincide, which in turn implies Lemma \ref{lemma-bil3}.

\begin{claim}\label{claim-ball-1}
For $y,z\in \Gamma_2(x)$, $y\sim z$ holds if and only if 
\[
\Gamma(x,y,z):=\{w_{ij}\mid (i,j)\in \mu_{x}(y)\cap \mu_{x}(z)\}
\]
induces either an edge or two disjoint edges in $\Gamma(x)$.
\end{claim}
{\it Proof}.\  The claim follows from Claims \ref{claim-1}, \ref{claim-2}, and 
the fact that the adjacency between vertices of the set $\{w_{ij}\}_{i=1,j=1}^{i=n,j=m}$ 
is determined by their indices
\hfill\vrule height .9ex width .8ex depth -.1ex

We call a triple of indices $\{i,j,\ell\}$ a {\it block} or a $\top$-{\it block} if 
there exists a vertex $z\in \Gamma_2(x)$ such that $\Gamma(x,z)\subset L_i\cup L_j\cup L_{\ell}$ 
or $\Gamma(x,z)\subset L_i^{\top}\cup L_j^{\top}\cup L_{\ell}^{\top}$, respectively.
By ${\cal B}_{\Gamma,x}$ (${\cal B}^{\top}_{\Gamma,x}$, respectively) we denote the set 
of all ($\top$-)blocks.

For a block $\{i,j,\ell\}$ and a $\top$-block $\{r,s,t\}$, 
by $H^{\{i,j,\ell\}}_{\{r,s,t\}}$ we denote the set of all sets $\sigma$
consisting of pairs $(i,j)$ such that the set $\{w_{ij}\mid (i,j)\in \sigma\}$ 
induces a 6-gon in the $(3\times 3)$-grid induced by 
$(L_i\cup L_j\cup L_{\ell})\cap (L_r^{\top}\cup L_s^{\top}\cup L_t^{\top})$.

\begin{claim}\label{claim-ball-2}
The following holds:
\[
\{\mu_{x}(y)\mid y\in \Gamma_2(x)\} = \{H^{\{i,j,\ell\}}_{\{r,s,t\}} \mid 
\{i,j,\ell\}\in {\cal B}_{\Gamma,x}, \{r,s,t\}\in {\cal B}^{\top}_{\Gamma,x}\}.
\]
\end{claim}
{\it Proof}.\  We note that the intersection $\Sigma':=\Sigma_1\cap \Sigma_2$ of 
the graphs induced by 
\[
\Sigma_1:=\{x\}\cup L_i\cup L_j\cup L_{\ell}\cup \{y\in \Gamma_2(x)\mid \Gamma(x,y)\subset 
L_i\cup L_j\cup L_{\ell}\}
\]
and 
\[
\Sigma_2:=\{x\}\cup L_r^{\top}\cup L_s^{\top}\cup L_t^{\top}\cup \{y\in \Gamma_2(x)\mid \Gamma(x,y)\subset 
L_r^{\top}\cup L_s^{\top}\cup L_t^{\top}\}
\]
is isomorphic to the bilinear forms graph $Bil_2(2\times 2)$, which has 
parameters $(16,9,4,6)$ and is locally the $(3\times 3)$-grid graph. 
The $(3\times 3)$-grid contains exactly six 6-gons, and there are exactly 
$16-9-1=6$ vertices of $\Sigma'$ at distance 2 from $x$.
For a vertex $y\in \Sigma'$ at distance 2 from $x$, the set 
of common neighbours of $x$ and $y$ in $\Sigma'$ clearly coincides with $\Gamma(x,y)$
and therefore induces a 6-gon. On the other hand, the set $\mu_{x}(y)$ 
uniquely determines a block $\{i,j,\ell\}$ and a $\top$-block $\{r,s,t\}$ 
such that $\mu_{x}(y)\in H^{\{i,j,\ell\}}_{\{r,s,t\}}$.
This shows the claim.\hfill\vrule height .9ex width .8ex depth -.1ex
\medskip

We now pick a vertex $\widetilde{x}\in \widetilde{\Gamma}$,  
and let $\{\widetilde{L}_i\}_{i=1}^{2^e-1}$, $\{\widetilde{L}_j^{\top}\}_{j=1}^{2^d-1}$ be 
the sets of the maximal cliques of $\widetilde{\Gamma}(\widetilde{x})$.
As above, we define the sets ${\cal B}_{\widetilde{\Gamma},\widetilde{x}}$ and 
${\cal B}_{\widetilde{\Gamma},\widetilde{x}}^{\top}$.

\begin{claim}\label{claim-ball-3}
There exist permutations $\pi$ acting on the set $\{1,2,\ldots,2^e-1\}$
and $\pi_{\top}$ acting on the set $\{1,2,\ldots,2^d-1\}$ such that 
\[
\pi({\cal B}_{\widetilde{\Gamma},\widetilde{x}})={\cal B}_{\Gamma,x},\text{~~and~~} 
\pi_{\top}({\cal B}_{\widetilde{\Gamma},\widetilde{x}}^{\top})={\cal B}_{\Gamma,x}^{\top},
\]
where $\pi({\cal B}_{\bullet})=\{\pi(b)\mid b\in {\cal B}_{\bullet}\}$.
\end{claim}
{\it Proof}.\  
Without loss of generality, we may assume that $\{1,2,3\}$ is an element of 
all four sets ${\cal B}_{\widetilde{\Gamma},\widetilde{x}}$, ${\cal B}_{\Gamma,x}$, 
${\cal B}_{\widetilde{\Gamma},\widetilde{x}}^{\top}$, and ${\cal B}_{\Gamma,x}^{\top}$.
By Lemma \ref{lemma-bil2}, the graphs induced by 
\[
\Sigma:=\{x\}\cup L_1\cup L_2\cup L_3\cup \{y\in \Gamma_2(x)\mid \Gamma(x,y)\subset 
L_1\cup L_2\cup L_3\}
\]
and 
\[
\widetilde{\Sigma}:=\{\widetilde{x}\}\cup \widetilde{L}_1\cup \widetilde{L}_2\cup \widetilde{L}_3\cup \{\widetilde{y}
\in \widetilde{\Gamma}_2(\widetilde{x})\mid \widetilde{\Gamma}(\widetilde{x},\widetilde{y})\subset 
\widetilde{L}_1\cup \widetilde{L}_2\cup \widetilde{L}_3\}
\]
are isomorphic. Since every subgraph induced on $\Gamma(x,y)$ for $y\in \Gamma_2(x)$ 
(or on $\widetilde{\Gamma}(\widetilde{x},\widetilde{y})$ for $\widetilde{y}\in \widetilde{\Gamma}_2(\widetilde{x})$) 
uniquely determines a block and a $\top$-block, 
the isomorphism between
$\Sigma$ and $\widetilde{\Sigma}$ defines the permutation $\pi_{\top}$.
The same argument applied to $\{1,2,3\}$ as a $\top$-block shows the existence of $\pi$, 
and thus the claim follows.\hfill\vrule height .9ex width .8ex depth -.1ex

{\it Proof of Lemma \ref{lemma-bil3}:} 
By Claims \ref{claim-ball-3} and \ref{claim-ball-2}, we may assume that 
\begin{equation}\label{eq-iso}
\{\mu_{x}(y)\mid y\in \Gamma_2(x)\} = 
\{\mu_{\widetilde{x}}(\widetilde{y})\mid \widetilde{y}\in \widetilde{\Gamma}_2(\widetilde{x})\}
\end{equation}
holds. The lemma now follows from Claim \ref{claim-ball-1}.\hfill\vrule height .9ex width .8ex depth -.1ex

Now we can precisely describe an extendable (in the sense of Section \ref{sect-step-cover}) 
isomorphism $\varphi$ between the local graphs at $x$ and $\widetilde{x}$: 
\[
\varphi:~~\{\widetilde{x}\}\cup \widetilde{\Gamma}(\widetilde{x}) \rightarrow \{x\}\cup \Gamma(x)
\]
with its extension $\varphi'$, i.e., a bijection:
\[
\varphi':~~\{\widetilde{x}\}\cup \widetilde{\Gamma}(\widetilde{x})\cup \widetilde{\Gamma}_2(\widetilde{x}) 
\rightarrow \{x\}\cup \Gamma(x)\cup \Gamma_2(x),
\]
mapping edges to edges, such that 
$\varphi'\mid_{\{\widetilde{x}\}\cup \widetilde{\Gamma}(\widetilde{x})}=\varphi$.
In fact, it follows from Lemma \ref{lemma-bil3} that $\varphi'$ is an isomorphism.

We may simply assume that $\varphi$ sends a unique vertex of 
$\widetilde{L}_i\cap \widetilde{L}_j$ to $w_{ij}$ (and, clearly, $\widetilde{x}$ to $x$).
By Claims \ref{claim-ball-3} and \ref{claim-ball-2}, we may assume that Eq. (\ref{eq-iso}) 
holds. We then let $\varphi'$ send a vertex $\widetilde{y}\in \widetilde{\Gamma}_2(\widetilde{x})$ 
to a unique vertex $y\in \Gamma_2(x)$ such that $\mu_{x}(y)=\mu_{\widetilde{x}}(\widetilde{y})$.





\subsection{Triangulability of the bilinear forms graphs}\label{sect-triangul}

Our result in this section is the following proposition.

\begin{prop}\label{prop-bilq-triangl} 
The bilinear forms graph $Bil_q(e\times d)$ is triangulable.
\end{prop}
{\it Proof}.\  We will make use of an alternative definition of $Bil_q(e\times d)$ \cite[Chapter~9.5.A]{BCN}. 
Let $V$ be a vector space of dimension $e+d$ over $\mathbb{F}_q$, 
$W$ be a fixed $e$-subspace of $V$. Then the vertices of $Bil_q(e\times d)$ are 
the $d$-dimensional subspaces of $V$ skew to $W$, with two such subspaces 
$X,Y$ adjacent if and only if ${\rm dim}(X\cap Y)=d-1$.

Recall that the number of $m$-dimensional subspaces of a $k$-dimensional vector space 
over $\mathbb{F}_q$ that contain a given $\ell$-dimensional subspace is equal to 
\[
\left[
\begin{matrix} 
k-\ell \\ 
m-\ell
\end{matrix}
\right]_q.
\]

\begin{claim}\label{claim-triangulable-1}
The graph $Bil_q(e\times d)$ satisfies (i) of Lemma \ref{lemma-triangl-necess-cond}.
\end{claim}
{\it Proof}.\  Let $X$ and $Y_1$ be two $d$-dimensional subspaces corresponding to vertices $x$ and $y_1$ 
at distance $j\geq 2$ of the bilinear forms graph $Bil_q(e\times d)$, i.e., 
${\rm dim}(X\cap Y_1)=d-j$, ${\rm dim}(X\cap W)={\rm dim}(Y_1\cap W)=0$.
We are interested in the subgraph of $Bil_q(e\times d)$ 
induced by the $d$-subspaces $U$ of $V$ satisfying 
\begin{equation}\label{eq-u-subspaces}
{\rm dim}(U\cap X)=d-1,~~{\rm dim}(U\cap Y_1)=d-(j-1),
\end{equation}
and ${\rm dim}(U\cap W)=0$.

Note that any $d$-subspace $U$ satisfying Eq. (\ref{eq-u-subspaces}) contains 
$X\cap Y_1$. Hence any such subspace can be formed by choosing 
$(j-1)$-dimensional subspace 
in $X/(X\cap Y_1)$ 
and 
$1$-dimensional subspace 
in $Y_1/(X\cap Y_1)$.
Thus, the number of $d$-subspaces $U$ of $V$ satisfying Eq. (\ref{eq-u-subspaces}) 
(however, note that some of these subspaces may not satisfy ${\rm dim}(U\cap W)=0$)
is equal to 
\[
\left[
\begin{matrix} 
d-(d-j) \\ 
1
\end{matrix}
\right]_q
\times 
\left[
\begin{matrix} 
d-(d-j) \\ 
j-1
\end{matrix}
\right]_q=
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q
\times 
\left[
\begin{matrix} 
j \\ 
j-1
\end{matrix}
\right]_q=
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q
\times 
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q.
\]

The graph $\Lambda$ induced by the set of $d$-subspaces satisfying Eq. (\ref{eq-u-subspaces})
with two such subspaces adjacent if their intersection has dimension $d-1$ is
the $\Big(\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q
\times 
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q\Big)$-grid, whose maximal $\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q$-cliques consist of all $d$-dimensional subspaces
containing 
a given $(j-1)$-dimensional subspace 
from $X/(X\cap Y_1)$ 
or 
a given $1$-dimensional subspace 
from $Y_1/(X\cap Y_1)$.

Now we need to exclude from our consideration $d$-subspaces satisfying Eq. (\ref{eq-u-subspaces}), 
but intersecting $W$ non-trivially, and then to show that the graph $\Lambda'$ 
obtained from $\Lambda$ by removing the corresponding vertices is still connected. 

Let $A$ be an $1$-dimensional subspace in $Y_1/(X\cap Y_1)$.
Then the subspace $Y$ generated by $A$ and $X$ 
has dimension $d+1$, 
and thus $Y$ intersects $W$ in an $1$-dimensional subspace, say, $P$.  
Hence the number of $d$-subspaces of $Y$ satisfying Eq. (\ref{eq-u-subspaces}) 
(i.e., containing $X\cap Y_1$), 
containing $A$, and intersecting $W$ non-trivially (in $P$), is equal to 
\[
\left[
\begin{matrix} 
(d+1)-(d-j+2) \\ 
d-(d-j+2)
\end{matrix}
\right]_q=
\left[
\begin{matrix} 
j-1 \\ 
j-2
\end{matrix}
\right]_q=
\left[
\begin{matrix} 
j-1 \\ 
1
\end{matrix}
\right]_q.
\]

Therefore, from every maximal clique of $\Lambda$ we need to remove precisely 
$\left[
\begin{matrix} 
j-1 \\ 
1
\end{matrix}
\right]_q$ vertices. Note that the number of vertices left in $\Lambda'$ equals 
\[
|\Lambda'|=
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]^2_q
-
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q
\left[
\begin{matrix} 
j-1 \\ 
1
\end{matrix}
\right]_q=
q^{j-1}
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q=c_j,
\]
compare with Eq. (\ref{eq-cj-bil}).

Suppose now that the graph $\Lambda'$ is disconnected. 
Let $z_1$ and $z_2$ be two vertices of $\Lambda$ belonging 
to different connected components of $\Lambda'$. Note that 
$\Lambda_1(z_1)$, the local graph of $z_1$ in $\Lambda$, 
is the disjoint union of two cliques, say 
$L_1$ and $L_2$, each of size $\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q-1$.
Denote by $L_i^-$, $i\in \{1,2\}$, the set of 
vertices from $\Lambda(z_1)\setminus \Lambda'_1(z_1)$ belonging 
to the clique $L_i\subset \Lambda_1(z_1)$, i.e., 
$|L_i^-|=\left[
\begin{matrix} 
j-1 \\ 
1
\end{matrix}
\right]_q$.

Then $z_2$ belongs to the subgraph of $\Lambda$ induced by 
\[
\{w\in \Lambda\mid \exists (w_1,w_2)\in L_1^-\times L_2^-\text{~and~}w\sim w_1\text{~and~}w\sim w_2\},
\]
and, moreover, 
$\Lambda'$ does not contain vertices
from any of the following sets:
\[
\{w\in \Lambda\mid \exists (w_1,w_2)\in (\{z_1\}\cup L_1\setminus L_1^-)\times L_2^-\text{~and~}w\sim w_1\text{~and~}w\sim w_2\},
\]
\[
\{w\in \Lambda\mid \exists (w_1,w_2)\in L_1^-\times (\{z_1\}\cup L_2\setminus L_2^-)\text{~and~}w\sim w_1\text{~and~}w\sim w_2\},
\]
as otherwise there is a path in $\Lambda'$ from $z_2$ to $z_1$ through 
a vertex in one of these sets. This yields that 
\[
|\{z_1\}\cup (L_1\setminus L_1^-)|=
\left[
\begin{matrix} 
j \\ 
1
\end{matrix}
\right]_q
-\left[
\begin{matrix} 
j-1 \\ 
1
\end{matrix}
\right]_q
\le 
\left[
\begin{matrix} 
j-1 \\ 
1
\end{matrix}
\right]_q,
\]
which is impossible.

Thus, $\Lambda'$ is connected, and $Bil_q(e\times d)$ satisfies 
(i) of Lemma \ref{lemma-triangl-necess-cond}, which shows the claim.\hfill\vrule height .9ex width .8ex depth -.1ex

\begin{claim}\label{claim-triangulable-2}
The graph $Bil_q(e\times d)$ satisfies (ii) of Lemma \ref{lemma-triangl-necess-cond}.
\end{claim}
{\it Proof}.\  Let $X$, $Y_1$, $Y_2$ be $d$-dimensional subspaces of $V$ corresponding to vertices 
$x$, $y_1$, $y_2$ of the bilinear forms graph $Bil_q(e\times d)$ and satisfying 
${\rm dim}(X\cap Y_1)={\rm dim}(X\cap Y_2)=d-j$, where $j\geq 2$, 
${\rm dim}(Y_1\cap Y_2)=d-1$, and ${\rm dim}(X\cap W)={\rm dim}(Y_1\cap W)={\rm dim}(Y_2\cap W)=0$.
We shall show that there exists a $d$-subspace $U$ of $V$ satisfying  
\begin{equation}\label{eq-u-subspaces-2}
{\rm dim}(U\cap X)=d-1,~~{\rm dim}(U\cap Y_1)={\rm dim}(U\cap Y_2)=d-(j-1),\text{~and~}{\rm dim}(U\cap W)=0.
\end{equation}

We first consider a partial case when $j=d$, the diameter of $Bil_q(e\times d)$.
Let $A$ be an $1$-dimensional subspace of $Y_1\cap Y_2$.
Then the subspace $Y$ generated by $A$ and $X$ has dimension $d+1$, 
and thus $Y$ intersects $W$ in an $1$-dimensional subspace, say, $P$.

Further, the number of $d$-subspaces in $Y$ that contain $A$ is 
\[
\left[
\begin{matrix} 
d+1-1 \\ 
d-1
\end{matrix}
\right]_q,
\]
while the number of $d$-subspaces in $Y$ that contain both $A$ and $P$ is 
\[
\left[
\begin{matrix} 
d+1-2 \\ 
d-2
\end{matrix}
\right]_q=
\left[
\begin{matrix} 
d-1 \\ 
d-2
\end{matrix}
\right]_q.
\]

Thus, the number of $d$-subspaces $U$ of $Y$ that do not contain $P$, 
but contain $A$ (and hence $U$ satisfies Eq. (\ref{eq-u-subspaces-2})) is 
equal to 
\[
\left[
\begin{matrix} 
d \\ 
d-1
\end{matrix}
\right]_q
-
\left[
\begin{matrix} 
d-1 \\ 
d-2
\end{matrix}
\right]_q>0,
\]
which shows the claim in given partial case. 

We now turn to the general case. 
Note that if 
${\rm dim}(X\cap Y_1\cap Y_2)=d-j$, then 
we may consider the bilinear forms graph 
$Bil_q(e\times j)$ defined on $V/(X\cap Y_1\cap Y_2)$, 
and the claim follows from the previous partial case $j=d$.
Therefore we may assume that 
${\rm dim}(X\cap Y_1\cap Y_2)=d-j-1$.

Again, considering (if necessarily) the bilinear forms graph defined on $V/(X\cap Y_1\cap Y_2)$, 
we may assume that $j=d-1$, 
${\rm dim}(X\cap Y_1\cap Y_2)=0$, and 
$A=X\cap Y_1$, $B=X\cap Y_2$ are 1-dimensional subspaces. 
Let $C$ be an $1$-dimensional subspace of $Y_1\cap Y_2$.
Then the subspace $Y$ generated by $C$ and $X$ has dimension $d+1$, 
$A,B,C\subset Y$, and thus $Y$ intersects $W$ in an $1$-dimensional subspace, say, $P$.
As above, we count the number of $d$-subspaces of $Y$ that contain 
$\langle A,B,C\rangle$, but do not contain $\langle A,B,C,P\rangle$ 
as
\[
\left[
\begin{matrix} 
d+1-3 \\ 
d-3
\end{matrix}
\right]_q
-
\left[
\begin{matrix} 
d+1-4 \\ 
d-4
\end{matrix}
\right]_q>0,
\]
and it is the number of $d$-subspaces $U$ satisfying Eq. (\ref{eq-u-subspaces-2}). 
This shows the claim.\hfill\vrule height .9ex width .8ex depth -.1ex

Proposition \ref{prop-bilq-triangl} follows from Claims \ref{claim-triangulable-1}, 
\ref{claim-triangulable-2} and Lemma \ref{lemma-triangl-necess-cond}.
\hfill\vrule height .9ex width .8ex depth -.1ex





\subsection{Proof of Theorem \ref{theo-main-1}}

We are now in a position to prove Theorem \ref{theo-main-1}.

In the notation of Theorem \ref{theo-MS}, 
we take the bilinear forms graph $Bil_q(e\times d)$, $e\geq d\geq 2$, as $\widetilde{\Gamma}$, 
and $\Gamma$ as a graph satisfying Theorem \ref{theo-main-1}, i.e., 
$\Gamma$ is locally the $(n\times m)$-grid, with diameter $D\geq 2$, 
and the intersection numbers given by Eq. (\ref{eq-assum-Gamma}) are well-defined.

{\it Proof of Theorem \ref{theo-main-1}:}
By Lemma \ref{lemma-bil3}, the graph $\Gamma$ has distinct $\mu$-graphs, 
and the graphs $\Gamma$ and $\widetilde{\Gamma}$ satisfy $(i)$ of Theorem \ref{theo-MS} 
with the extendable isomorphism $\varphi$ defined in Section \ref{sect-step3}.
By Proposition \ref{prop-bilq-triangl}, the graph $\widetilde{\Gamma}$ satisfies $(iii)$ 
of Theorem \ref{theo-MS}.

Thus, what is left is to show that the graphs $\Gamma$ and $\widetilde{\Gamma}$ 
satisfy $(ii)$ of Theorem \ref{theo-MS}. 
We will follow the notation of Section \ref{sect-step3}.
Let $\widetilde{y}\in \widetilde{\Gamma}(\widetilde{x})$. 
Our goal is to show that 
\[
\varphi'\mid_{\{\widetilde{y}\}\cup \widetilde{\Gamma}(\widetilde{y})}:~~
\{\widetilde{y}\}\cup \widetilde{\Gamma}(\widetilde{y})
\rightarrow \varphi(\{\widetilde{y}\})\cup \Gamma(\varphi(\widetilde{y}))
\]
is an extendable isomorphism.

As in Section \ref{sect-step3}, we may similarly define the sets 
${\cal B}_{\widetilde{\Gamma},\widetilde{y}}$ and ${\cal B}^{\top}_{\widetilde{\Gamma},\widetilde{y}}$
of all blocks and $\top$-blocks, respectively, of the $(n\times m)$-grid $\widetilde{\Gamma}(\widetilde{y})$.

Without loss of generality, we assume that $\{1,2,3\}\in {\cal B}_{\widetilde{\Gamma},\widetilde{x}}$, 
and $\{\widetilde{y}\}=\widetilde{L}_1\cap \widetilde{L}^{\top}_1$.
Pick a $\top$-block $\{i,j,\ell\}\in {\cal B}^{\top}_{\widetilde{\Gamma},\widetilde{x}}$, 
and choose a vertex 
$\widetilde{z}\in \widetilde{\Gamma}_2(\widetilde{x})\cap \widetilde{\Gamma}_2(\widetilde{y})$ 
such that 
$\mu_{\widetilde{x}}(\widetilde{z})\in H^{\{1,2,3\}}_{\{i,j,\ell\}}$, i.e., 
$\widetilde{z}$ is at distance $2$ from $\widetilde{y}$, 
and $\widetilde{\Gamma}(\widetilde{x},\widetilde{y},\widetilde{z})$ is a pair 
of vertices containing in $\widetilde{L}_1$.
As the $\mu$-graphs in $\widetilde{\Gamma}$ are hexagons, 
this yields that $\widetilde{y}$ and $\widetilde{z}$ have four more common neighbours 
in $\widetilde{\Gamma}_2(\widetilde{x})$, and, in particular, 
these four common neighbours determine three maximal $n$-cliques of 
$\widetilde{\Gamma}(\widetilde{y})$. Thus, the $\top$-block 
$\{i,j,\ell\}\in {\cal B}^{\top}_{\widetilde{\Gamma},\widetilde{x}}$
uniquely determines a $\top$-block of ${\cal B}^{\top}_{\widetilde{\Gamma},\widetilde{y}}$.
In the same manner, it follows that each of blocks of 
${\cal B}_{\widetilde{\Gamma},\widetilde{x}}$
uniquely determines a block of ${\cal B}_{\widetilde{\Gamma},\widetilde{y}}$.

The same argument applied to the graph $\Gamma$, the vertex $x$ and the vertex 
$y=\varphi(\{\widetilde{y}\})$, and the proof of Lemma \ref{lemma-bil3} show 
that the isomorphism $\varphi'\mid_{\{\widetilde{y}\}\cup \widetilde{\Gamma}(\widetilde{y})}$ is extendable.
The theorem is proved.
\hfill\vrule height .9ex width .8ex depth -.1ex






\section{Main result}

In this section we prove our main result, Theorem \ref{theo-main}.

Let $\Gamma$ be a distance-regular graph with the same intersection array as $Bil_2(d\times d)$, $d\geq 3$.
Using Theorem \ref{theo-terwpoly} and Proposition \ref{prop-roots}, 
in Section \ref{sect-step-local}, 
we show that $\Gamma$ has the same local graphs as $Bil_2(d\times d)$.
Theorem \ref{theo-main} then follows from Theorem \ref{theo-main-1}.

\subsection{Local graphs of $\Gamma$}\label{sect-step-local}

In this section, we assume that $\Gamma$ is a distance-regular graph with 
the same intersection array as $Bil_q(e\times d)$, $e\geq d\geq 3$.
Let $\Delta:= \Gamma_1(x)$ denote the local graph for a vertex $x\in \Gamma$, 
and let $\eta$ be a non-principal eigenvalue of $\Delta$.

The following lemma shows Result \ref{theo-localspec}.

\begin{lemma}\label{lemma-locev}
The eigenvalue $\eta$ satisfies
\[
-q-1\leq \eta\leq -1,\text{~or~} q^d-q-1\leq \eta\leq q^e-q-1.
\]
\end{lemma}
{\it Proof}.\  The result follows immediately from Result \ref{reslt-bilformclassparams}, 
Theorem \ref{theo-terwpoly} and Proposition \ref{prop-roots}.\hfill\vrule height .9ex width .8ex depth -.1ex

Now we show that the spectrum of $\Delta$ is uniquely determined if $e=d$ and $q=2$.

\begin{lemma}\label{lemma-locev-q=2}
If $q=2$ and $e=d$, then $\Delta$ has spectrum 
\[
[2(2^d-2)]^1,~[2^d-3]^{2(2^d-2)},~[-2]^{(2^d-2)^2},
\]
and $\Delta$ is the $(2^d-1)\times (2^d-1)$-grid.
\end{lemma}
{\it Proof}.\  We first need the following claim.

\begin{claim}
The graph $\Delta$ has integral non-principal eigenvalues only, i.e., 
$\eta\in \{-3,-2,-1,2^d-3\}$.
\end{claim}
{\it Proof}.\  Recall that the eigenvalues of a graph are algebraic integers 
and their product is an integer. 
Suppose that $\eta_1,\ldots,\eta_s$ are all non-integral (i.e., irrational) eigenvalues 
of $\Delta$. Then, by Lemma \ref{lemma-locev}, we see that 
$-3<\eta_i<-1$ holds for all $i=1,\ldots,s$, and 
$\prod_{i=1}^s\eta_i$ is an integer. 
Therefore $\prod_{i=1}^s(\eta_i+2)$ is an integer.

As $-3<\eta_i<-1$ holds, it follows that $|\eta_i+2|<1$ and thus $\prod_{i=1}^s(\eta_i+2)=0$,
which shows the claim.\hfill\vrule height .9ex width .8ex depth -.1ex

We may assume now that $\Delta$ has the following distinct eigenvalues
\[
\eta_0=a_1=2(2^d-2),~\eta_1=2^d-3,~\eta_2=-1,~\eta_3=-2,~\eta_4=-3,
\]
and let $f_i$ denote the multiplicity of $\eta_i$, $i=0,\ldots,4$.

Note that $\Delta$ is a connected graph, as otherwise $\eta_0$ must be 
a non-principal eigenvalue of $\Delta$, which contradicts Lemma \ref{lemma-locev}.
Hence $f_0=1$.

We now consider the system of linear equations with respect to unknowns $f_1,f_2,f_3,f_4$:
\begin{align}
f_1+f_2+f_3+f_4&=(2^d-1)^2-1,\label{eq-trace0}
\\
(2^d-3)f_1-f_2-2f_3-3f_4&=-2(2^d-2),
\\
(2^d-3)^2f_1+f_2+4f_3+9f_4&=2(2^d-2)(2^d-1)^2-4(2^d-2)^2,
\end{align}
following from Eq. (\ref{trace}) for $\ell=0,1,2$.

Calculating the reduced row echelon form of this system gives:
\begin{align}
f_1+\frac{2}{(2^d-1)(2^d-2)}f_4&=2(2^d-2),\label{eq-redtrace0}
\\
f_2-\frac{2^d}{2^d-2}f_4&=0,\label{eq-redtrace1}
\\
f_3+\frac{2^{d+1}}{2^d-1}f_4&=(2^d-2)^2,\label{eq-redtrace2}
\end{align}

As all $f_i$'s are non-negative integers, one can see 
from Eq. (\ref{eq-redtrace0}) that if $f_4\ne 0$ then $f_4\geq (2^d-1)(2^d-2)/2$ 
and then $f_2\geq 2^d(2^d-1)/2$ follows from Eq. (\ref{eq-redtrace1}).
Thus, $f_2+f_4\geq (2^d-1)^2$, and Eq. (\ref{eq-trace0}) yields $f_1+f_3\leq -1$,
a contradiction. 
Therefore, $f_4=f_2=0$, and $\Delta$ has spectrum 
\[
[2(2^d-2)]^1,~[2^d-3]^{2(2^d-2)},~[-2]^{(2^d-2)^2}.
\]

This yields that $\Delta$ is strongly regular with the same parameters as the 
$(2^d-1)\times (2^d-1)$-grid. As $d\geq 3$ holds, and the $(m\times m)$-grid is uniquely 
determined by its parameters whenever $m\ne 4$ (see \cite{Shrikhande}), 
the lemma and Theorem \ref{theo-main} follow.\hfill\vrule height .9ex width .8ex depth -.1ex





\section{Concluding remarks}

In this paper, we showed that the bilinear forms graph $Bil_q(e\times d)$, 
with $q=2$ and $e=d\geq 3$, 
is uniquely determined by its intersection array. 
Of course, the main challenge is to generalize this result for any prime power $q$ 
and $e\in \{d,d+1,d+2\}$ (and $e=d+3$ if $q=2$). 
An attempt to prove it in the same manner as we did would require to modify 
almost all steps of the proof of Theorem \ref{theo-main}, 
including the spectral characterization of the $(q-1)$-clique extensions of grids.
The latter problem seems to be a highly non-trivial one even for $q=3$: 
in Yang et al. \cite{YAK} they showed that there exists a positive integer $T$ such that 
the $2$-clique extension of the $(t \times t)$-grid is characterized by its spectrum if $t \geq T$.

We also wonder whether the characterization of the bilinear forms graphs 
(for all $q$, $e$ and $d$)
in the spirit of Theorem \ref{theo-main-1} is possible, and, in particular, 
whether we really need to assume that the intersection number $b_2$ is well-defined.
Note that the same assumption (that the intersection number $a_2$ is well-defined)
was used in \cite{MunemasaPasechnikShpectorov} 
for local characterization of the graphs of alternating forms and the graphs 
of quadratic forms over $\mathbb{F}_2$, where the authors hoped that 
the condition would be shown superfluous in further research.
We are aware of only one such attempt, see \cite{MakPad}, which 
requires that $a_2(x,y)$ does not exceed some number 
(equivalently, $b_2(x,y)$ is not less than some number), 
for any pair of vertices $x,y\in \Gamma$ at distance $2$.

Finally, we would like to close our paper with one more result and an open problem.
One may check that the intersection array 
\begin{equation}\label{eq-doubtarr}
\{7(M-1),6(M-2),4(M-4);1,6,28\}
\end{equation}
is feasible (in the sense of \cite[Chapter~4.1.D]{BCN}) for all integers $M\ge 6$.
The only known graphs with this array are the bilinear forms graphs $Bil_2(m\times 3)$, 
where $M=2^m$.

By the result of Metsch, see \cite[Corollary~1.3(d)]{Metsch99}, 
if a distance-regular graph $\Gamma$ with intersection array given by Eq. (\ref{eq-doubtarr})
is not the bilinear forms graph, then $M\leq 133$.

The case when $M=6$ was ruled out in \cite{JurisicVidali}, 
the proof was based on counting some triple intersection numbers.
Here we present an alternative proof for this result.

\begin{prop}\label{prop-JVarray}
There exists no distance-regular graph with intersection array $\{35,24,8;1,6,28\}$.
\end{prop}
{\it Proof}.\  The graphs with intersection array given by Eq. (\ref{eq-doubtarr}) 
are $Q$-polynomial with diameter $D=3$ and classical parameters 
$(D,b,\alpha,\beta) = (3,2,1,M-1)$. 

Let $\Gamma$ be a graph with intersection array given by Eq. (\ref{eq-doubtarr}) 
with $M=6$, i.e., $\{35,24,8;1,6,28\}$.
By Proposition \ref{prop-roots}, the Terwilliger polynomial 
of $\Gamma$ has the following four roots:
\[
3,~~-1,~~-3,~~5,
\]
while the sign of its leading term coefficient is negative.

This yields that, for a vertex $x\in \Gamma$ and a non-principal 
eigenvalue $\eta$ of the local graph $\Delta:=\Gamma(x)$, one has:
\[
-3\leq \eta \leq -1\text{~~or~~}3\leq \eta \leq 5.
\]

Moreover, by \cite[Theorem~4.4.3]{BCN}, we have that $\eta\leq -1-\frac{b_1}{\theta_D+1}$, 
where the smallest eigenvalue $\theta_D$ of $\Gamma$ is equal to $-7$. 
Thus, $\eta\leq 3$. Now, in the same manner, as in the proof of Lemma \ref{lemma-locev-q=2}, 
one can show that the local graph $\Delta$ may only have integer eigenvalues, 
i.e., $\eta\in \{3,-1,-2,-3\}$, including the principal eigenvalue equal to $a_1=10$, 
whose multiplicity $f_0$ equals $1$.

We may assume that $\Delta$ has the following distinct eigenvalues
\[
\eta_0=a_1=10,~\eta_1=3,~\eta_2=-1,~\eta_3=-2,~\eta_4=-3,
\]
and let $f_i$ denote the multiplicity of $\eta_i$, $i=0,\ldots,4$.

Eq. (\ref{trace}) gives the following system of linear equations with respect to unknown 
multiplicities $f_1,f_2,f_3,f_4$:
\begin{align}
f_1+f_2+f_3+f_4&=34,
\\
3f_1-f_2-2f_3-3f_4&=-10,
\\
9f_1+f_2+4f_3+9f_4&=250,
\end{align}
which has the only solution in non-negative integers: $f_1=13$, $f_2=7$, $f_3=0$, $f_4=14$, 
and hence $\Delta$ has spectrum 
\[
[10]^1,~[3]^{13},~[-1]^{7},~[-3]^{14}.
\]

As the graph $\Delta$ is regular and has the four distinct eigenvalues, 
it follows that the number of triangles through a given its vertex $y$ 
is independent of $y$, and equals (see, for instance, \cite[Section~3.1]{vD95})
\[
\frac{1}{2\cdot 35}(10^3+13\cdot 3^3+7\cdot (-1)^3+14\cdot (-3)^3)=\frac{966}{70},
\]
which is impossible. Therefore there exists no graph $\Delta$ with given spectrum, 
and the proposition follows.
\hfill\vrule height .9ex width .8ex depth -.1ex

Now let $\Gamma$ be a graph with intersection array given by Eq. (\ref{eq-doubtarr}) 
with $M=7$, i.e., $\{42,30,12;1,6,28\}$. Similarly to the proof of Proposition \ref{prop-JVarray}, 
one can show that, for a vertex $x\in \Gamma$, the local graph $\Delta:=\Gamma(x)$ of $x$  
has spectrum 
\[
[11]^1,~[4]^{12},~[-1]^{14},~[-3]^{15},
\]
however, this time the number of closed walks of length $\ell$ through a vertex of $\Delta$ given by:
\[
\frac{1}{2\cdot 42}(11^l+12\cdot 4^l+14\cdot (-1)^l+15\cdot (-3)^l)
\]
is integer for all $\ell$. 

We challenge the reader to solve whether a distance-regular graph
with intersection array $\{42,30,12;1,6,28\}$ does exist.






