\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)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}