\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P5}{20(4)}{2013}
\usepackage{amsfonts}
\usepackage{amsmath,hyperref}
\usepackage{amsmath,amssymb,latexsym,color}
\usepackage[mathscr]{eucal}
\usepackage{color}
\def\thefootnote{\fnsymbol{footnote}}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{example}{Example}[section]
\newtheorem{defin}[thm]{Definition}
\newenvironment{definition}{\begin{defin} \rm}{\end{defin}}
\newtheorem{remark}{Remark}[section]
\newenvironment{re}{\begin{remark} \rm}{\end{remark}}
\newenvironment{eg}{\begin{example} \rm}{\end{example}}
\newcommand{\note}{\vspace{2ex}\noindent{\bf Note.\quad}}
\newcommand{\proof}{{\it Proof.\quad}}
\newcommand{\qed}{\hfill\Box\medskip}
\definecolor{red}{rgb}{1,0,0}
\definecolor{blue}{rgb}{0,1,0}
\usepackage{CJK}
\begin{document}
\begin{CJK*}{GBK}{song}

\title{\bf The Terwilliger algebra of the incidence graphs of Johnson geometry}

\author{
Qian Kong\\
\small College of Engineering\\
\small Nanjing Agricultural University,
Nanjing 210031, China\\
\small Sch. Math. Sci. {\rm \&} Lab. Math. Com.
Sys.\\[-0.8ex]
\small  Beijing Normal University, Beijing 100875,  China\\
\small \texttt{kongqian@njau.edu.cn}\\
\and Benjian Lv\\
\small Sch. Math. Sci. {\rm \&} Lab. Math. Com.
Sys.\\[-0.8ex]
\small  Beijing Normal University, Beijing 100875,  China\\
\small \texttt{benjian@mail.bnu.edu.cn}\\
\and Kaishun Wang\thanks{Corresponding
author}\\
\small Sch. Math. Sci. {\rm \&} Lab. Math. Com.
Sys.\\[-0.8ex]
\small  Beijing Normal University, Beijing 100875,  China\\
\small \texttt{wangks@bnu.edu.cn}}


\date{\dateline{Jan 4, 2012}{Oct 8, 2013}{Oct 21, 2013}\\
\small Mathematics Subject Classifications: 05E30}


 \maketitle



\begin{abstract}
In 2007, Levstein and Maldonado  computed the Terwilliger algebra of
the Johnson graph $J(n,m)$ when $3m\leq n$. It is well known that
the halved graphs of  the incidence graph $J(n,m,m+1)$ of Johnson
geometry are Johnson graphs. In this paper, we determine the
Terwilliger algebra of  $J(n,m,m+1)$  when $3m\leq n$, give two
bases of this algebra, and calculate its dimension.

\bigskip\noindent {\bf Keywords:} Terwilliger algebra; Johnson graph;
incidence graph; Johnson geometry

\end{abstract}


\section{Introduction}

