% % % % Accepted to E-JC % 19.2.2018 % % % \documentclass[a4paper,12pt]{article} \catcode`\"=13 \def"#1{\v#1} \usepackage[dvips]{epsfig,graphicx} \usepackage{amsmath,amsfonts,amssymb,verbatim} \usepackage{e-jc} \specs{P1.52}{25(1)}{2018} \newcommand{\CC}{{\mathbb C}} \newcommand{\ZZ}{{\mathbb Z}} \newcommand{\B}[1]{\boldsymbol{#1}} \newcommand{\bi}[1]{\hbox{\boldmath{$#1$}}} \newcommand{\RR}{{\mathbb R}} \newcommand{\NN}{{\mathbb N}} \newcommand{\ths}{\theta^*} \newcommand{\qed}{\hfill\hbox{\rule{3pt}{6pt}}} \newcommand{\proof}{{\sc Proof. }} %\newcommand{\Label}[1]{\marginpar{\footnotesize #1} \label{#1}} \newcommand{\Label}{\label} \newcommand{\mat}{{\rm Mat}} \newcommand{\MX}{\mat_X(\CC)} \newcommand{\G}{\Gamma} \newcommand{\Es}{E^*} \newcommand{\pceq}{\preccurlyeq} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}[theorem]{Definition} \newtheorem{notation}[theorem]{Notation} \newtheorem{remark}[theorem]{Remark} \newtheorem{conjecture}{Conjecture}[section] \newtheorem{problem}{Problem}[section] %\hoffset=-15mm %\textwidth=16cm %\voffset=-16mm %\textheight=23cm % % \title{On bipartite $Q$-polynomial distance-regular graphs with diameter 9, 10, or 11} \author{"Stefko Miklavi"c \thanks{This work is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0032, N1-0038, N1-0062, J1-6720, and J1-7051). } \\ \small Andrej Maru\v si\v c Institute, University of Primorska \\[-0.8ex] \small Muzejski trg 2, 6000 Koper, Slovenia, and \\[-0.8ex] \small Institute of Mathematics, Physics and Mechanics \\[-0.8ex] \small Jadranska 19, 1000 Ljubljana, Slovenia \\ \small\tt stefko.miklavic@upr.si\\ } \date{\dateline{Sep 20, 2017}{Feb 19, 2018}{Mar 2, 2018}\\ \small Mathematics Subject Classifications: 05C50, 05E30} \begin{document} \maketitle \begin{abstract} Let $\Gamma$ denote a bipartite distance-regular graph with diameter $D$. In [J.\ S.\ Caughman, Bipartite Q-polynomial distance-regular graphs, {\it Graphs Combin.} {\bf 20} (2004), 47--57], Caughman showed that if $D \ge 12$, then $\G$ is $Q$-polynomial if and only if one of the following (i)-(iv) holds: (i) $\G$ is the ordinary $2D$-cycle, (ii) $\G$ is the Hamming cube $H(D,2)$, (iii) $\G$ is the antipodal quotient of the Hamming cube $H(2D,2)$, (iv) the intersection numbers of $\G$ satisfy $c_i = (q^i - 1)/(q-1), \, b_i = (q^D-q^i)/(q-1) \; (0 \le i \le D)$, where $q$ is an integer at least $2$. In this paper we show that the above result is true also for bipartite distance-regular graphs with $D \in \{9,10,11\}$. \bigskip\noindent \textbf{Keywords:} bipartite distance-regular graph; $Q$-polynomial property \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} \Label{sec:intro} As a classification of all distance-regular graphs is currently beyond our reach, classifications of some subclasses of distance-regular graphs are also very important projects. One such subclass is the class of $Q$-polynomial bipartite distance-regular graphs. This paper is part of an effort to understand and classify $Q$-polynomial bipartite distance-regular graphs (see \cite{Ca1, Ca2, Ca3, Ca4, Ca5} for relevant literature). A crucial step towards a classification of this class was made by Caughman, who proved the following result. \begin{theorem} \label{thm:caug} (\cite[Theorem 1.1]{Ca5}) Let $\G$ denote a bipartite distance-regular graph with diameter $D \ge 12$. Then $\G$ is $Q$-polynomial if and only if one of the following (i)-(iv) holds: \begin{itemize} \item[(i)] $\G$ is the ordinary $2D$-cycle. \item[(ii)] $\G$ is the Hamming cube $H(D,2)$. \item[(iii)] $\G$ is the antipodal quotient of the Hamming cube $H(2D,2)$. \item[(iv)] The intersection numbers of $\G$ satisfy $$ c_i = \frac{q^i - 1}{q-1}, \qquad b_i = \frac{q^D-q^i}{q-1} \qquad (0 \le i \le D), $$ where $q$ is an integer at least $2$. \end{itemize} \end{theorem} In this paper we prove an analogue of Theorem \ref{thm:caug} for bipartite distance-regular graphs with diameter $D \in \{9,10,11\}$. We follow the ideas of Caughman \cite{Ca5} and use the Terwilliger algebra of $\G$ to prove our result. Generalization of Theorem \ref{thm:caug} to bipartite distance-regular graphs with diameter less than 12 is also mentioned as an open problem in the recent survey paper {\em Distance-regular graphs} by van Dam, Koolen and Tanaka, see \cite[Section 18.3]{DKT}. The paper is organized as follows. In Sections \ref{sec:prelim}, \ref{sec:Q-poly}, \ref{sec:ter} we review some basic definitions and results about distance-regular graphs, the $Q$-polynomial property of distance-regular graphs, and the Terwilliger algebra of distance-regular graphs. In Section \ref{sec:mult} we review and prove some results concerning multiplicities of irreducible modules of the Terwilliger algebra. In Sections \ref{sec:bound} and \ref{sec:main} we prove our main result. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} \label{sec:prelim} In this section we review some definitions and basic concepts. See the book of Brouwer, Cohen and Neumaier \cite{BCN} for more background information. Throughout this paper, $\Gamma=(X,R)$ will denote a finite, undirected, connected graph, without loops or multiple edges, with vertex set $X$, edge set $R$, path length distance function $\partial$, and diameter $D:=\max \{\partial(x,y) | x,y \in X \}$. For a vertex $x \in X$ define $\Gamma_i(x)$ to be the set of vertices at distance $i$ from $x$. We abbreviate $\Gamma(x):=\Gamma_1(x)$. Let $k$ denote a nonnegative integer. Then $\Gamma$ is said to be {\it regular} with {\it valency} $k$ whenever $|\Gamma(x)|=k$ for all $x \in X$. The graph $\Gamma$ is said to be {\it distance-regular} whenever for all integers $h,i,j$ $(0 \le h,i,j \le D)$, and all $x,y \in X$ with $\partial(x,y)=h$, the number \begin{equation} p_{ij}^h := | \{z \, | \, z \in X, \, \partial(x,z)=i, \, \partial(y,z)=j \} | \end{equation} is independent of $x,y$. The constants $p_{ij}^h$ are known as the {\it intersection numbers} of $\Gamma$. For convenience, set $c_i:=p_{1 i-1}^i$ for $1 \le i \le D, \, a_i:=p_{1i}^i$ for $0 \le i \le D, \, b_i:=p_{1 i+1}^i$ for $0 \le i \le D-1, k_i:=p_{ii}^0$ for $0 \le i \le D$, and $c_0=b_D=0$. We observe $a_0=0, \; c_1=1$. Moreover, $\Gamma$ is regular with valency $k=b_0$, and $c_i+a_i+b_i=k$ for $0 \le i \le D$. It is well-known that \begin{equation} \label{eq:k} k_i=\frac{b_0 \cdots b_{i-1}}{c_1 \cdots c_i} \qquad (0 \le i \le D). \end{equation} Observe that $\Gamma$ is bipartite if and only if $a_i=0$ for $0 \le i \le D$. In this case $b_i+c_i=k$ for $0 \le i \le D$. \medskip From now on we assume $\Gamma$ is distance-regular with diameter $D \ge 3$ and valency $k \ge 3$. We recall the Bose-Mesner algebra of $\Gamma$. Let $\MX$ denote the $\CC$-algebra consisting of the matrices over $\CC$ which have rows and columns indexed by $X$. For $0 \le i \le D$ let $A_i$ denote the matrix in $\MX$ with $x,y$ entry \begin{equation} (A_i)_{x y} = \left\{ \begin{array}{lll} 1 & \hbox{if } \; \partial(x,y)=i, & \\ & & (x,y \in X). \\ 0 & \hbox{if } \; \partial(x,y) \ne i & \end{array} \right. \end{equation} We call $A_i$ the $i$-th {\em distance matrix} of $\Gamma$. We abbreviate $A=A_1$ and call $A$ the {\em adjacency matrix} of $\Gamma$. The matrices $A_0,A_1, \ldots, A_D$ form a basis for a commutative semi-simple $\CC$-algebra $M$, known as the {\it Bose-Mesner algebra}, see for example \cite[Lemma 11.2.2]{Go}. The algebra $M$ has a second basis $E_0,E_1, \ldots, E_D$ such that $E_i E_j = \delta_{ij} E_i \; (0 \le i,j \le D)$, see \cite[Theorem 2.6.1]{BCN}. The $E_0,E_1, \ldots, E_D$ are known as the {\it primitive idempotents} of $\Gamma$, and $E_0$ is the {\it trivial} idempotent. For $0 \le i \le D$ define a real number $\theta_i$ by $A = \sum_{i=0}^D \theta_i E_i$. Then $AE_i = E_iA =\theta_i E_i$ for $0 \le i \le D$. The scalars $\theta_0, \theta_1, \ldots, \theta_D$ are distinct, since $A$ generates $M$ \cite[p. 197]{BI}. The $\theta_0, \theta_1, \ldots, \theta_D$ are known as the {\it eigenvalues} of $\Gamma$. We remark $k \ge \theta_i \ge -k$ for $0 \le i \le D$, and $\theta_0=k$ \cite[p. 45]{BCN}. Let $\theta$ denote an eigenvalue of $\Gamma$, and let $E$ denote the associated primitive idempotent. For $0 \le i \le D$ define a real number $\ths_i$ by $E = |X|^{-1}\sum_{i=0}^D \ths_i A_i$. We call the sequence $\ths_0, \ths_1, \ldots, \ths_D$ the {\it dual eigenvalue sequence} associated with $\theta, E$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The $Q$-polynomial property} \label{sec:Q-poly} In this section we recall the $Q$-polynomial property of distance-regular graphs. Let $\Gamma$ denote a distance-regular graph with diameter $D \ge 3$ and valency $k \ge 3$, and let $A_0, A_1, \ldots, A_D$ denote the distance matrices of $\G$. Observe that $A_i \circ A_j = \delta_{ij}A_i \; (0 \le i,j \le D)$, where $\circ$ denotes entrywise multiplication, and so algebra $M$ is closed under $\circ$. Let $E_0, E_1, \ldots, E_D$ denote the primitive idempotents of $\G$. The {\it Krein parameters} $q_{ij}^h \; (0 \le h,i,j \le D)$ of $\Gamma$ are defined by \begin{equation} E_i \circ E_j = |X|^{-1} \sum_{h=0}^D q_{ij}^h E_h \;\;\; (0 \le i,j \le D). \end{equation} We say $\Gamma$ is {\it $Q$-polynomial} (with respect to the given ordering $E_0, E_1, \ldots, E_D$ of the primitive idempotents), whenever for all distinct integers $i,j \; (0 \le i,j \le D)$ the following holds: $q_{ij}^1 \ne 0 \; \hbox{ if and only if } \; |i-j|=1$. Let $E$ denote a nontrivial primitive idempotent of $\Gamma$. We say $\Gamma$ is {\it $Q$-polynomial with respect to $E$} whenever there exists an ordering $E_0, E_1=E, \ldots, E_D$ of the primitive idempotents of $\Gamma$, with respect to which $\Gamma$ is $Q$-polynomial. \smallskip \noindent We have the following important result about bipartite $Q$-polynomial distance-regular graphs, see \cite[Lemma 3.2, Lemma 3.3]{Ca5}. \begin{lemma} \label{lem:caug} Let $\Gamma$ denote a bipartite distance-regular graph with diameter $D \ge 4$, valency $k \ge 3$, and intersection numbers $b_i, c_i$ $(0 \le i \le D)$. We assume $\Gamma$ is $Q$-polynomial with respect to $E_0, E_1, \ldots, E_D$. For $0 \le i \le D$ let $\theta_i$ denote the eigenvalue associated with $E_i$. Let $\ths_0, \ths_1, \ldots, \ths_D$ denote the dual eigenvalue sequence associated with $E_1$. Assume $\Gamma$ is not the $D$-cube or the antipodal quotient of the $2D$-cube. Then there exist scalars $q,s^* \in \RR$ such that {\rm (i)--(iii)} hold below. \begin{itemize} \item[{\rm (i)}] $|q| > 1, \;$ $s^* q^i \ne 1 \qquad (2 \le i \le 2D+1)$; \item[{\rm (ii)}] $\theta_i=h(q^{D-i}-q^i), \;$ $\ths_i=\ths_0 + h^*(1-q^i)(1-s^* q^{i+1})q^{-i} \;$ for $0 \le i \le D$, where $$ h=\frac{1-s^* q^3}{(q-1)(1-s^* q^{D+2})}, \; \; h^*=\frac{(q^D+q^2)(q^D+q)}{q(q^2-1)(1-s^* q^{2D})}, \; \; \ths_0=\frac{h^*(q^D-1)(1-s^* q^2)}{q(q^{D-1}+1)}; $$ \item[{\rm (iii)}] $k=c_D=h(q^D-1)$, and $$ c_i=\frac{h(q^i-1)(1-s^* q^{D+i+1})}{1-s^* q^{2i+1}}, \qquad b_i=\frac{h(q^D-q^i)(1-s^* q^{i+1})}{1-s^* q^{2i+1}} \qquad (1 \le i \le D-1). $$ \end{itemize} \end{lemma} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The Terwilliger algebra} \label{sec:ter} In this section we recall the Terwilliger algebra of a distance-regular graph. Let $\Gamma$ denote a distance-regular graph with diameter $D \ge 3$, valency $k \ge 3$, and distance matrices $A_0, A_1, \ldots, A_D$. Fix any vertex $x \in X$. For $0 \le i \le D$ let $E_i^*=E_i^*(x)$ denote the diagonal matrix in $\MX$ with $y,y$ entry $(A_i)_{xy}$ $(y \in X)$. Let $T=T(x)$ denote the subalgebra of $\MX$ generated by $A$ and $E_0^*, \ldots, E_d^*$. We call $T$ the {\em Terwilliger algebra} of $\Gamma$ with respect to $x$. We remark that $T$ is finite dimensional and semisimple. \smallskip \noindent Let $V$ denote the $\CC$-vector space consisting of the column vectors over $\CC$ which have rows indexed by $X$. Observe that $\MX$ acts on $V$ by left multiplication. We refer to $V$ as the {\em standard module of} $T$. By a $T$-{\em module} we mean a subspace $W$ of the standard module $V$ such that $BW \subseteq W$ for all $B \in T$. Let $W$ denote a $T$-module. Then $W$ is said to be {\em irreducible} whenever $W$ is nonzero and $W$ contains no $T$-modules other than zero and~$W$. \smallskip \noindent Let $W$ and $W'$ denote $T$-modules. By a $T$-{\em isomorphism} from $W$ to $W'$, we mean a vector space isomorphism $\sigma:W \to W'$ such that $(\sigma B - B \sigma)W=0$ for all $B \in T$. The modules $W$ and $W'$ are said to be {\em isomorphic} whenever there exists a $T$-isomorphism from $W$ to $W'$. \smallskip \noindent Let $W$ denote a $T$-module and let $W'$ denote a $T$-module contained in $W$. Then the orthogonal complement of $W'$ in $W$ is a $T$-module. From this we find $W$ is an orthogonal direct sum of irreducible $T$-modules. Taking $W=V$ we find $V$ is an orthogonal direct sum of irreducible $T$-modules. Let $W$ denote an irreducible $T$-module. By the {\em multiplicity} with which $W$ appears in $V$, we mean the number of irreducible $T$-modules in this sum which are isomorphic to $W$. It is known that the multiplicity of $W$ is independent of the decomposition of $V$. \smallskip \noindent Let $W$ denote an irreducible $T$-module. We define the {\em endpoint} $r$ and the {\em diameter} $d$ of $W$ by $r = \min \{i \mid 0 \le i\le D, \; E^*_i W \ne 0 \}$ and $d=|\{i \mid 0 \le i \le D, \; E^*_i W \ne 0\}|-1$. Similarly, the {\em dual endpoint} $t$ and {\em dual diameter} $d^*$of $W$ are defined by $t = \min \{i \mid 0 \le i\le D, \; E_i W \ne 0 \}$ and $d^*:=|\{i \mid 0 \le i \le D, \; E_i W \ne 0\}|-1$. We say $W$ is {\em thin}, whenever ${\rm dim}(\Es_i W) \le 1$ for every $0 \le i \le D$. \noindent Assume now that our distance-regular graph $\G$ is $Q$-polynomial. Let $W$ denote an irreducible $T$-module with endpoint $r$, dual endpoint $t$, diameter $d$ and dual diameter $d^*$. Then $W$ is thin by \cite[Theorem 9.3]{Ca2}. We comment on $r,t,d$ and $d^*$. By \cite[Lemma 5.1(ii)]{Ca2} we have $2r+d^* \ge D$, and by \cite[Lemma 9.2(ii)]{Ca2} we have that $d=d^*$. It follows that $(D-d)/2 \le r$. It is also clear that $r + d \le D$, and so we have that $$ \frac{D-d}{2} \le r \le D-d. $$ We have $2t+d=D$ by \cite[Theorem 9.4(ii)]{Ca2}, and so $D-d$ is even. By \cite[Theorem 13.1]{Ca2}, the isomorphism class of $W$ is determined by $r$ and $d$. For the rest of the paper we will consider the following situation. \begin{notation} \label{blank} Let $\G=(X,R)$ denote a bipartite distance-regular graph with diameter $D \ge 4$, valency $k \ge 3$, intersection numbers $b_i, c_i$, and distance matrices $A_i \; (0 \le i \le D)$. We fix $x \in X$ and let $\Es_i = \Es_i(x) \; (0 \le i \le D)$ and $T=T(x)$ denote the dual idempotents and the Terwilliger algebra of $\G$ with respect to $x$, respectively. Let $V$ denote the standard module for $\G$. Let $H(D,2)$ denote the $D$-dimensional hypercube, and let $\overline{H}(2D,2)$ denote the antipodal quotient of $H(2D,2)$. \end{notation} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Multiplicities of the irreducible $T$-modules} \label{sec:mult} With reference to Notation \ref{blank}, assume that $\G$ is $Q$-polynomial. In this section we review and prove some results about the multiplicities of irreducible $T$-modules (see also \cite[Section 14]{Ca2}). Fix a decomposition of the standard module $V$ into an orthogonal direct sum of irreducible $T$-modules. Let $W$ denote an irreducible $T$-module. Recall that the multiplicity of $W$ equals the number of irreducible $T$-modules in this sum which are isomorphic to $W$. As the isomorphism class of $W$ is determined by its endpoint and diameter, we introduce the following notation. For any integers $r,d \; (0 \le r,d \le D)$, we define mult$(r,d)$ to be the number of irreducible $T$-modules in this decomposition which have endpoint $r$ and diameter $d$. If no such modules exist, then we set mult$(r,d)=0$. Note that if $W$ has endpoint $r$ and diameter $d$, then the multiplicity of $W$ equals mult$(r,d)$. \begin{definition} \label{def:pairs} (\cite[Definition 14.2]{Ca2}) With reference to Notation \ref{blank}, assume that $\G$ is $Q$-polynomial. Define a set $\Upsilon$ by $$ \Upsilon := \{(r,d) \in \ZZ^2 \mid 0 \le d \le D, D-d \text{ even }, \frac{D-d}{2} \le r \le D-d \}. $$ \end{definition} Observe that mult$(r,d) = 0$ for all integers $r,d$ such that $(r,d) \not\in \Upsilon$. We define a partial order $\pceq$ on $\Upsilon$ by $$ (r',d') \pceq (r,d) \quad \text{ if and only if } \quad r' \le r \text{ and } r+d \le r'+d'. $$ To further describe mult$(r,d)$, we need a definition. Let $(r,d) \in \Upsilon$. Following \cite[pp. 87-88]{Ca2} we define scalars $c_i(r,d) \; (1 \le i \le d)$ and $b_i(r,d) \; (0 \le i \le d-1)$ by \begin{equation} \label{cW} c_i(r,d) =\frac{\theta_t(\ths_{r+i+1}-\ths_{r+1})-\theta_{t+1}(\ths_{r+i}-\ths_r)} {\ths_{r+i+1}-\ths_{r+i-1}} \qquad (1 \le i \le d-1), \end{equation} \begin{equation} \label{bW} b_i(r,d) =\frac{\theta_t(\ths_{r+1}-\ths_{r+i-1})+\theta_{t+1}(\ths_{r+i}-\ths_r)} {\ths_{r+i+1}-\ths_{r+i-1}} \qquad (1 \le i \le d-1), \end{equation} where $t=(D-d)/2$. We also set $b_0(r,d)=c_d(r,d)=\theta_t$, $b_d(r,d)=c_0(r,d)=0$. Assume now that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Then using Lemma \ref{lem:caug}(ii) we get that \begin{equation} \label{cWqs} c_i(r,d) =\frac{h(q^i-1)(1-s^* q^{2r+d+i+1})} {q^{d+t}(1-s^*q^{2r+2i+1})} \qquad (1 \le i \le d-1), \end{equation} \begin{equation} \label{bWqs} b_i(r,d) =\frac{h(q^d-q^i)(1-s^* q^{2r+i+1})} {q^{d+t}(1-s^*q^{2r+2i+1})} \qquad (1 \le i \le d-1), \end{equation} and $b_0(r,d)=c_d(r,d)=h(q^{-t}-q^{t-D})$, $b_d(r,d)=c_0(r,d)=0$. \begin{theorem} \label{thm:mult-formula} (\cite[Theorem 14.7]{Ca2}) With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$. Then $$ k_r \prod_{i=r}^{r+d-1} b_i c_{r+d-i} = \sum_{{(r',d') \in \Upsilon \atop (r',d') \pceq (r,d)}} {\rm mult}(r',d') \prod_{i=r-r'}^{r+d-r'-1} b_i(r',d') c_{i+1}(r',d'). $$ \end{theorem} \begin{corollary} \label{cor:r+d=D} With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$ such that $r+d=D \; (1 \le r \le D-1)$. Then $r$ is even and $$ k_r \prod_{i=r}^{D-1} b_i c_{D-i} = \sum_{\ell=0}^{r/2} {\rm mult}(2\ell,D-2\ell) \prod_{i=r-2\ell}^{D-2\ell-1} b_i(2\ell,D-2\ell) c_{i+1}(2\ell,D-2\ell). $$ \end{corollary} \proof Recall that $r=D-d$ is even by definition of the set $\Upsilon$. As $r+d=D$, it follows from the definition of $\pceq$ that the only pairs $(r',d') \in \Upsilon$ such that $(r',d') \pceq (r,d)$ are pairs with $r' \le r$ and $r'+d'=D$. Note that $r'+d'=D$ implies $r'$ is even, and so the result follows from Theorem \ref{thm:mult-formula}. \qed \begin{lemma} \label{lem:r+d=D} With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$ such that $r+d=D \; (1 \le r \le D-1)$. Assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. If there exists an irreducible $T$-module with endpoint $r$ and diameter $d$, then $$ \prod_{i=0}^{D-r-1} b_i(r,D-r) c_{i+1}(r,D-r) \ne 0. $$ \end{lemma} \proof Let $q, s^*$ be as in Lemma \ref{lem:caug}. Recall that $|q|>1$ and $s^*q^i \ne 1$ for $2 \le i \le 2D+1$. Using this, equations \eqref{cWqs}, \eqref{bWqs} and $b_0(r,d)=c_d(r,d)=h(q^{-t}-q^{t-D})$, we find that $b_i(r,D-r) \ne 0$ and $c_{i+1}(r,D-r) \ne 0$ for $0 \le i \le D-r-1$. The result follows. \qed \begin{corollary} \label{cor-a:r+d=D} With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$ such that $r+d=D \; (1 \le r \le D-1)$. Assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Then ${\rm mult}(r,d)$ is equal to the quantity $$ k_r \prod_{i=r}^{D-1} b_i c_{D-i} - \sum_{\ell=0}^{r/2-1} {\rm mult}(2\ell,D-2\ell) \prod_{i=r-2\ell}^{D-2\ell-1} b_i(2\ell,D-2\ell) c_{i+1}(2\ell,D-2\ell), $$ divided by the quantity $$ \prod_{i=0}^{D-r-1} b_i(r,D-r) c_{i+1}(r,D-r). $$ \end{corollary} % \proof Immediately from Corollary \ref{cor:r+d=D} and Lemma \ref{lem:r+d=D}. \qed \smallskip We now give explicit formulae for $mult(r,d)$ for some specific values of $r,d$. To do this we need the following definition. For $a,b \in \RR$ and for a non-negative integer $n$ we set $$ (a;b)_n = \prod_{i=1}^n (1-ab^{i-1}). $$ \begin{theorem} \label{thm:mult} With reference to Definition \ref{def:pairs} assume $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Then the following {\rm (i)--(iii)} hold. \begin{itemize} \item[{\rm (i)}] ${\rm mult}(0,D)=1$. \item[{\rm (ii)}] If $r \in \{2,4\}$, then $$ {\rm mult}(r,D-r)= \frac{(-1)^t q^{t(t-1)} (1-s^* q^{2r}) (q^{d+1};q)_r (-s^* q^{D+1};q)_t (s^*q^2;q^2)_{t-1}} {(q^2;q^2)_t (s^* q^{D+t+1};q)_t (s^*q^{D+d+2};q^2)_t}; $$ where $d=D-r$ and $t=(D-d)/2=r/2$. \item[{\rm (iii)}] If $r \in \{6,8\}$ and $D \in \{9,10,11\}$, then $$ {\rm mult}(r,D-r)= \frac{(-1)^t q^{t(t-1)} (1-s^* q^{2r}) (q^{d+1};q)_r (-s^* q^{D+1};q)_t (s^*q^2;q^2)_{t-1}} {(q^2;q^2)_t (s^* q^{D+t+1};q)_t (s^*q^{D+d+2};q^2)_t}; $$ where $d=D-r$ and $t=(D-d)/2=r/2$. \end{itemize} \end{theorem} \proof (i), (ii) This is \cite[Theorem 15.6 (i),(iii),(vii)]{Ca2}. \noindent (iii) The proof (although a bit tedious and lengthy) follows straightforward from Corollary \ref{cor-a:r+d=D} using \eqref{cWqs}, \eqref{bWqs}. We omit the details. \qed \begin{remark} With reference to Definition \ref{def:pairs} assume $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. We conjecture that the formula for {\rm mult}$(r,D-r)$ given in Theorem \ref{thm:mult} holds for any diameter $D$ and for any even number $r \le D$. See also \cite[Conjecture 15.8]{Ca2} for an extended conjecture about the multiplicities of irreducible $T$-modules of $\G$. However, for the purpose of this paper, Theorem \ref{thm:mult} suffices. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Some results about parameter $s^*$} \label{sec:bound} With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial, and let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. In this section we derive some restrictions on parameter $s^*$. We first recall some results of Caughman. \begin{theorem} \label{thm:q} (\cite[Theorem 4.1, Lemma 5.1, Lemma 6.6]{Ca5}) With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Then the following {\rm (i)--(iii)} hold. \begin{itemize} \item[{\rm (i)}] If $D \ge 6$, then $q > 1$. \item[{\rm (ii)}] If $q > 1$, then $-q^{-D-1} \le s^* < q^{-2D-1}$. \item[{\rm (iii)}] If $D \ge 7$ and $-q^{-13} \le s^* \le q^{-13}$, then $s^*=0$. \end{itemize} \end{theorem} \begin{lemma} \label{lem:beta} With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Set $\beta = q + 1/q$. If $D \ge 5$, then $\beta$ is a rational number. \end{lemma} \proof Assume that $\G$ is $Q$-polynomial with respect to $E_0, E_1, \ldots, E_D$ and let $\theta_1$ denote the eigenvalue of $\G$ corresponding to $E_1$. By \cite[Lemma 3.2]{Ca4} we have that $\theta_1 \ne -1$ and $$ \beta = \frac{\theta_1^2 + c_2 \theta_1 + b_2 (k-2)}{b_2(\theta_1 +1)}. $$ If $D \ge 5$ then $\theta_1$ is integer by \cite[Theorem 8.1.3]{Di}, see also \cite[Lemma 3.3(i)]{Ca4}. The result follows. \qed We note that it is easy to see that $q^2 + q^{-2} = \beta^2-2$, $q^3 + q^{-3} = \beta^3-3\beta$ and $q^4+q^{-4}=\beta^4-4\beta^2+2$. Also, if $D \ge 6$, then $q > 1$ by Theorem \ref{thm:q}(i), and so $\beta > 2$ in this case. The following result was proved by Lang. \begin{proposition} \label{prop:s1} (\cite[Lemma 9.3]{La}) With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. If $D \ge 5$, then $s^* \ne -q^{-D-3}$. \end{proposition} \begin{comment} \proof Assume on contrary that $D \ge 9$ and $s^* = -q^{-D-3}$. Observe that this implies $s^* < 0$ as $q>1$ by Theorem \ref{thm:q}(i). If $D \ge 10$, then $s^* = -q^{-D-3}$ implies $-q^{-13} \le s^* \le q^{-13}$. But then $s^*=0$ by Theorem \ref{thm:q}(iii), a contradiction. Assume now $D=9$. Then using Lemma \ref{lem:caug}(iii) we find $$ c_2 = \frac{2(q^2-q+1)(q^6-q^3+1)}{q(q^6-q^5+q^4-q^3+q^2-q+1)} = \frac{2(\beta - 1)(\beta^3-3\beta - 1)}{\beta^3-\beta^2-2\beta+1}, $$ where $\beta$ is as in Lemma \ref{lem:beta}. This shows that $\beta$ is a root of a polynomial with coefficients in $\ZZ$ and with leading coefficient equal to $2$. As $\beta$ is rational by Lemma \ref{lem:beta}, this implies that $\beta=n$ or $\beta=n/2$ for some integer $n$. Recall also that $\beta > 2$ (and so $n$ is positive). Now consider the above formula for $c_2$ and note that $$ c_2 = 2\beta - \frac{2 \beta^2-2\beta-2}{\beta^3-\beta^2-2\beta+1}. $$ This shows that $(2 \beta^2-2\beta-2) / (\beta^3-\beta^2-2\beta+1)$ is an integer. Observe that $2 \beta^2-2\beta-2$ and $\beta^3-\beta^2-2\beta+1$ are both positive for $\beta \ge 2$ and so $\beta^3-\beta^2-2\beta+1 \le 2\beta^2-2\beta-2$, or equivalently, $\beta^3-3\beta^2+ 3\le 0$. However, $\beta^3-3\beta^2+ 3 > 0$ for $\beta \ge 3$, and so $\beta=5/2$ (recall that $\beta > 2$). But this implies $c_2 = 171/43$, a contradiction. This shows that $s^* \ne -q^{-D-3}$. \qed \end{comment} \begin{proposition} \label{prop:s2} With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. If $D \ge 9$, then $s^* \ne -q^{-D-2}$. \end{proposition} \proof Assume on contrary that $D \ge 9$ and $s^* = -q^{-D-2}$. Observe that this implies $s^* < 0$ as $q>1$ by Theorem \ref{thm:q}(i). If $D \ge 11$, then $s^* = -q^{-D-2}$ implies $-q^{-13} \le s^* \le q^{-13}$. But then $s^*=0$ by Theorem \ref{thm:q}(iii), a contradiction. If $D \in \{9,10\}$ then the proof is similar to the proof of Proposition \ref{prop:s1} for the case $D=9$. Let $\beta$ be as in Lemma \ref{lem:beta}. Assume first that $D=10$. In this case we have $$ 2 c_2 = \beta^2+2\beta-1 - \frac{2\beta^2-\beta-3}{\beta^3-\beta^2-2\beta+1}, $$ which shows that $\beta$ is an algebraic integer. As $\beta$ is rational by Lemma \ref{lem:beta}, this implies that $\beta$ is an integer, and so $(2\beta^2-\beta-3)/(\beta^3-\beta^2-2\beta+1)$ is an integer. Observe that $2\beta^2-\beta-3$ and $\beta^3-\beta^2-2\beta+1$ are both positive for $\beta \ge 2$, so $2\beta^2-\beta-3 \ge \beta^3-\beta^2-2\beta+1$. But this implies $\beta=2$, a contradiction (recall that $\beta > 2$). Assume now $D=9$. In this case we have $$ 2 c_2 = \beta^2+2\beta-1 - \frac{2\beta^2+\beta-4}{\beta(\beta^2-3)}, $$ which again shows that $\beta$ is an algebraic integer. As $\beta$ is rational by Lemma \ref{lem:beta}, this implies that $\beta$ is an integer, and so $(2\beta^2+\beta-4)/(\beta(\beta^2-3))$ is an integer. Observe that $2\beta^2+\beta-4$ and $\beta(\beta^2-3)$ are both positive for $\beta \ge 2$, so $2\beta^2+\beta-4 \ge \beta(\beta^2-3)$. But this implies $\beta=2$, a contradiction. This shows that $s^* \ne -q^{-D-2}$. \qed \begin{proposition} \label{prop:s3} With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. If $D \ge 6$, then $s^* \ne -q^{-D-1}$. \end{proposition} \proof We assume $s^* = -q^{-D-1}$ and derive a contradiction. By Theorem \ref{thm:mult}(ii) we find that ${\rm mult}(2,D-2)=0$. But now $\G$ has, up to isomorphism, a unique irreducible $T$-module with endpoint $2$, and this module has diameter $D-4$. By \cite[Theorem 3.12]{Cu1}, $\G$ is $2$-homogeneous in the sense of Nomura \cite{No}. However, as $D \ge 6$ we have that $\G$ is $H(D,2)$ by \cite[Theorem 1.2]{No1} (see also \cite[Theorem 4.1]{Cu1}), a contradiction. This shows that $s^* \ne -q^{-D-1}$. \qed %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of the main theorem} \label{sec:main} In this section we prove our main theorem. To do this we first need the following result. \begin{theorem} \label{thm:bound} With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Assume further that $D \in \{9,10,11\}$. Then $s^* \ge -q^{-D-4}$. \end{theorem} \proof The result obviously holds if $s^* \ge 0$ (recall that $q > 1$ by Theorem \ref{thm:q}(i)), so assume that $s^* < 0$. Consider ${\rm mult}(2,D-2)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(ii) that $$ (1+s^* q^{D+1}) \ge 0. $$ As $s^* \ne -1/q^{D+1}$ by Proposition \ref{prop:s3}, we have that $s^* > -q^{-D-1}$. Consider now ${\rm mult}(4,D-4)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(ii) that $$ (1+s^* q^{D+1})(1+s^* q^{D+2}) \ge 0. $$ We have just proved that $s^* > -q^{-D-1}$ and so $1+s^* q^{D+1} > 0$, implying that $1+s^* q^{D+2} \ge 0$. As $s^* \ne -q^{-D-2}$ by Proposition \ref{prop:s2}, this shows that $s^* > -q^{-D-2}$. Consider now ${\rm mult}(6,D-6)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(iii) that $$ (1+s^* q^{D+1})(1+s^* q^{D+2}) (1+s^* q^{D+3})\ge 0. $$ We have just proved that $s^* > -q^{-D-2}$ and so $(1+s^* q^{D+1})(1+s^* q^{D+2}) > 0$, implying that $1+s^* q^{D+3} \ge 0$. As $s^* \ne -q^{-D-3}$ by Proposition \ref{prop:s1}, this shows that $s^* > -q^{-D-3}$. Finally, consider ${\rm mult}(8,D-8)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(iii) that $$ (1+s^* q^{D+1})(1+s^* q^{D+2}) (1+s^* q^{D+3}) (1+s^* q^{D+4})\ge 0. $$ We have just proved that $s^* > -q^{-D-3}$ and so $(1+s^* q^{D+1})(1+s^* q^{D+2})(1+s^* q^{D+3}) > 0$, implying that $1+s^* q^{D+4} \ge 0$. This shows that $s^* \ge -q^{-D-4}$. \qed We are now ready to prove our main result. \begin{theorem} \label{thm:main} Let $\G$ denote a bipartite distance-regular graph with diameter $D \ge 9$. Then $\G$ is $Q$-polynomial if and only if one of the following (i)--(iv) holds: \begin{itemize} \item[(i)] $\G$ is the ordinary $2D$-cycle. \item[(ii)] $\G$ is the Hamming cube $H(D,2)$. \item[(iii)] $\G$ is the antipodal quotient of the Hamming cube $H(2D,2)$. \item[(iv)] The intersection numbers of $\G$ satisfy \begin{equation} \label{eq:int} c_i = \frac{q^i - 1}{q-1}, \qquad b_i = \frac{q^D-q^i}{q-1} \qquad (0 \le i \le D), \end{equation} where $q$ is an integer at least $2$. \end{itemize} \end{theorem} \proof If $D \ge 12$ then this is \cite[Theorem 1.1]{Ca5}, therefore we assume $D \in \{9,10,11\}$. Assume first that $\G$ is $Q$-polynomial and that $\G$ is not a $2D$-cycle, $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. By Theorem \ref{thm:bound} we have $s^* \ge -q^{-D-4}$. Together with Theorem \ref{thm:q}(ii) this implies that $-q^{-13} \le s^* \le q^{-13}$, and so $s^*=0$ by Theorem \ref{thm:q}(iii). It follows from Lemma \ref{lem:caug} that $$ c_i = \frac{q^i - 1}{q-1}, \qquad b_i = \frac{q^D-q^i}{q-1} \qquad (0 \le i \le D). $$ But now $c_2 = q+1$, and so $q$ is an integer. As $q > 1$ we have that $q \ge 2$. Concerning the converse, assume that one of the cases (i)-(iv) holds. If (i) or (iii) holds, then $\G$ is $Q$-polynomial by \cite[Corollary 8.5.3(i),(iii)]{BCN}. If (ii) or (iv) holds, then $\G$ has classical parameters and it is $Q$-polynomial by \cite[Corollary 8.4.2]{BCN}. \qed \subsection*{Acknowledgement} The author thanks John Caughman for giving this paper a close reading and offering valuable suggestions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{99} %{\small \bibitem{BI} E.\ Bannai, T.\ Ito, {\it Algebraic Combinatorics I: Association Schemes}, The Benjamin-Cummings Lecture Notes Ser. 58, Menlo Park, CA, 1984. \bibitem{BCN} A.\ E.\ Brouwer, A.\ M.\ Cohen, and A.\ Neumaier, {\it Distance-Regular Graphs}, Springer-Verlag, Berlin, Heidelberg, 1989. \bibitem{Ca1} J.\ S.\ Caughman, Spectra of bipartite $P$- and $Q$-polynomial association schemes, {\em Graphs Combin.} {\bf 14} (1998), 321--343. \bibitem{Ca2} J.\ S.\ Caughman, The Terwilliger algebras of bipartite $P$- and $Q$-polynomial schemes, {\em Discrete Math.} {\bf 196} (1999), 65--95. \bibitem{Ca3} J.\ S.\ Caughman, Bipartite $Q$-polynomial quotients of antipodal distance-regular graphs, {\em J. Combin. Theory Ser. B} {\bf 76} (1999), 291--296. \bibitem{Ca4} J.\ S.\ Caughman, The parameters of bipartite $Q$-polynomial distance-regular graphs, {\em J. Algebraic Combin.} {\bf 15} (2002), 223--229. \bibitem{Ca5} J.\ S.\ Caughman, Bipartite $Q$-polynomial distance-regular graphs, {\it Graphs Combin.} {\bf 20} (2004), 47--57. \bibitem{Cu1} B.\ Curtin, Almost $2$-homogeneous bipartite distance-regular graphs, {\em European J. Combin.} {\bf 21} (2000), 865--876. \bibitem{Di} G. Dickie, {\it Q-polynomial structures for association schemes and distance-regular graphs}, Ph.D. Thesis, University of Wisconsin, 1995. \bibitem{DKT} E.\ R.\ van Dam, J.\ H.\ Koolen, and H.\ Tanaka, Distance-regular graphs, {\em Electron. J. Combin.} {\#DS22} (2016). \bibitem{Go} C.\ D.\ Godsil, {\it Algebraic combinatorics}, Chapman and Hall, New York, 1993. \bibitem{La} M.\ S.\ Lang, Bipartite distance-regular graphs: The Q -polynomial property and pseudo primitive idempotents, {\em Discrete Math.} {\bf 331} (2014), 27--35. \bibitem{No} K.\ Nomura, Homogeneous graphs and regular near polygons, {\em J. Combin. Theory Ser. B} {\bf 60} (1994), 63--71. \bibitem{No1} K.\ Nomura, Spin models on bipartite distance-regular graphs, {\em J. Combin. Theory Ser. B} {\bf 64 (2)} (1994), 300--313. \end{thebibliography} \end{document}