Let $\Gamma=(X,R)$ denote a simple connected graph with the vertex
set $X$ and the edge set $R$. Suppose Mat$_X(\mathbb{C})$ denotes
the algebra over the complex number field  $\mathbb{C}$ consisting
of all matrices whose rows and columns are indexed by elements of
$X$. For vertices $x$ and $y$, $\partial(x,y)$ denotes the
\emph{distance} between $x$ and $y$, i.e., the length of a shortest
path connecting $x$ and $y$. Fix a vertex $x\in X$. Let
$D(x)=\max\{\partial(x,y)\mid y\in X\}$ denote the \emph{diameter
with respect to} $x$. For each $i\in \{0,1,\ldots,D(x)\}$, let
$\Gamma_i(x)=\{y\in X\mid
\partial(x,y)=i\}$ and define $E_i^*=E_i^*(x)$ to be the diagonal matrix in
Mat$_X(\mathbb{C})$ with $yy$-entry
$$
(E_i^*)_{yy}=\left\{ \begin{array}{ll}
1,& \textrm{if $y\in \Gamma_i(x)$},\\
0,& \textrm{otherwise}.\\
\end{array} \right.
$$
The subalgebra $\mathcal {T}=\mathcal {T}(x)$ of Mat$_X(\mathbb{C})$
generated  by the adjacency matrix $A$ of $\Gamma$ and
$E_0^*,E_1^*,\ldots,E_{D(x)}^*$ is called the \emph{Terwilliger
algebra} of $\Gamma$ with respect to $x$. Let $\mathbb{C}^X$ denote
the vector space over $\mathbb{C}$ consisting of all column vectors
whose coordinates are indexed by $X$. A \emph{$\mathcal {T}$-module}
is any subspace $W$ of $ \mathbb{C}^X$ such that $\mathcal
{T}W\subseteq W$. We call a nonzero $\mathcal {T}$-module
\emph{irreducible} if it does not properly contain a nonzero
$\mathcal {T}$-module. An irreducible $\mathcal {T}$-module $W$ is
\emph{thin} if $\dim E_i^*W\leq 1$ for every $i$, and the graph
$\Gamma$ is said to be \emph{thin with respect to $x$} if every
irreducible $\mathcal {T}(x)$-module is thin.

Terwilliger \cite{ter1, ter2, ter3} initiated the study of the
Terwilliger algebra of an association scheme, which has been an
important tool in   studying   structures of an association scheme.
For more information, see \cite{bpq, abpq, curtin}. The Terwilliger
algebras of group schemes were discussed in \cite{s5a5, bannai1}.
The Terwilliger algebras of some distance-regular graphs have been
determined; see  \cite{sr} for strongly regular graphs, \cite{go}
for Hypercubes, \cite{hdq} for  Hamming graphs, \cite{johnson} for
Johnson graphs, \cite{Kong} for   odd graphs.

Let $\Omega$ be a set of cardinality $n$ and let ${\Omega \choose
i}$ denote the collection of all $i$-subsets of $\Omega$. Suppose
$m$ is a nonnegative  integer with $m+1\leq n.$ The \emph{incidence
graph $J(n,m,m+1)$ of Johnson geometry} is a bipartite graph with a
bipartition ${\Omega \choose m}\cup {\Omega \choose m+1}$, where
$y\in {\Omega \choose m}$ and $z\in {\Omega \choose m+1}$ are
adjacent   if $y\subseteq z$. The graph $J(n,m,m+1)$ is
\emph{distance-biregular} (see \cite {bcn}). It is well known that
the halved graphs of $J(n,m,m+1)$ are Johnson graphs.

Levstein and Maldonado \cite{johnson} determined the Terwilliger
algebra of the Johnson graph $J(n,m)$ when $3m\leq n$. In this paper
we shall determine the Terwilliger algebra of $J(n,m,m+1)$ with
respect to $x\in {\Omega \choose m}$ when $n\geq 3m$. In Section 2,
we introduce some useful identities for intersection matrices. In
Section 3,   the Terwilliger algebra of $J(n,m,m+1)$ is described.
In Section 4, we give two bases of this algebra and compute its
dimension.


\section{Intersection matrices}


In this section we shall introduce intersection matrices  and some
related  identities.



Let $V$ be a set of cardinality $v$. The \emph{inclusion matrix}
$W_{i,j}(v)$ is a binary matrix whose rows and columns are indexed
by elements of ${V \choose i}$ and ${V \choose j}$, respectively,
with the $yz$-entry defined by
$$
(W_{i,j}(v))_{yz}=\left\{ \begin{array}{ll}
1,& \textrm{if $y\subseteq z$},\\
0,& \textrm{otherwise}.\\
\end{array} \right.
$$
Observe that
\begin{eqnarray}\label{3}
W_{i,j}(v)W_{j,k}(v)={k-i \choose j-i}W_{i,k}(v).
\end{eqnarray}

 Let $H_{i,j}^l(v)$ be a binary matrix whose rows and
columns are indexed by elements of ${V \choose i}$ and ${V \choose
j}$, respectively, and the $yz$-entry is defined by
$$
(H_{i,j}^l(v))_{yz}=\left\{ \begin{array}{ll}
1,& \textrm{if $|y\cap z|=l$},\\
0,& \textrm{otherwise}.\\
\end{array} \right.
$$
Define
\begin{eqnarray}\label{17}
C_{i,j}^l(v)=\sum_{g=l}^{\min(i,j)}{g \choose l}H_{i,j}^g(v).
\end{eqnarray}


%We adopt the convention that $C_{i,j}^l(v)=0$ for any integer $l$
%such that $l<0$ or $\min(i,j)<l$.

In order to simply the notation, we write $W_{i,j}$ for $W_{i,j}(v)$
when $v$ is clear from context, and do the same for $H_{i,j}^l(v)$
and $ C_{i,j}^l(v)$. The  matrices $W_{i,j}, H_{i,j}^l$ and
$C_{i,j}^l$ are \emph{intersection matrices} introduced in
\cite{Mohammad-Noori}.

 Observe $C_{i,j}^0$ is the all-one matrix and
$$
C_{i,j}^{\min(i,j)}=\left\{\begin{array}{ll}
W_{j,i}^\textrm{T},& \textrm{if $i>j$}, \\
 W_{i,j},&\textrm{otherwise}.
\end{array}\right.
$$




\begin{lemma}{\rm(\cite{Mohammad-Noori})}\label{8}
 Let $V$ be a set of cardinality $v$. Write $W_{i,j}=W_{i,j}(v)$ and
$C_{i,j}^l=C_{i,j}^l(v)$. Then
$$
C_{i,j}^lC_{j,k}^s=\sum\limits_{h=\max(0,l+s-j)}^{\min(l,s)}{v-l-s
\choose j-l-s+h}{i-h \choose l-h}{k-h \choose s-h}C_{i,k}^h.
$$ In particular, the following hold:

\emph{(i)} $W_{i,j}^\emph{T}W_{i,k}=C_{j,k}^i;$

\emph{(ii)} $C_{i,j}^lW_{j,k}={k-l \choose j-l}C_{i,k}^l;$

\emph{(iii)}
$W_{i,k}W_{j,k}^\emph{T}=\sum\limits_{l=\max(0,i+j-k)}^{\min(i,j)}{v-i-j
\choose k-i-j+l}C_{i,j}^l;$

\emph{(iv)}
$W_{i,j}C_{j,k}^l=\sum\limits_{h=\max(0,l+j-i)}^{\min(l,i)}{v-l-i
\choose j-l-i+h}{k-h \choose l-h}C_{i,k}^h.$
\end{lemma}






 Fix $x\in {\Omega \choose m}$. We then consider the adjacency matrix
$A$ of $J(n,m,m+1)$ as a block matrix with respect to the partition
$\{x\}\cup\Gamma_1(x)\cup\cdots\cup\Gamma_{D(x)}(x)$. Let $A_{i,j}$
be the submatrix of $A$ with rows indexed by vertices of
$\Gamma_i(x)$ and columns indexed by vertices of $\Gamma_j(x)$.

\begin{lemma}\label{1} Given two vertices $x, y$ of
 $J(n,m,m+1)$. If
$x\in {\Omega \choose m}$, then
$$
\partial(x,y)=\left\{\begin{array}{ll}
                      2i,&{\rm if}\ \ |y|=m\ {\rm and}\ |x\cap y|=m-i,\\
                      2i+1,&{\rm if}\ \ |y|=m+1\ {\rm and}\ |x\cap
                      y|=m-i.
                      \end{array}\right.
$$
In particular,   $D(x)=\min(2m+1, 2n-2m)$.
\end{lemma}
\textbf{Proof.} Immediate from \cite [Lemma 2.2] {hiraki}. $\qed$


\begin{lemma}\label{4}
Let $I_{{v \choose k}}$ be the identity matrix of size ${v \choose
k}$. Then
\begin{eqnarray}
\label{5}{}&&A_{i,j}=0, \quad \textrm{if} \ \ 0\leq i\leq j \leq
D(x)\ \
\textrm{and} \ \ i\neq j-1; {}\\
\label{6}{}&&A_{2i,2i+1}=I_{{m \choose m-i}}\otimes W_{i,i+1}(n-m),
\quad \textrm{if} \ \
0\leq i\leq   \lfloor\frac{D(x)-1}2 \rfloor;\\
\label{7}{}&&A_{2i+1,2i+2}=W_{m-i-1,m-i}^\emph{T}(m)\otimes I_{{n-m
\choose i+1}}, \quad \textrm{if} \ \ 0\leq i\leq
 \lfloor\frac{D(x)}2 \rfloor-1,
\end{eqnarray}
where ``$\otimes$'' denotes the Kronecker product of matrices.
\end{lemma}
\textbf{Proof.} (\ref{5}) is directed.

Pick $y\in\Gamma_{2i}(x)$, $z\in\Gamma_{2i+1}(x)$. By Lemma \ref{1}
we have $|y|=m$, $|z|=m+1$, $|x\cap y|=|x\cap z|=m-i$. Suppose
$y=\alpha_{m-i}\cup\beta_i$, $z=\alpha_{m-i}'\cup\beta_{i+1}'$,
where $\alpha_{m-i}$ and $\alpha_{m-i}'\in{x \choose m-i}$, while
$\beta_i\in{\Omega\setminus x \choose i}$ and
$\beta_{i+1}'\in{\Omega\setminus x \choose i+1}$. Then
$$
(A_{2i,2i+1})_{yz}=1\Leftrightarrow\alpha_{m-i}=\alpha_{m-i}'  \;
\textrm{and}\;  \beta_i\subseteq \beta_{i+1}'\Leftrightarrow (I_{m
\choose m-i}\otimes W_{i,i+1}(n-m))_{yz}=1,
$$
which leads to (\ref{6}).

Similarly, (\ref{7}) holds. $\qed$





\section{The Terwilliger algebra}


  Let $n\geq 3m$ and   $X$ denote the vertex set of $J(n,m,m+1)$. Fix $x\in {\Omega\choose m}.$ In this
section we shall determine the Terwilliger algebra $\mathcal
{T}=\mathcal {T}(x)$ of $J(n,m,m+1)$. Hereafter the ground set of
all matrices $C^l_{p,q}(m)$ is $x$ and that of $C^l_{p,q}(n-m)$ is
$\Omega\setminus x.$

 For
$i,j\in\{0,1,\ldots, 2m+1\}$, let $\mathcal {M}_{i,j}$ be  the
vector space spanned  by
$$C_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^l(m)\otimes
C_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^s(n-m),
$$
where
 $$
 0\leq
l\leq\min(m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor),
\ 0\leq s\leq\min(\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil).
$$
Write
\begin{eqnarray}\label{9}
\mathcal {M}=\bigoplus\limits_{i,j=0}^{2m+1}L(\mathcal {M}_{i,j}),
\end{eqnarray}
where $L(\mathcal {M}_{i,j})=\{L(M)\in{\rm Mat}_X(\mathbb C)\mid
M\in \mathcal {M}_{i,j}\}$, and
$$
L(M)_{\Gamma_k(x)\times\Gamma_l(x)}=\left\{ \begin{array}{ll}
M,& \textrm{if $k=i$ and $l=j$},\\
0,& \textrm{otherwise}.\\
\end{array} \right.
$$

Note that $\mathcal {M}$ is a vector space. By Lemma \ref{8},
$\mathcal {M}$ is an algebra. In the remaining of this section we
shall prove $\mathcal {T}=\mathcal {M}$.



\begin{lemma}\label{11}
The Terwilliger algebra $\mathcal {T}$ is a subalgebra of $\mathcal
{M}$.
\end{lemma}
\textbf{Proof.} By Lemma \ref{4} we have $ A\in \mathcal {M}$. For
$0\leq i\leq 2m+1$, since
$$
E_i^*=E_i^*(x)=L(C_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{i}{2}\rfloor}^{m-\lfloor\frac{i}{2}\rfloor}(m)\otimes
C_{\lceil\frac{i}{2}\rceil,\lceil\frac{i}{2}\rceil}^{\lceil\frac{i}{2}\rceil}(n-m))\in
\mathcal {M},
$$
we get $\mathcal {T}\subseteq\mathcal {M}$. $\qed$


  For $i,j\in\{0,1,\ldots, 2m+1\}$, let $\mathcal
{T}_{i,j}=\{M_{i,j}\mid M\in\mathcal {T}\}$, where $M_{i,j}$ is the
submatrix of $M$ with rows indexed by vertices  of $\Gamma_i(x)$ and
columns indexed by vertices  of $\Gamma_j(x)$. Since $\mathcal {T}$
is an algebra, each $\mathcal {T}_{i,j}$ is a vector space. Since
$\mathcal {T}E_j^*\mathcal {T}\subseteq\mathcal {T}$, $(\mathcal
{T}E_j^*\mathcal {T})_{i,k}\subseteq\mathcal {T}_{i,k}$, which gives
\begin{eqnarray}\label{23}
\mathcal {T}_{i,j}\mathcal {T}_{j,k}\subseteq\mathcal {T}_{i,k}.
\end{eqnarray}
Since $A$, $E_i^*\in\mathcal {T}$, we have
$E_{i_1}^*AE_{i_2}^*AE_{i_3}^*\cdots AE_{i_{p-1}}^*AE_{i_{p}}^*\in
E_{i_1}^*\mathcal {T}E_{i_{p}}^*$, from which it follows that
\begin{eqnarray}\label{13}
A_{i_1,i_2}A_{i_2,i_3}\cdots A_{i_{p-2},i_{p-1}}A_{i_{p-1},i_p}\in
\mathcal {T}_{i_1,i_p},
\end{eqnarray}
where $0\leq i_s\leq2m+1$ for any $s\in\{1,\ldots, p\}$.


Note that
$$
W_{m-\lfloor\frac{h}{2}\rfloor, m-\lfloor\frac{h}{2}\rfloor}^{\rm
T}(m)\otimes
W_{\lceil\frac{h}{2}\rceil,\lceil\frac{h}{2}\rceil}(n-m)=I_{m\choose
m-\lfloor\frac{h}{2}\rfloor}\otimes I_{n-m\choose
\lceil\frac{h}{2}\rceil}.
$$
 By Lemma \ref{4} and (\ref{3}), for
$h+1\leq k,$ one gets
$$
A_{h,h+1}\cdots A_{k-1,k}=({\lfloor}\frac{k}{2}{\rfloor}-
{\lfloor}\frac{h}{2} {\rfloor})! ( {\lceil}\frac{k}{2} {\rceil}-
{\lceil}\frac{h}{2} {\rceil})!
W_{m-\lfloor\frac{k}{2}\rfloor,m-\lfloor\frac{h}{2}\rfloor}^{\rm
T}(m)\otimes
W_{\lceil\frac{h}{2}\rceil,\lceil\frac{k}{2}\rceil}(n-m).
$$
 Hence, by (\ref{13}), for   $h\leq k,$  we have
\begin{eqnarray}\label{wwt}
W_{m-\lfloor\frac{k}{2}\rfloor,m-\lfloor\frac{h}{2}\rfloor}^{\rm
T}(m)\otimes
W_{\lceil\frac{h}{2}\rceil,\lceil\frac{k}{2}\rceil}(n-m)\in \mathcal
{T}_{h,k}.
\end{eqnarray}





\begin{lemma}\label{12}
For $2i+2\leq j\leq 2m+1$ and $0\leq s\leq i+1$, we have
\begin{eqnarray}\label{l32}
C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s(n-m)\in\mathcal {T}_{2i+2,j}.
\end{eqnarray}
\end{lemma}
\textbf{Proof.} We use induction on $s$ ($s$ decreasing from $i+1$
to $0$). Since
$$
C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^{i+1}(n-m)=W_{m-\lfloor\frac{j}{2}\rfloor,m-i-1}^{\rm
T}(m)\otimes W_{i+1,\lceil\frac{j}{2}\rceil}(n-m),
$$
by (\ref{wwt}), (\ref{l32}) holds for $2i+2\leq j\leq 2m+1$ and $s=
i+1.$


Assume that
$C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s(n-m)\in\mathcal {T}_{2i+2,j}$. By
(\ref{23}) and (\ref{13}) we obtain
\begin{eqnarray}
(C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s(n-m))(A_{j,j+1}A_{j+1,j})\in
\mathcal {T}_{2i+2,j}\mathcal {T}_{j,j}\subseteq\mathcal
{T}_{2i+2,j},\label{35}\\
(C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s(n-m))(A_{j,j-1}A_{j-1,j})\in
\mathcal {T}_{2i+2,j}\mathcal {T}_{j,j}\subseteq\mathcal
{T}_{2i+2,j}.\label{33}
\end{eqnarray}
When $j$ is even, by Lemma \ref{4}, Lemma \ref{8}, (\ref{35}) leads
to
$$
aC_{m-i-1,m-\frac{j}{2}}^{m-\frac{j}{2}}(m)\otimes
C_{i+1,\frac{j}{2}}^s(n-m)+bC_{m-i-1,m-\frac{j}{2}}^{m-\frac{j}{2}}(m)\otimes
C_{i+1,\frac{j}{2}}^{s-1}(n-m)\in\mathcal {T}_{2i+2,j},
$$
where $a=(n-m-s-\frac{j}{2})(\frac{j}{2}-s+1)$ and
$b=(i-s+2)(\frac{j}{2}-s+1)$. Similarly when $j$ is odd, (\ref{33})
yields that
$$
a'C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s(n-m)+b'C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^{s-1}(n-m)
$$
belongs to $\mathcal {T}_{2i+2,j}$, where
$a'=(n-m-s-\lceil\frac{j}{2}\rceil+1)(\lceil\frac{j}{2}\rceil-s)$
and $b'=(i-s+2)(\lceil\frac{j}{2}\rceil-s+1)$. Since $s\leq i+1\leq
\lceil\frac{j}{2}\rceil$, $b\neq0$ and $b'\neq0$. Thus we have
$C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{j}{2}\rfloor}(m)\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^{s-1}(n-m)\in\mathcal {T}_{2i+2,j}$.

Hence the desired result follows. $\qed$

\begin{lemma}\label{14}
The algebra $\mathcal {M}$ is a subalgebra of $\mathcal {T}$.
\end{lemma}
\textbf{Proof.} During this proof we will omit the symbol $(m)$ from
matrices in front of ``$\otimes$'', and omit $(n-m)$ from matrices
behind ``$\otimes$''.

In order to get the desired conclusion, we only need to show that
$\mathcal {M}_{i,j}\subseteq\mathcal {T}_{i,j}$ for
$i,j\in\{0,1,\ldots,  2m+1\}$. Write $\mathcal
{M}_{i,j}^\textrm{T}=\{M^\textrm{T}\mid M\in\mathcal {M}_{i,j}\}$
and $\mathcal {T}_{i,j}^\textrm{T}=\{M^\textrm{T}\mid M\in\mathcal
{T}_{i,j}\}$. Since $\mathcal {M}_{j,i}=\mathcal
{M}_{i,j}^\textrm{T}$ and $\mathcal {T}_{j,i}=\mathcal
{T}_{i,j}^\textrm{T}$, it suffices to prove $\mathcal
{M}_{i,j}\subseteq\mathcal {T}_{i,j}$ for $i\leq j$. We use
induction on $i$.

\medskip
\textbf{Step 1.} We show that $\mathcal {M}_{0,j}\subseteq\mathcal
{T}_{0,j}$ for $0\leq j\leq 2m+1$.

According to (\ref{9}), the subspace $\mathcal {M}_{0,j}$ is
spanned by $
 C_{m,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{0,\lceil\frac{j}{2}\rceil}^0,$ where $ 0\leq l\leq
m-\lfloor\frac{j}{2}\rfloor. $ Since
$$
C_{m,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{0,\lceil\frac{j}{2}\rceil}^0={m-\lfloor\frac{j}{2}\rfloor \choose
l}W_{m-\lfloor\frac{j}{2}\rfloor,m}^\textrm{T}\otimes
W_{0,\lceil\frac{j}{2}\rceil}
$$
for any $l\in\{0,1,\ldots,m-\lfloor\frac{j}{2}\rfloor\}$, we get
$\mathcal {M}_{0,j}\subseteq\mathcal {T}_{0,j}$ from (\ref{wwt}).

\medskip
\textbf{Step 2.} Assume that $\mathcal {M}_{p,j}\subseteq\mathcal
{T}_{p,j}$ for $p\leq 2i$. We will show that $\mathcal
{M}_{2i+1,j}\subseteq\mathcal {T}_{2i+1,j}$ and $\mathcal
{M}_{2i+2,j}\subseteq\mathcal {T}_{2i+2,j}$.

\medskip
\textbf{Step 2.1.} We show that $\mathcal
{M}_{2i+1,j}\subseteq\mathcal {T}_{2i+1,j}$ for $2i+1\leq j\leq
2m+1$.

It suffices to prove
\begin{eqnarray}\label{31}
C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s\in\mathcal {T}_{2i+1,j},
\end{eqnarray}
where $0\leq l\leq m-\lfloor\frac{j}{2}\rfloor$, $0\leq s\leq i+1$.

By induction hypothesis,
$$
C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{i,\lceil\frac{j}{2}\rceil}^s\in\mathcal
{M}_{2i,j}\subseteq\mathcal {T}_{2i,j},
 $$
for $0\leq l\leq m-\lfloor\frac{j}{2}\rfloor,\ 0\leq s\leq i.
$
Since
$$
A_{2i,2i+1}^\textrm{T}=I_{m \choose m-i}\otimes
W_{i,i+1}^\textrm{T}\in\mathcal
{M}_{2i,2i+1}^\textrm{T}\subseteq\mathcal {T}_{2i,2i+1}^\textrm{T},
$$
we have
$$
(I_{m \choose m-i}\otimes
W_{i,i+1}^\textrm{T})(C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{i,\lceil\frac{j}{2}\rceil}^s)\in\mathcal
{T}_{2i,2i+1}^\textrm{T}\mathcal {T}_{2i,j}\subseteq\mathcal
{T}_{2i+1,j}.
$$
By Lemma \ref{8}, (\ref{31}) holds for $0\leq l\leq
m-\lfloor\frac{j}{2}\rfloor$ and $0\leq s\leq i$.


Next we shall show that (\ref{31}) holds for $0\leq l\leq
m-\lfloor\frac{j}{2}\rfloor$ and $s=i+1$.

By (\ref{wwt}), for $j\leq k\leq 2m+1,$
$$
(W_{m-\lfloor\frac{j}{2}\rfloor,m-i}^\textrm{T}\otimes
W_{i+1,\lceil\frac{j}{2}\rceil})(W_{m-\lfloor\frac{k}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^
\textrm{T}\otimes
W_{\lceil\frac{j}{2}\rceil,\lceil\frac{k}{2}\rceil})(W_{m-\lfloor\frac{k}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}\otimes
W_{\lceil\frac{j}{2}\rceil,\lceil\frac{k}{2}\rceil}^{\rm T})
$$
belongs to $\mathcal {T}_{2i+1,j}.$ By Lemma~\ref{8},
\begin{eqnarray}\label{16}
a
C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^{m-\lfloor\frac{k}{2}\rfloor}\otimes
\left(\sum_{h=\max(0,i+1+\lceil\frac{j}{2}\rceil-\lceil\frac{k}{2}\rceil)}^{i+1}{n-m-i-1-\lceil\frac{j}{2}\rceil
\choose
\lceil\frac{k}{2}\rceil-i-1-\lceil\frac{j}{2}\rceil+h}C_{i+1,\lceil\frac{j}{2}\rceil}^h\right)
\end{eqnarray}
belongs to $\mathcal {T}_{2i+1,j}$, where
$a={\lfloor\frac{k}{2}\rfloor-i\choose\lfloor\frac{k}{2}\rfloor-\lfloor\frac{j}{2}\rfloor}
{\lceil\frac{k}{2}\rceil-i-1\choose\lceil\frac{j}{2}\rceil-i-1}\neq
0$. Since (\ref{31}) holds for $0\leq l\leq
m-\lfloor\frac{j}{2}\rfloor$ and $0\leq s\leq i,$  one has
$$
{n-m-i-1-\lceil\frac{j}{2}\rceil \choose
\lceil\frac{k}{2}\rceil-\lceil\frac{j}{2}\rceil}C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^
{m-\lfloor\frac{k}{2}\rfloor}\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^{i+1}\in\mathcal {T}_{2i+1,j}.
$$
Since $0\leq 2i+1\leq j\leq k-1\leq 2m-1$ and $n\geq 3m$, we get
$$
n-m-i-1-\lceil\frac{j}{2}\rceil\geq
n-m-m-\lceil\frac{j}{2}\rceil\geq
m-\lceil\frac{j}{2}\rceil\geq\lceil\frac{k}{2}\rceil-\lceil\frac{j}{2}\rceil\geq
0,
$$
and so ${n-m-i-1-\lceil\frac{j}{2}\rceil \choose
\lceil\frac{k}{2}\rceil-\lceil\frac{j}{2}\rceil}\neq 0$. Hence
(\ref{31}) holds for $0\leq l\leq m-\lfloor\frac{j}{2}\rfloor$ and
$s=i+1$.





\medskip
\textbf{Step 2.2.} We show that $\mathcal {M}_{2i+2,j}\subseteq
\mathcal {T}_{2i+2,j}$ for $2i+2\leq j\leq 2m+1$.

It suffices to prove
\begin{eqnarray}\label{25}
C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s\in \mathcal {T}_{2i+2,j}, \quad
0\leq l\leq m-\lfloor\frac{j}{2}\rfloor, \ 0\leq s\leq i+1.
\end{eqnarray}
By the inductive assumption, for $0\leq l\leq
m-\lfloor\frac{j}{2}\rfloor$ and $0\leq s\leq i+1$,
$$
C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s\in\mathcal
{M}_{2i+1,j}\subseteq\mathcal {T}_{2i+1,j}.
$$
Since
$$
A_{2i+1,2i+2}^\textrm{T}=W_{m-i-1,m-i}\otimes I_{n-m \choose
i+1}\in\mathcal {T}_{2i+1,2i+2}^\textrm{T},
$$
by (\ref{23}) we have
\begin{eqnarray}
 (W_{m-i-1,m-i}\otimes I_{n-m \choose
i+1})(C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^l\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s) \in\mathcal
{T}_{2i+1,2i+2}^\textrm{T}\mathcal {T}_{2i+1,j}   \subseteq \mathcal
{T}_{2i+2,j}.\label{26}
\end{eqnarray}
By Lemma \ref{8},
$$
W_{m-i-1,m-i}C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^l=
(i+1-l)C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^l+(m-\lfloor\frac{j}{2}\rfloor-l+1)C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{l-1}.
$$
Thus (\ref{26}) implies that
\begin{eqnarray}\label{27}
((i+1-l)C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^l+(m-\lfloor\frac{j}{2}\rfloor-l+1)C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{l-1})\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s
\end{eqnarray}
belongs to $\mathcal {T}_{2i+2,j},$ where $0\leq l\leq
m-\lfloor\frac{j}{2}\rfloor$, $0\leq s\leq i+1$.\ Since the
coefficient of $C_{m-i-1,m-\lfloor\frac{j}{2}\rfloor}^{l-1}\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^s$ in (\ref{27}) is
$m-\lfloor\frac{j}{2}\rfloor-l+1\neq 0$, by Lemma \ref{12} we get
(\ref{25}).

Hence the desired result follows. $\qed$

\begin{thm}\label{21}
Fix  $x\in {\Omega\choose m}.$  Let $\mathcal {T}$ be the
Terwilliger algebra   of $J(n,m,m+1)$ with respect to   $x$ and
$\mathcal {M}$ be the   algebra defined in $(\ref{9})$.  If $n\geq
3m$, then $\mathcal {T}=\mathcal {M}$.
\end{thm}
\textbf{Proof.} Combining Lemmas \ref{11} and  \ref{14}, the desired
result follows. $\qed$

 The condition $n\geq 3m$ guarantees the coefficient of
$C_{m-i,m-\lfloor\frac{j}{2}\rfloor}^
{m-\lfloor\frac{k}{2}\rfloor}\otimes
C_{i+1,\lceil\frac{j}{2}\rceil}^{i+1}$ in (\ref{16}) is non-zero. It
seems to be interesting to determine the Terwilliger algebra of
$J(n,m,m+1)$ without this assumption.

\begin{thm}{\rm(\cite[Theorem 13]{ter4})}\label{ths}
Let $\Gamma=(X,R)$ be a graph and $\mathcal{T}$ be the Terwilliger
algebra   of $\Gamma$ with respect to  a vertex $x$. If
$E^*_{i}\mathcal{T}E^*_{i}$ is symmetric for any
$i\in\{0,1,\ldots,D(x)\},$ then $\Gamma$ is thin with respect  to
$x$.
\end{thm}

\begin{cor}\label{32}
With reference to Theorem \ref{21}, $J(n,m,m+1)$ is thin with
respect to $x$.
\end{cor}
\textbf{Proof.} By Theorem \ref{21},  for any
$i\in\{0,1,\ldots,D(x)\}$, the subspace $E_i^*\mathcal {T}E_i^*$ is
spanned by
$$
L(C_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{i}{2}\rfloor}^l(m)\otimes
C_{\lceil\frac{i}{2}\rceil,\lceil\frac{i}{2}\rceil}^s(n-m)),
$$
where $ 0\leq l\leq m-\lfloor\frac{i}{2}\rfloor,   0\leq s\leq
\lceil\frac{i}{2}\rceil. $
 Since each element of
$E_i^*\mathcal {T}E_i^*$ is symmetric, we get the conclusion from
Theorem~\ref{ths}. $\qed$

\section{Two bases of the Terwilliger algebra}


In this section we shall determine two bases  of the Terwilliger
algebra $\mathcal {T}$ in Theorem~\ref{21}. Set
$$
G_{i,j}=\{g\mid
H_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^g(m)\neq
0\},\; R_{i,j}=\{r\mid
H_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^r(n-m)\neq
0\}.
$$

\begin{thm}\label{18}
Let   $\mathcal {T}$ be as in Theorem \ref{21}. Then
\begin{eqnarray}\label{2}
\{L(H_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^g(m)\otimes
H_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^r(n-m)), \ g\in
G_{i,j}, \ r\in R_{i,j}\}_{i,j=0}^{2m+1}
\end{eqnarray}
as well as
\begin{eqnarray}\label{10}
\{L(C_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^l(m)\otimes
C_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^s(n-m)), \ l\in
G_{i,j}, \ s\in R_{i,j}\}_{i,j=0}^{2m+1}
\end{eqnarray}
are two bases of $\mathcal {T}$.
\end{thm}
\textbf{Proof.} Without loss of generality, suppose $i\leq j$. We
have $H_{i,j}^l(v)\neq 0$ if and only if $\max(0,i+j-v)\leq l\leq
\min(i,j)$, so $\lceil\frac{i}{2}\rceil-|R_{i,j}|+1\leq r \leq
\lceil\frac{i}{2}\rceil$ when $r\in R_{i,j}$. By (\ref{17}) we
obtain
\begin{eqnarray}\label{19}
C_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^r(n-m)
=\sum_{h=r}^{\lceil\frac{i}{2}\rceil}{h \choose
r}H_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^h(n-m),
\end{eqnarray}
which implies that
$H_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^r(n-m)$  is a
linear combination of
$\{C_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^s(n-m)\}_{s\in
R_{i,j}}$ for any $r\in R_{i,j}$. Similarly,
$H_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^g(m)$
can be expressed as a linear combination of
$\{C_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^l(m)\}_{l\in
G_{i,j}}$ for any $g\in G_{i,j}$ . Hence every element of
\begin{eqnarray}\label{bij}
\{H_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^g(m)\otimes
H_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^r(n-m)\}_{g\in
G_{i,j}, r\in R_{i,j}}
\end{eqnarray}
belongs to $\mathcal {M}_{i,j}$. Again by (\ref{17}), for $0\leq
l\leq m-\lfloor\frac{j}{2}\rfloor$ and $0\leq s\leq
\lceil\frac{i}{2}\rceil$,
\begin{eqnarray*}
&&C_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^l(m)\otimes
C_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^s(n-m)\\
&=&\Big{(}\sum_{g=l}^{m-\lfloor\frac{j}{2}\rfloor}{g \choose
l}H_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^g(m)\Big{)}\otimes
\Big{(}\sum_{r=s}^{\lceil\frac{i}{2}\rceil}{r \choose
s}H_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^r(n-m)\Big{)}.
\end{eqnarray*}
Observe that (\ref{bij}) are linearly independent, so (\ref{bij}) is
a basis of $\mathcal {M}_{i,j}$. Therefore (\ref{2}) is a basis of
$\mathcal {T}$.

Furthermore, by (\ref{19}) we   get
$\{C_{m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor}^l(m)\otimes
C_{\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil}^s(n-m)\}_{l\in
G_{i,j}, s\in R_{i,j}}$ is also a basis of $\mathcal {M}_{i,j}$,
from which it follows that (\ref{10}) is a basis of $\mathcal {T}$.
 $\qed$

\begin{cor}\label{28}
With reference to Theorem \ref{21} we get the dimension of $\mathcal
{T}$ is
$$
\dim \mathcal {T}=\left\{ \begin{array}{lll} \frac{1}{12}(m+1)(m+2)(m+3)(3m+10)-4,& \emph{if $n=3m$},\\
\frac{1}{12}(m+1)(m+2)(m+3)(3m+10)-1,& \emph{if $n=3m+1$},\\
\frac{1}{12}(m+1)(m+2)(m+3)(3m+10),& \emph{if $n\geq3m+2$}.\\
\end{array} \right.
$$
\end{cor}
\textbf{Proof.} By Theorem \ref{18},
\begin{eqnarray*}
\dim \mathcal {T}&=&\sum_{i,j=0}^{2m+1}|G_{i,j}||R_{i,j}|\\
&=&\sum_{i,j=0}^{2m+1}(\min(m-\lfloor\frac{i}{2}\rfloor,m-\lfloor\frac{j}{2}\rfloor)
-\max(0,m-\lfloor\frac{i}{2}\rfloor-\lfloor\frac{j}{2}\rfloor)+1)\\
&&\times (\min(\lceil\frac{i}{2}\rceil,\lceil\frac{j}{2}\rceil)
-\max(0,\lceil\frac{i}{2}\rceil+\lceil\frac{j}{2}\rceil-n+m)+1).
\end{eqnarray*}
By zigzag calculation, we get the desired result.  $\qed$

\section{Concluding Remark}

We conclude this paper with the following remarks:

(i) Let $\Omega$ be a set of cardinality $n$ and let $J(n,m)$ be the
Johnson graph based on $\Omega$ with $n\geq 3m$. Fix an $m$-subset
$x$ of $\Omega$. Let $\mathcal {T}'=\mathcal {T}'(x)$ and $\mathcal
{T}=\mathcal {T}(x)$ be the Terwilliger algebra of $J(n,m)$ and
$J(n,m,m+1)$ with respect to $x$, respectively. Since
$\bigoplus_{i,j=0}^mE_{2i}^*(x)\mathcal {T}E_{2j}^*(x)$ is an
algebra, $\{L(H_{m-i,m-j}^g(m)\otimes H_{i,j}^r(n-m)),\ g\in
G_{2i,2j}, \ r\in R_{2i,2j}\}_{i,j=0}^{m}$ is a basis of
$\bigoplus_{i,j=0}^mE_{2i}^*(x)\mathcal {T}E_{2j}^*(x)$ by Theorem
\ref{18}. By \cite [Definition 4.2, Lemma 4.4, Theorem 5.9]{johnson}
this basis coincides with that of $\mathcal {T}'$, which implies
that $\mathcal {T}'\simeq\bigoplus_{i,j=0}^mE_{2i}^*(x)\mathcal
{T}E_{2j}^*(x)$.

(ii) Using the same method, the Terwilliger algebra of $J(n,m,m+1)$
with respect to an $(m+1)$-subset may be determined.




\subsection*{Acknowledgement} We are indebted to the anonymous reviewer  for
his detailed  reports. We  would like to thank Professor Hiroshi
Suzuki for proposing this problem. This research is supported by
NSFC (11301270, 11271047).




\begin{thebibliography}{00}

\bibitem{s5a5} P. Balmaceda, M. Oura, The Terwilliger algebras of the group association schemes of
$S_5$ and $A_5$, {\em Kyushu J. Math.} {\bf 48} (1994) 221--231.

\bibitem{bannai1} E. Bannai, A. Munemasa, The Terwilliger algebras of group association schemes, {\em Kyushu J.
Math.} {\bf 49} (1995) 93--102.

\bibitem{bcn} A.E. Brouwer, A.M. Cohen, A. Neumaier,
 Distance-Regular Graphs, Springer-Verlag, Berlin, Heidelberg, 1989.

\bibitem{bpq} J.S. Caughman IV, The Terwilliger algebra for bipartite $P$- and $Q$-polynomial association schemes,
{\em Discrete Math.} {\bf 196} (1999) 65--95.

\bibitem{abpq} J.S. Caughman, M.S. MacLean, P. Terwilliger, The Terwilliger algebra of an almost-bipartite
$P$- and $Q$-polynomial association scheme, {\em Discrete Math.}
{\bf 292} (2005) 17--44.

\bibitem{curtin} B. Curtin, The Terwilliger algebra of a 2-homogeneous bipartite
distance-regular graph, {\em J. Combin. Theory Ser. A} {\bf 81}
(2001) 125--141.

\bibitem{Mohammad-Noori}  N. Ghareghani, E.
Ghorbani, M. Mohammad-Noori, Intersection matrices revisited, {\em
J. Combin. Des.} {\bf 20} (2012) 383--397.

\bibitem{go} J. Go, The Terwilliger algebra of the hypercube, {\em European J.
Combin.} {\bf 23} (2002) 399--429.


\bibitem{hiraki} A. Hiraki, A characterization of the doubled Grassmann
graphs, the doubled Odd graphs, and the Odd graphs by strongly
closed subgraphs, {\em European J.   Combin.} {\bf 24} (2003)
161--171.

\bibitem{Kong} Q. Kong, B. Lv, K. Wang, The Terwilliger algebra
of odd graphs, {\em Discrete Math.} {\bf 313} (2013) 698--703.


\bibitem{hdq} F. Levstein, C. Maldonado, D. Penazzi, The Terwilliger algebra of
a Hamming scheme $H(d,q)$, {\em European J. Combin.} {\bf 27} (2006)
1--10.

\bibitem{johnson} F. Levstein, C. Maldonado, The Terwilliger algebra of the Johnson
schemes, {\em Discrete Math.} {\bf 307} (2007) 1621--1635.



\bibitem{ter1} P. Terwilliger, The subconstituent algebra of an association scheme I, {\em J. Algebr. Combin.}
{\bf 1} (1992) 363--388.

\bibitem{ter2} P. Terwilliger, The subconstituent algebra of an association scheme II, {\em J. Algebr. Combin.} {\bf 2} (1993)
73--103.

\bibitem{ter3} P. Terwilliger, The subconstituent algebra of an association scheme III, {\em J. Algebr. Combin.} {\bf 2} (1993)
177--210.

\bibitem{ter4} P. Terwilliger, Algebraic Graph Theory, Hand-Written Lecture Note of Paul Terwilliger,
Rewritten and Added Comments by H. Suzuki, \url{http://subsite.icu.ac.jp/people/hsuzuki/lecturenote}

\bibitem{sr} M. Tomiyama, N. Yamazaki, The subconstituent algebra of a strongly regular graph, {\em Kyushu J.
Math.} {\bf 48} (1994) 323--334.


\end{thebibliography}






\end{CJK*}

\end{document}
