¿^creative ^commor
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 187-210
https://doi.org/10.26493/1855-3974.2193.0b0
(Also available at http://amc-journal.eu)
ARS MATHEMATICA CONTEMPORANEA
On a certain class of 1-thin distance-regular
graphs
Mark S. MacLean ©
Mathematics Department, Seattle University, 901 Twelfth Avenue, Seattle WA 98122-1090, USA
Stefko Miklavic * ©
University ofPrimorska, Andrej Marusic Institute, Muzejski trg 2, 6000 Koper, Slovenia
Received 9 December 2019, accepted 2 June 2020, published online 18 October 2020
Abstract
Let r denote a non-bipartite distance-regular graph with vertex set X, diameter D > 3, and valency k > 3. Fix x e X and let T = T(x) denote the Terwilliger algebra of r with respect to x. For any z e X and for 0 < i < D, let ^(z) = {w e X : d(z, w) = i}. For y e ri(x), abbreviate Dj = Dj(x, y) = ^(x) n r(y) (0 < i, j < D). For 1 < i < D and for a given y, we define maps Hi : D| ^ Z and V : D|_1 U D]-1 ^ Z as follows:
Hi(z) = |ri(z) n d]_ 11, Vi(z) = |ri(z) n d]_ 11.
We assume that for every y e r 1 (x) and for 2 < i < D, the corresponding maps Hi and V are constant, and that these constants do not depend on the choice of y. We further assume that the constant value of Hi is nonzero for 2 < i < D. We show that every irreducible T-module of endpoint 1 is thin. Furthermore, we show r has exactly three irreducible T-modules of endpoint 1, up to isomorphism, if and only if three certain combinatorial conditions hold. As examples, we show that the Johnson graphs J (n, m) where n > 7, 3 < m < n/2 satisfy all of these conditions.
Keywords: Distance-regular graph, Terwilliger algebra, subconstituent algebra. Math. Subj. Class. (2020): 05E30
* The author acknowledges the financial support from the Slovenian Research Agency (research core funding No. P1-0285 and research projects N1-0032, N1-0038, J1-5433, J1-6720, J1-7051). The author acknowledges the European Commission for funding the InnoRenew CoE project (Grant Agreement #739574) under the Hori-zon2020 Widespread-Teaming program and the Republic of Slovenia (Investment funding of the Republic of Slovenia and the European Union of the European regional Development Fund).
E-mail addresses: macleanm@seattleu.edu (Mark S. MacLean), stefko.miklavic@upr.si (Stefko Miklavic)
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
188
Ars Math. Contemp. 18 (2020) 187-210
1	Introduction
This paper is motivated by a desire to find a combinatorial characterization of the distance-regular graphs with exactly three irreducible modules (up to isomorphism) of the Ter-williger algebra with endpoint 1, all of which are thin (see Sections 2, 3 for formal definitions). This is a difficult problem which we will not complete in this paper. To begin, we find combinatorial conditions under which a distance-regular graph is 1-thin. When these combinatorial conditions hold, we identify additional combinatorial conditions that hold if and only if the distance-regular graph has exactly three irreducible T-modules of endpoint 1, up to isomorphism.
Let r denote a distance-regular graph with diameter D > 3 and valency k > 3. Let X denote the vertex set of r. For x e X, let T = T(x) denote the Terwilliger algebra of r with respect to x. It is known that there exists a unique irreducible T-module with endpoint 0, and this module is thin [5, Proposition 8.4]. It is also known that r is bipartite or almost-bipartite if and only if r has exactly one irreducible T-module of endpoint 1, up to isomorphism, and this module is thin [4, Theorem 1.3]. Furthermore, Curtin and Nomura have shown that r is pseudo-1-homogeneous with respect to x with ai =0 if and only if r has exactly two irreducible T-modules of endpoint 1, up to isomorphism, both of which are thin [4, Theorem 1.6].
For any z e X and any integer i > 0, let r*(z) = {w e X : d(z, w) = i}. For y e r1 (x) and integers i, j > 0, abbreviate Dj = Dj (x, y) = r*(x) n Tj (y). For 1 < i < D and for a given y, we define maps H* : D* ^ Z, K* : D* ^ Z and V : Dîi_1 U D*-1 ^ Z as follows:
Hi(z) = |r (z) n d*-1|, Ki(z) = |ri(z) n Di+1|, V*(z) = |ri(z) n Di-11. Our main result is the following.
Theorem 1.1. Let r = (X, R) denote a non-bipartite distance-regular graph with diameter D > 3 and valency k > 3, and fix vertex x e X. Assume that for every y e r1(x) and for 2 < i < D, the corresponding maps H* and V* are constant, and that these constants do not depend on the choice of y. Also assume that the constant value of H* is nonzero for
2	< i < D. Then r is 1-thin with respect to x.
We need the following definition.
Definition 1.2. With the assumptions of Theorem 1.1, for y e r1(x) let Dj = Dj (x,y) (0 < i, j < D) and let K1 denote the corresponding map. Let B = B(y) denote the adjacency matrix of the subgraph of r induced on D1. Observe that B e MatDi (C), and
so the rows and the columns of B are indexed by the elements of D1. Let j e Cd1 denote the all-ones column vector with rows indexed by the elements of D11.
With reference to Definition 1.2, we denote by P1, P2 and P3 the following properties of r:
P1: There exists y e r1(x) such that K1 is not a constant.
P2: For every y, z e r1(x) with d(y, z) e {0, 2}, the number of walks of length 3 inside r1(x) from y to z is a constant number, which depends only on d(y, z) (and not on the choice of y, z).
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
189
P3: There exist scalars a, ft such that for every y G ^(x) we have
B2j = aBj + j
We prove the following.
Theorem 1.3. With reference to Definition 1.2, r has exactly three irreducible T-modules of endpoint 1, up to isomorphism, if and only if properties P1, P2, and P3 hold. We note these three T-modules are all thin by Theorem 1.1.
Finally, we show that the Johnson graphs J (n, m) where n > 7, 3 < m < n/2 satisfy the assumptions in Theorem 1.1 and the equivalent conditions in Theorem 1.3.
2 Preliminaries
In this section we review some definitions and basic results concerning distance-regular graphs. See the book of Brouwer, Cohen and Neumaier [2] for more background information.
Let C denote the complex number field and let X denote a nonempty finite set. Let MatX (C) denote the C-algebra consisting of all matrices whose rows and columns are indexed by X and whose entries are in C. Let V = CX denote the vector space over C consisting of column vectors whose coordinates are indexed by X and whose entries are in C. We observe MatX (C) acts on V by left multiplication. We call V the standard module. We endow V with the Hermitian inner product (, } that satisfies (u, v) = v/'v for u, v G V, where t denotes transpose and _ denotes complex conjugation. For y G X let y denote the element of V with a 1 in the y coordinate and 0 in all other coordinates. We observe {y | y G X} is an orthonormal basis for V. The following will be useful: for each B G MatX (C) we have
(u, Bv) = (Btu, v)	(u, v G V).	(2.1)
Let r = (X, R) denote a finite, undirected, connected graph, without loops or multiple edges, with vertex set X and edge set R. Let d denote the path-length distance function for r, and set D := max{d(x, y) | x, y G X}. We call D the diameter of r. For a vertex x g X and an integer i > 0 let ^(x) denote the set of vertices at distance i from x. We abbreviate r(x) = r1(x). For an integer k > 0 we say r is regular with valency k whenever |r(x) | = k for all x G X. We say r is distance-regular whenever for all integers h, i, j (0 < h, i, j < D) and for all vertices x, y G X with d(x, y) = h, the number
pj = |r<(x) n r (y)|
is independent of x and y. The phj are called the intersection numbers of r.
For the rest of this paper we assume r is distance-regular with diameter D > 3. Note that phj = phji for 0 < h, i, j < D. For convenience set q := p1i-1 (1 < i < D), a := Pii (0 < i < D), bi := p1i+1 (0 < i < D - 1), k := p0i (0 < i < D), and co = bD = 0. By the triangle inequality the following hold for 0 < h, i, j < D: (i) pj = 0 if one of h, i, j is greater than the sum of the other two; (ii) pj =0 if one of h, i, j equals the sum of the other two. In particular ci =0 for 1 < i < D and bi = 0 for 0 < i < D — 1.
190
Ars Math. Contemp. 18 (2020) 187-210
We observe that r is regular with valency k = k1 = bo and that cj + aj + bj = k for 0 < i < D. Note that kj = |ri(x)| for x e X and 0 < i < D.
We recall the Bose-Mesner algebra of r. For 0 < i < D let Aj denote the matrix in Matx (C) with (x, y)-entry
(Aj)xy ^ if d(X,y) = i, (x,y e X).	(2.2)
( )xy \0 ifd(x,y) = i ( ,y )
We call Aj the ith distance matrix of r. We abbreviate A := A1 and call this the adjacency matrix of r. We observe (ai) A0 = I; (aii) J2 D= o Aj = J; (aiii) Aj = Aj (0 < i < D); (aiv) Af = Aj (0 < i < D); (av) AjAj = ^D=o PjAh (0 < i, j < D), where I (resp. J) denotes the identity matrix (resp. all 1's matrix) in MatX (C). Using these facts we find A0, A1,..., Ad is a basis for a commutative subalgebra M of MatX (C). We call M the Bose-Mesner algebra of r. It turns out that A generates M [1, p. 190]. By [2, p. 45], M has a second basis Eo, E1,..., Ed such that (ei) Eo — |X| 1J; (eii) y^i=o
Ej = I;
(eiii) Ej = Ej (0 < i < D); (eiv) Ef = Ej (0 < i < D); (ev) EjEj = SjjEi (0 < i, j < D). We call Eo, E1,..., ED the primitive idempotents of r.
3 The Terwilliger algebra
Let r = (X, R) denote a distance-regular graph with diameter D > 3 and valency k > 3. In this section we recall the dual Bose-Mesner algebra and the Terwilliger algebra of r. Fix a vertex x e X. We view x as a "base vertex." For 0 < i < D let E* = E* (x) denote the diagonal matrix in MatX (C) with (y, y)-entry
(E*)yy = (1 if d(x,y) = i, (y e X). [0 if d(x,y) = i
We call E* the ith dual idempotent of r with respect to x [11, p. 378]. We observe (i) ED=o E* = I; (ii) E* = Ej* (0 < i < D); (iii) Ef = E* (0 < i < D); (iv) E*E* = JjjE* (0 < i, j < D). By these facts E* E*,..., ED form a basis for a commutative subalgebra M* = M* (x) of MatX (C). We call M* the dual Bose-Mesner algebra of r with respect to x [11, p. 378]. For 0 < i < D we have
Ej*V = span{y | y e T(x)}
so dim E* V = kj. We call E* V the ith subconstituent of r with respect to x. Note that
V = E|*V + E*V +-----+ EDV	(orthogonal direct sum).
Moreover E* is the projection from V onto E* V for 0 < i < D.
We recall the Terwilliger algebra of r. Let T = T(x) denote the subalgebra of MatX (C) generated by M, M*. We call T the Terwilliger algebra of r with respect to x [1 , Definition 3.3]. Recall M (resp. M*) is generated by A (resp. E*, E*,..., ED) so T is generated by A, E*, E*,..., ED. We observe T has finite dimension. By construction T is closed under the conjugate-transpose map so T is semi-simple [11, Lemma 3.4(i)].
By a T-module we mean a subspace W of V such that SW C W for all S e T. Let W denote a T-module. Then W is said to be irreducible whenever W is nonzero and W contains no T-modules other than 0 and W.
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
191
By [6, Corollary 6.2] any T-module is an orthogonal direct sum of irreducible T-modules. In particular the standard module V is an orthogonal direct sum of irreducible T-modules. Let W, W' denote T-modules. By an isomorphism of T-modules from W to W' we mean an isomorphism of vector spaces a : W ^ W' such that (aS - Sa) W = 0 for all S G T. The T-modules W, W' are said to be isomorphic whenever there exists an isomorphism of T-modules from W to W'. By [3, Lemma 3.3] any two non-isomorphic irreducible T-modules are orthogonal. Let W denote an irreducible T-module. By [11, Lemma 3.4(iii)] W is an orthogonal direct sum of the nonvanishing spaces among E0* W, E* W,..., E*d W. By the endpoint of W we mean minji | 0 < i < D, E*W = 0}. By the diameter of W we mean |{i | 0 < i < D, E*W = 0}| - 1. We say W is thin if dim(E*W) < 1 for 0 < i < D. We say r is 1-thin with respect to x if every T-module with endpoint 1 is thin.
By [5, Proposition 8.3, Proposition 8.4] MX is the unique irreducible T-module with endpoint 0 and the unique irreducible T-module with diameter D. Moreover MX is the unique irreducible T-module on which E0 does not vanish. We call MX the primary module. We observe that vectors si (0 < i < D) form a basis for MX, where
si = ^ y.	(3.1)
yeri(x)
Lemma 3.1. Let r = (X, R) denote a distance-regular graph with diameter D > 3 and distance matrices Ai (0 < i < D). Fix a vertex x G X and let E* = E*(x) (0 < i < D) denote the dual idempotents with respect to x. For 0 < h, i, j < D, the matrix Eh*AiEj* = 0 whenever any one of h, i, j is bigger than the sum of the other two.
Proof. Routine using elementary matrix multiplication.	□
The following result will be crucial later in the paper.
Lemma 3.2. Let r = (X, R) denote a distance-regular graph with diameter D > 3. Fix a vertex x G X and let E* = E*(x) (0 < i < D) denote the dual idempotents with respect to x. Let T = T(x) denote the Terwilliger algebra of r with respect to x. Assume that (up to isomorphism) r has exactly three irreducible T-modules with endpoint 1, and that these modules are all thin. Let F\, F2, F3, F4, F5 G T and pick an integer i, 1 < i < D. Then the matrices
Z?* T? Z?* Z?* T? Z?* Z?* Z? Z?* Z?* Z? Z?* Z?* Z? Z?* Ei F iE 1, Ei F2E 1, Ei F3E 1, Ei F4E 1, Ei F5E 1
are linearly dependent.
Proof. Let V0 denote the primary module of r, and let Ve (1 < i < 3) denote pairwise non-isomorphic irreducible T-modules with endpoint 1. Define vectors ve (0 < i < 3) as follows. If E* Ve = 0, then let ve = 0. Otherwise, let ve be an arbitrary nonzero vector of E* V«. Furthermore, for 0 < i < 3 fix a nonzero ue G E* V«. As modules Ve (0 < i < 3) are thin, there exist scalars Aj (1 < j < 5, 0 < i < 3) such that
E* Fj E*u« = A« v«.
192
Ars Math. Contemp. 18 (2020) 187-210
Consider now the following homogeneous system of linear equations:
^0	A2	A3	A4	A0\		( a A		/0\
A1	A2	Ai1i	A4	A5		«2		0
A2	A2	Ai	A4	A2		«3		0
VAi	A2	A3	A4	A5)		«4 w		w
(3.2)
Observe that the above system has a nontrivial solution, and let (m 1, M2, M3, M4, M5)1 denote one of its nontrivial solutions. We will now show that J25=1 MjE*FjE{ = 0. First, pick an arbitrary u G E^V,, for some i (0 < i < 3). As module V, is thin, there exists a scalar A, such that u = Au,. Now we have
5	5	5	5
Y Mj E*Fj Eiu = A Y Mj E*Fj EJu, = A Y Mj A, v, = Av, Y Mj Aj = 0. (3.3)
j=1 j=1 j=1 j=1
Assume now that W is an irreducible T-module with endpoint 1 and note that W is isomorphic to V, for some 1 < i < 3. Pick arbitrary w G E^W. Let a: V, ^ W be a T-module isomorphism and let u G V, be such that w = a(u). Now by (3.3) we have that
5	5	, 5	s
YMjE*FjEJw = YMjE;FjEJa(u) = a ( YMjE*FjE?u J = 0. (3.4)
j=1 j=1 j=1
j=i
j=i
For 1 < i < 3 let Vl denote the sum of all irreducible T-modules with endpoint 1, which are isomorphic to Vi. Observe that
Eî V = Eî Vo + Eî V i + Eî V2 + E î V3 (orthogonal sum).
(3.5)
Pick now an arbitrary v G EJV. Note that by (3.5) v is a sum of vectors v5, where £ belongs to some index set S, and each v5 is contained in E lW5, where W5 is either V0, or isomorphic to Vi for some 1 < i < 3. By (3.4) we have that £5= 1 MjElFjEJv^ = 0 for each £ G S, and consequently5=1 MjElFjEJ v = 0. This shows that £5= 1 MjElFjEl = 0. As at least one of Mj (1 < j < 5) is nonzero (recall that (m 1, M2, M3, M4, Ms)4 is a nontrivial solution of (3.2)), the result follows.	□
4 The local eigenvalues
In order to discuss the thin irreducible T-modules with endpoint 1, we first recall some parameters called the local eigenvalues. We will use the notation from [7].
Definition 4.1. Let r = (X, R) denote a distance-regular graph with diameter D > 3, valency k > 3 and adjacency matrix A. Fix a vertex x G X. We let A = A(x) denote the graph (X, R), where
X = {y G X | d(x, y) = 1}, R= {yz | y, z G X , d(y,z) = 1}.
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
193
The graph A has exactly k vertices and is regular with valency a 1. We let A denote the adjacency matrix of A. The matrix A is symmetric with real entries, and thus A is diagonalizable with real eigenvalues. We let n 1denote the eigenvalues of A. We call n 1, n2,..., Ik the local eigenvalues of r with respect to x.
We now consider the first subconstituent E\ V. We recall the dimension of El V is k. Observe E\V is invariant under the action of E\AEJ\ We note that for an appropriate ordering of the vertices of r, we have
ElAEl = (A 0),
where A is from Definition 4.1. Hence the action of El AEl on El V is essentially the adjacency map for A. In particular the action of E AE on E V is diagonalizable with eigenvalues n 1, n2,..., nk. We observe the vector s 1 from (3.1) is contained in E l V. One may easily show that s1 is an eigenvector for E l AE l with eigenvalue a1. Reordering the eigenvalues if necessary, we have n1 = a1. For the rest of this paper, we assume the local eigenvalues are ordered in this way. Now consider the the orthogonal complement of s1 in El V. By (2.1), this space is invariant under multiplication by El AEl. Thus the restriction of the matrix El AE l to this space is diagonalizable with eigenvalues — .
Definition 4.2. Let r = (X, R) denote a distance-regular graph with diameter D > 3, valency k > 3 and adjacency matrix A. Fix a vertex x G X, and let T = T(x) denote the Terwilliger algebra of r with respect to x. Let W denote a thin irreducible T-module with endpoint 1. Observe El W is a 1-dimensional eigenspace for E l AE l; let n denote the corresponding eigenvalue. We observe El W is contained in E l V so n is one of n2, n3,..., nk. We refer to n as the local eigenvalue of W.
Theorem 4.3 ([ , Theorem 12.1]). Let r = (X, R) denote a distance-regular graph with diameter D > 3 and valency k > 3. Fix a vertex x G X, and let T = T(x) denote the Terwilliger algebra of r with respect to x. Let W denote a thin irreducible T-module with endpoint 1 and local eigenvalue n. Let W' denote an irreducible T-module. Then the following (i), (ii) are equivalent.
(i)	W and W' are isomorphic as T-modules.
(ii)	W' is thin with endpoint 1 and local eigenvalue n.
Let r = (X, R) denote a distance-regular graph with diameter D > 3 and valency k > 3. Fix a vertex x G X, and let T = T(x) denote the Terwilliger algebra of r with respect to x. Recall that in Section 3, we said that the standard module V is an orthogonal direct sum of irreducible T-modules. Let W denote an irreducible T-module. By the multiplicity of W, we mean the number of irreducible T-modules in the above decomposition which are isomorphic to W. It is well-known that this number is independent of the decomposition of V.
Theorem 4.4 ([ , Theorem 12.9]). Let r = (X, R) denote a distance-regular graph with diameter D > 3 and valency k > 3. Fix a vertex x G X, and let T = T(x) denote the Terwilliger algebra of r with respect to x. With reference to Definition 4.1, the following are equivalent.
194
Ars Math. Contemp. 18 (2020) 187-210
(i)	For every i (2 < i < k), there exists a thin irreducible T-module W of endpoint 1 with local eigenvalue ni. Moreover, the multiplicity with which n appears in the list n2,	is equal to the multiplicity with which W appears in the standard decomposition of V.
(ii)	r is 1-thin with respect to x.
With reference to Theorem 4.4, we note that if r is 1-thin with respect to x, then the number of non-isomorphic irreducible T-modules of endpoint 1 is equal to the number of distinct local eigenvalues in the list — We will need this fact later in the paper.
5 The matrices L, F, R
Let r = (X, R) denote a distance-regular graph with diameter D > 3. Fix a vertex x G X. In this section we recall certain matrices L, F, R of the Terwilliger algebra T = T(x).
Definition 5.1. Let r = (X, R) denote a distance-regular graph with diameter D > 3 and adjacency matrix A. Fix a vertex x G X and let E* = E* (x) (0 < i < D) denote the dual idempotents with respect to x. We define matrices L = L(x), F = F(x), R = R(x) by
D	D	D-1
L = £ E*-iAEh,	F = £ EhAEh,	R = £ E*+1AE*.
h=1 h=0 h=0
Note that A = L + F + R [ , Lemma 4.4]. We call L, F, and R the lowering matrix, the flat matrix, and the raising matrix of r with respect to x, respectively.
Lemma 5.2. Let r = (X, R) denote a distance-regular graph with diameter D > 3 and valency k > 3. We fix x G X and let L = L(x), F = F(x) and R = R(x) be as in Definition 5.1. For y, z G X the following (i)-(iii) hold.
(i)	Lzy = 1 if d(z,y) = 1 and d(x, z) = d(x,y) — 1, and 0 otherwise.
(ii)	Fzy = 1 if d(z, y) = 1 and d(x, z) = d(x, y), and 0 otherwise.
(iii)	Rzy = 1 if d(z, y) = 1 and d(x, z) = d(x, y) + 1, and 0 otherwise.
Proof. Immediate from Definition 5.1 and elementary matrix multiplication.	□
With the notation of Lemma 5.2, we display the (z, y)-entry of certain products of the matrices L, F and R. To do this we need another definition.
A sequence of vertices [y0, y1,..., yt] of r is a walk in r if yi-1yi is an edge for
1 < i < t.
Lemma 5.3. Let r = (X, R) denote a distance-regular graph with diameter D > 3 and valency k > 3. We fix x G X and let L = L(x), F = F(x) and R = R(x) be as in Definition 5.1. Choose y, z G X and let m denote a positive integer. Assume that y G ri(x). Then the following (i)-(vi) hold.
(i)	The (z, y)-entry of Rm is equal to the number of walks [y = y0, y1,..., ym = z], such that yj G ri+j (x) for 0 < j < m.
(ii)	The (z, y)-entryof RmL is equal to the number of walks [y = y0, y1,..., ym+1 = z], such that yj G ri-2+j- (x) for 1 < j < m +1.
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
195
(iii)	The (z, y)-entry of LRm is equal to the number of walks [y = y0,y1,..., ym+1 = z], such that yj G ri+j (x) for 0 < j < m and ym+1 G ri+m-1(x).
(iv)	The (z, y)-entry of RmF is equal to the number of walks [y = y0,y1,..., ym+1 = z], such that yj G ri-1+j (x) for 1 < j < m +1.
(v)	The (z, y)-entry of FRm is equal to the number of walks [y = y0,y1,..., ym+1 = z], such that yj G ri+j-(x) for 0 < j < m and ym+1 G ri+m(x).
(vi)	The (z, y)-entry of Fm is equal to the number of walks [y = y0, y1,...,ym = z], such that yj G Tj(x) for 0 < j < m.
Proof. Immediate from Lemma 5.2 and elementary matrix multiplication.	□
6 The sets Dj
Let r = (X, R) denote a distance-regular graph with diameter D > 3. In this section we display a certain partition of X that we find useful.
Definition 6.1. Let r = (X, R) denote a distance-regular graph with diameter D > 3 and valency k > 3. Pick x G X and y G r(x). For 0 < i,j < D we define Dj = Dj(x, y) by
Dj =Ti(x) n r (y).
For notational convenience we set Dj = 0 if i or j is contained in {-1,D + 1}. Please refer to Figure 1 for a diagram of this partition.
Figure 1: The partition with reference to Definition 6.1.
We now recall some properties of sets Dj.
Lemma 6.2 ([10, Lemma 4.2]). With reference to Definition 6.1 the following (i), (ii) hold for 0 < i,j < D.
(i)	|Dj | = pj.
(ii)	Dj = 0 if and only if pj = 0.
Observe that for 1 < i < D we have p1,i_1 = ciki/k = 0 by [ , p. 134]. Therefore, D*_1 and D*-1 are nonempty for 1 < i < D.
Lemma 6.3 ([9, Lemma 2.11]). With reference to Definition 6.1 pick an integer i (1 < i < D). Then the following (i), (ii) hold.
196
Ars Math. Contemp. 18 (2020) 187-210
-1
a.
(i)	Each z € D|_1 (resp. D
(a)	precisely
(b)	precisely
(c)	precisely
(d)	precisely
(e)	precisely
(ii)	Each z € D| is adjacent to
(a)	precisely
(b)	precisely
(c)	precisely
(d)	precisely
(e)	precisely
) is adjacent to
ci-1
d - ci-i - |r(z) n d*-ai-1 - |r(z) n Di-1| bi
- ai-1 + |r(z) n d*-
vertices in Di-1 (resp. D. vertices in D*-1 (resp. D. vertices in D*-1 (resp. D] vertices in D*+1 (resp. D. vertices in Di.
-1),
--11),
i+1),
c* - |r(z) n d; ci - |r(z) n d bi - |r(z) n d bi - |r(z) n d
-11
-1| i+1| +11
+1|
- bi - Ci + |r(z) n d*-1| + |r(z) n Dj+H
vertices in D*-1, vertices in Di-1, vertices in D®+1, vertices in D®+1, vertices in Di.
In view of the above lemma we have the following definition.
Definition 6.4. With reference to Definition 6.1, for 1 < i < D we define maps Hi: D| ^
Z, Ki: Di ^ Z and Vi: Di_ 1 U Dp1 ^ Z as follows:
Hi(z) = |r(z) n d*-1|,
Ki(z) = |r(z) n d*+1|,
Vi(z) = |r(z) n d*-1|.
We have the following observation.
Lemma 6.5. With reference to Definition 6.4, fix an integer i (2 < i < D) and assume that there exist integers m1; m2, such that Vi(z) = m1 for every z G Dp1 and Vi(z) = m2 for every z G D*-1. Then m1 = m2.
Proof. By Lemma 6.3(i) and using a simple double-counting argument we find that
|Di-1 |(c* - Ci-1 - m1) = 1|(c* - Ci-1 - m2).
As |Di 11 = |Di_11 = 0 by the comment below Lemma 6.2, the result follows. For the rest of the paper we assume the following situation.
□
Definition 6.6. Let r = (X, R) denote a non-bipartite distance-regular graph with diameter D > 3, valency k > 3, and distance matrices Ai (0 < i < D). We abbreviate A := A1. Fix x € X and let E* = E*(x) (0 < i < D) denote the dual idempotents with respect to x. Let T = T(x) denote the Terwilliger algebra with respect to x. Let A = A(x) be as in Definition 4.1. Let matrices L = L(x), F = F(x), R = R(x) be as defined in Definition 5.1. For y € r(x), let sets Dj(x, y) (0 < i,j < D) and the corresponding maps Hi,Ki,Vi (1 < i < D) be as defined in Definition 6.1 and Definition 6.4. We assume that for every y € r(x) and for every 2 < i < D, the corresponding maps Hi and Vi are constant, and that these constants do not depend on the choice of y. We denote the constant value of Hi (Vi, respectively) by hi (vi, respectively). We further assume that hi = 0 for 2 < i < D.
Remark 6.7. With reference to Definition 6.6, pick y € r(x) and let Dj = Dj (x,y) (0 < i, j < D). Since r is assumed to be non-bipartite, a = 0 for some integer j (1 < j < D). It follows that Dj = 0 by Lemma 6.2(ii) and [ , p. 127]. But since each
|
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
197
hi = 0 (2 < i < D), we conclude each of sets Dj_ ^ Dj_2,..., D{ is nonempty. Since D{ = 0, we have a i = 0. Now by [2, Proposition 5.5.1], we find ai = 0 for 1 < i < D -1. Thus Di = 0 for 1 < i < D - 1. However, with our assumptions of Definition 6.6, it is possible that aD =0 and D^ = 0. In this case, we make the convention that hD := 1. Finally, we wish to make clear that while we are assuming the maps Hi and Vi are constant for 2 < i < D, we are not making any such global assumptions about the maps Ki.
7 Some products in T
With reference to Definition 6.6, in this section we display the values of the entries of certain products in T.
Lemma 7.1. With reference to Definition 6.6, pick y G r(x) and let Dj = Dj (x, y) (0 < i,j < D). Pick an integer i (1 < i < D), and let z G ri(x). Then the following (i)-(iii) hold.
(i) (Ri- 1)
zy
ci_ici_2 ••• C 1 ifZ G D|_ 1, 0	otherwise.
(ii) (RiL)zy = CiCi_ i ••• c i.
biCiCi_i • • • c i (iii) (LRi)zy = <( (bi - Ki(z))CiCi_ i • • • c i
f z G Di_ i, if z G Di,
(Ci+i - Ci - Vi+ i)cici_ i • • • c i if z G D|+ i.
Proof. First we observe that, by the triangle inequality, we have d(y, z) G {i - 1, i, i + 1}.
(i):	By Lemma 5.3(i), the (z, y)-entry of Ri_ i is equal to the number of walks [y = y0,y i,... ,yi_ i = z], such that yj G ri +j(x) for 0 < j < i - 1. Observe that there are no such walks if d(y, z) > i. If d(y, z) = i - 1, then it is easy to see that yj G j i (x ) n r (y) = Dj+i for 0 < j < i - 1. Lemma 6.3(i) now implies that the number of such walks is equal to ci_ici_2 • • • c i.
(ii):	By Lemma 5.3(ii), the (z, y)-entry of RiL is equal to the number of walks [y = y0,y i,... ,yi+i = z], such that yj G Tj_ i(x) for 1 < j < i + 1. Observe that this implies that y i = x. On the other hand, since z G ri(x), there are cici_ i • • • c i walks [x = y i, y2,..., yi+ i = z], such that yj G rj_ i(x) for 1 < j < i +1. The result follows.
(iii):	By Lemma 5.3(iii), the (z, y)-entry of LRi is equal to the number of walks [y = y0, y i,..., yi+i = z], such that yj G rj+i(x) for 0 < j < i. It follows that yj G Dj+i for 0 < j < i. Furthermore, observe that by Lemma 6.3, z has exactly ci+ i - ci - vi+i neighbours in D*+i if d(y, z) = i+1 (thatis, if z G D*+ i), exactly bi-Ki(z) neighbours in D*+ i if d(y,z) = i (that is, if z G D|), and exactly bi neighbours in D*+i if d(y, z) = i-1 (that is, if z G D*_i). Moreover, by Lemma 6.3(i), for any vertex yi G D*+ i, the number of walks [y = y0, y i,..., yi], such that yj G Dj+i for 0 < j < i, is equal to cici_ i • • • c i.
The result follows.
□
Lemma 7.2. With reference to Definition 6.6, pick y G r(x) and let Dj = Dj (x, y) (0 < i, j < D). Pick an integer i (1 < i < D), and let z G ri(x). Then the following (i), (ii) hold.
198
Ars Math. Contemp. 18 (2020) 187-210
(i) (Ri-1F)
zy
(ii) (FR4-1 )zy
Sj-=1 ci-ici-2 • • • Cj+iVj+ihjhj-i • • • h2 hihi-i • • • h-2 0
(fli-i - Vi)ci-iCi-2 • • • ci if z e Di-i, (ci - hi)ci-iCi-2 • • • ci if z e Di, 0	if z e Di+i.
if z e Di-i, if z e Di, if z e Di+i.
Proof. The proof is very similar to the proof of Lemma 7.1, so we omit the details. We only provide a sketch of the proof.
(i):	We would like to count the number of walks of length i —1 from z to D{. First, this number is 0 if z G Dj+1. If z G Dj, then this walk must pass through sets Dj-1, Dj_2, ..., D2. Observe the number of such walks is equal to hhi-1 • • • h2. Finally, suppose z G Dj_ 1. For any walk of length i — 1 from z to Dj, there must exist some integer 1 < j < i — 1 such that this walk passes through sets Dj-1, Dj_|,..., Dj+1, Dj, Dj'-i,..., D2, D1. By Lemma 6.3, the number of such walks (for a fixed j) is ci-1ci-2 • • • cj+1vj+1hjhj-1 • • • h2. The result follows.
(ii):	Here we note that z has 0 neighbours in Dj-1 if z G Dj+1, c — h neighbours in Dj-1 if z G Dj, and aj_1 — vj neighbours in Dj-1 if z G Dj-1. Moreover, there are ci-1ci-2 • • • c1 walks of length i — 1 from each vertex of Dj_1 to y.	□
8 Proof of the main result
In this section we will prove our main result. With reference to Definition 6.6, we will show that r is 1-thin with respect to x.
Lemma 8.1. With reference to Definition 6.6, fix an integer i (1 < i < D). Then there exist scalars A1, A2 such that
E*Ffii-iE1* = AiE;fii-iE1* + A2E*Ri-i F£j\
i1
i1
(8.1)
Proof. Let z, y G X. We shall show the (z, y)-entry of both sides of (8.1) agree. Note that we may assume z G ^(x), y G r(x); otherwise the (z, y)-entry of both sides of (8.1) is zero. Let Dj = Dj(x, y) (0 < j < D) and define scalars A1, A2 as follows:
(ci - hi) ^j=i ci-ici-2 • • • cj+iWj+ihjhj-i • • • h2
Ai = a^i - Vi -
hihi-i • • • h2
(ci - hj)cj-icj-2 • • • ci hi hi — i • • • h2
Treating separately the cases where z e D|-i, D|, D|+i, it's now routine using Lemma 7.1(i) and Lemma 7.2 to check that the (z, y)-entry of both sides of (8.1) agree. □
Lemma 8.2. With reference to Definition 6.6,
E*Ai-iE1 =
1
cic2 • • • i
Ei1fii-iE1 (1 < i < D).
(8.2)
A
2
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
199
Proof. Let z,y G X. Observe the (z, y)-entries of both sides of (8.2) are zero unless z G r(x), y G r(x). When z G r,(x), y G r(x), the (z, y)-entries of both sides of (8.2) are equal by (2.2) and Lemma 7.1(i). The result follows.	□
Lemma 8.3. With reference to Definition 6.6, assume v G E* V is an eigenvector for F. Then
v G span{Ri- 1 v} (1 < i < D).	(8.3)
Proof. We proceed by induction on i. For i = 1, the result is immediate since v is an eigenvector for F. Now assume the result is true for a fixed i, 1 < i < D - 1. By [2, p. 127],
0j+i Aj+i = AAj - OjAj - 6j_ i Aj_ i. Using this equation, Lemma 3.1, Definition 5.1, and Lemma 8.2, we find
ci+ 1E*+ 1 Ai+1 Eiv = E*+ 1 AAiEiv - a,E*+ iAjE*
v
= E*+ 1 (R + F + L)AE*v--a-E*+ 1 RjE*v
+	c 102 ••• Oj +
= RE^AjEiv + FE*+ 1 AjEiv -	™ ™ ^
(8.4)
iv - iR E i <
+	O 102 • • • Oj +
Observe EE*+ xA®Ei v = (c 1C2 ••• c®)- 1 E*+ xERiE1*v by (8.2), and E*+ xER®EJ v G span{R®v} by Lemma 8.1 and the fact that v is an eigenvector for E. Using this information along with (8.4) and the inductive hypothesis, we find E*+ 1Ai+ 1EJv G span{R®v}, as desired.	□
Lemma 8.4. With reference to Definition 6.6, let U denote the sum of all T-modules of endpoint 1. Assume v G E \U is an eigenvector for E. Then Lv = 0 and LR®v G span{Ri-1v} for 1 < i < D - 1.
Proof. Since v is contained in a sum of irreducible T-modules of endpoint 1, we find Lv = 0. By [ , Propositions 8.3(ii), 8.4], the primary module is the unique irreducible T-module upon which J does not vanish. Thus JE I v = 0, and for 1 < j < D - 1,
D
0 = E* JE* v = E* (^ At )E* v t=0
= E* A,-_ iE* v + E* Aj E1 v + E* Aj+iE* v.
V + Ej AjE V + Ej	V
Thus E* Aj+iE *v = -E* Aj_ lEJ v - E* AjE*v, and so by Lemma 8.2 and Lemma 8.3, E*Aj+1 E*v G span{Rj-1v} (1 < j < D - 1).	(8.5)
Now fix an integer i (1 < i < D - 1). By [2, p. 127],
AAj = Cj+1Ai+1 + ajAj + 6j_1Aj_1.
Thus
E* AAiE* v = ci+1E* AmEi v + ajE* AjE * v + 6j_1E* Aj_1Ei v. (8.6) In view of (8.6), and using (8.5), (8.3), (8.2), we find
E*AAjE*v G span{Ri-1v}.	(8.7)
200	Ars Math. Contemp. 18 (2020) 187-210
Now using Definition 5.1 and (8.2),
E*AAiE*1 v = E* (R + F + L)AiE*v
= RE*_ 1AiE *v + FE**AiE*v + LE**+1AiE*1v
= RE*_ 1AiE*v + FEi*AiE *v +-1-LRi
C 1C2 • • • Ci
Thus
LRiv = c1c2 • • • ci(Ei* AAiE*v - RE*_ 1 AiE*v - FE*AiE*v).
Recalling that v is an eigenvector for F, the result now follows from (8.7), (8.5), (8.3), (8.1). □
We now present our main result. With reference to Definition 6.6, let W denote an irreducible T-module of endpoint 1, and observe by Definition 5.1 that FE*W C E*W. Thus, there is a nonzero vector v e E*W such that v is an eigenvector for F. We shall show W is thin.
Theorem 8.5. With reference to Definition 6.6, let W denote an irreducible T-module with endpoint 1. Choose nonzero v e E *W which is an eigenvector for F. Then the following set spans W:
{v,Rv,R2v,...,RD- 1 v}.	(8.8)
In particular, W is thin.
Proof. We first show that W is spanned by the vectors in (8.8). Let W' denote the subspace of V spanned by the vectors in (8.8) and note that W' C W. We claim that W' is T-invariant. Observe that since RE*V C E*+1V for 0 < j < D - 1, W' is invariant under the action of E* for 0 < j < D, and so W' is M* -invariant. By definition and since RED V = 0, W' is invariant under R. From Lemma 8.1, Lemma 8.4, and the fact that v is an eigenvector for F, it follows that W' is also invariant under F and L. Since A = R + F + L and since A generates M, W' is M-invariant. The claim follows. Hence W' is a T -module, and it is nonzero since v e W '.By the irreducibility of W we have that W' = W. Since for 0 < j < D - 1 we have Rjv e E*+1W, it follows that W is thin. □
v.
9 Special case - two modules with endpoint 1
With reference to Definition 6.6, in this section we consider the case where r has (up to isomorphism) exactly two irreducible T-modules with endpoint 1. Note that these modules are thin by Theorem 8.5. Observe that in this case it follows from the comments of Section 4 that the local graph A = A(x) has either two or three distinct eigenvalues. In the former case A is a disjoint union of complete graphs (with order a1 +1), while in the latter case A is a strongly regular graph (see [8, Chapter 10, Lemma 1.5]). We observe that A has one of these two forms if and only if the map K1 is constant for every y e r(x), and this constant does not depend on y.
Proposition 9.1. With reference to Definition 6.6, assume that A is a disjoint union of k/(a1 + 1) cliques of order a1 + 1. Let W denote an irreducible T-module with endpoint 1. Then W is thin with local eigenvalue a1 or -1.
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
201
Proof. Recall that W is thin by Theorem 8.5. Let n denote the local eigenvalue of W, and note that n is an eigenvalue of A by the comments of Section 4. But the eigenvalues of A are a1 (with multiplicity k/(a1 + 1) > 1) and -1 (with multiplicity k - k/(a1 + 1) = ka1/(ai + 1)). The result follows.	□
Proposition 9.2. With reference to Definition 6.6, assume that A is a connected strongly regular graph with parameters (k, a1, A, v2). Let W denote an irreducible T-module with endpoint 1. Then W is thin with local eigenvalue n2 or n3, where
A - V2 ± v7(A - V2)2 + 4(ai - V2) n2,n3 = -2-•	(9.1)
Proof. Recall that W is thin by Theorem 8.5. Let n denote the local eigenvalue of W, and recall that n is an eigenvalue of A. Therefore, by the well-known formula for the eigenvalues of a connected strongly regular graph, the eigenvalues of r(x) are n1 = a1 (with multiplicity 1), and scalars n2, n3 from (9.1). The result follows.	□
Theorem 9.3. With reference to Definition 6.6, assume that for every y G r(x) the map K1 is constant, and that this constant does not depend on y. Then r has (up to isomorphism) exactly two irreducible T-modules with endpoint 1, both of which are thin. In particular, for every 1 < i < D - 1, the map Ki is constant, and this constant does not depend on y (in other words, r is pseudo-1-homogeneous with respect to x in the sense ofCurtin and Nomura [4]).
Proof. Recall that every irreducible T-module of r is thin by Theorem 8.5. Therefore, by Theorem 4.3, two irreducible T-modules with endpoint 1 are isomorphic if and only if they have the same local eigenvalue. As K1 is constant and this constant does not depend on y, the local graph A is either a disjoint union of cliques of order a1 +1, or connected strongly regular graph. The first part of the above theorem now follows from Propositions 9.1 and 9.2. The second part follows from [4, Theorem 1.6].	□
10 Special case - three modules with endpoint 1
With reference to Definition 6.6, in this section we consider the case where r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1. Note that these modules are thin by Theorem 8.5. It follows from the comments in Section 4 that this situation occurs if and only if the local graph A is either disconnected with exactly three distinct eigenvalues, or connected with exactly four distinct eigenvalues. Moreover, A is not connected if and only if v2 = 0. But if v2 = 0, then it is easy to see that A is a disjoint union of complete graphs (with order a1 + 1), and has therefore 2 distinct eigenvalues. This shows that v2 = 0, and so A is connected with exactly four distinct eigenvalues. To describe this case we need the following definition.
Definition 10.1. With reference to Definition 6.6, for y G r(x) let B = B(y) denote the adjacency matrix of the subgraph of r induced on D^ Observe that B G MatDi (C), and
„„ ............. „n1 .
so the rows and the columns of B are indexed by the elements of D 1. Let j G CDi denote the all-ones column vector with rows indexed by the elements of D .
Lemma 10.2. With reference to Definition 10.1, pick y G r(x). Then for every z G D 1 we have
K(z) = b1 - a 1 + (Bj)z + 1.
202
Ars Math. Contemp. 18 (2020) 187-210
Proof. Observe that (Bj )z is equal to the number of neighbours that z has in D{. Therefore, z has a 1 -1 - (Bj)z neighbours in D^. But as z also has K (z) neighbours in D^ and no neighbours in Df, it must have b 1 - K1 (z) neighbours in D|. The result follows. □
With reference to Definition 10.1, we now describe three properties that r could have.
Definition 10.3. With reference to Definition 10.1, we denote by P1, P2 and P3 the following properties of T:
P1: There exists y G r(x) such that K is not a constant.
P2: For every y, z G r(x) with d(y, z) G {0, 2}, the number of walks of length 3 from y to z in graph A is a constant number, which depends only on d(y, z) (and not on the choice of y, z).
P3: There exist scalars a, ft such that for every y G r(x) we have
B2j = aBj + j
With reference to Definition 10.3, in the rest of this section we prove that r has properties P1, P2, P3 if and only if r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1.
Proposition 10.4. With reference to Definition 10.3, assume that r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1. Then r has property P1.
Proof. Assume on the contrary that K2 is a constant for every y G r(x). We claim that this constant is independent of the choice of y G r(x). Pick y G r(x) and let Dj = Dj(x, y). Denote the constant value of K2 = K2(y) by « = «(y). Observe that every vertex in D2 has v2 neighbours in D {, and that every vertex in D { has b 2 - « neighbours in D2. As |D2| = b 2 and |D ^ = a2, this gives us a2(b 2 - «) = b 2 v2. This shows that « is independent of the choice of y G r(x). By Theorem 9.3, r has up to isomorphism at most two irreducible modules with endpoint 1, a contradiction. This shows that r has property P1.	□
Lemma 10.5. With reference to Definition 10.3, assume that r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1. Then
EF 3E2 = EÎ^LR + ^RL + F + ^F2 )EÎ	(10.1)
for some scalars (1 < i < 4).
Proof. By Lemma 3.2, there exist scalars A2, A2, A3, A4, A5, not all zero, such that
EÎ(A1LR + A2RL + A3F + A4F2 + A5F 3)EJj; =0.	(10.2)
We claim that A5 = 0. Assume on the contrary that A5 = 0. By Proposition 10.4, there exists y G r(x) such that K2 = K2(y) is not a constant. Pick such y and let Dj = Dj (x, y). Let z G D{. We now compute the (z, y)-entry of (10.2). By Lemma 7.1(ii),(iii),
the (z, y) entry of EÎLREÎ (EÎRLEÎ, respectively) is b2 - K2(z) (1, respectively). By Lemma 5.3(vi), the (z, y)-entry of EÎFEÎ is 1, and the (z, y)-entry of E2F2EÎ is equal
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
203
to the number of neighbours of z in D ^ But by Lemma 10.2, the number of neighbours of z in D 1 is equal to a 1 — 1 — b 1 + K1 (z). It follows from the above comments that
A 1 (b 1 — K (z)) + A2 + A3 + A4(a 1 — 1 — b 1 + K (z)) = 0.
Note that by the assumption the map K1 is not constant, and so the above equality implies A4 = A 1. Therefore A 1 (a 1 — 1) + A2 + A3 = 0.
We now compute the (y, y)-entry of (10.2). Similarly as above we get
A1(k — 1) + A2 =0.
Finally, pick z G D1. By computing the (y, z)-entry of (10.2) we get
A1(c2 — 1) + A2 =0.
It follows easily from the above equations that A1 = A2 = A3 = A4 = 0, a contradiction. This shows that A5 =0 and so
E1F3 Ei =	+ m2rl + m3f + m4f 2)EJ\
where Mi = — Ai/A5 for 1 < i < 4.	□
Theorem 10.6. With reference to Definition 10.3, assume that r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1. Then r has properties P2 and P3.
Proof. Note that for every y, z G r(x), the (z, y)-entry of EJF3EJ is equal to the number of walks of length 3 from y to z in graph A. Pick y, z G r(x) such that d(y, z) G {0,2}. We compute the (z, y)-entry of (10.1). Using Lemma 5.3(vi) and Lemma 7.1(ii),(iii) we find that
_ Jm 1b1 + M2 + M4a 1	ifz = y,
M 1 (c2 — v2 — 1) + M2 + M4v2 if z = y.
(E*F 3El)zy =
This shows that r has property P2.
Pick now y, z G r(x) such that d(y, z) = 1 and let Dj = Dj(x, y). Let K denote the corresponding map, and let B = B(y). Let [y = y0, y 1, y2, y3 = z] be a walk of length 3 from y to z in A. We will say that this walk is of type 0 if y2 = y, of type 1 if y2 G D ^ and of type 2 if y2 G D1. It is clear that we have a 1 walks of type 0 and (a 1 — 1 — (Bj)z)v2 walks of type 2. Similarly, there are (B2 j)z walks of type 1. So there are in total
a1 + (a1 — 1 — (Bj )z )v2 + (B2j )z
walks of length 3 from y to z in A.
We now compute the (z, y)-entry of the right side of (10.1). Using Lemma 7.1(iii) and Lemma 10.2, we find that the (z, y)-entry of E{LREl is equal to
b1 — K(z) = a 1 — (Bj)z — 1.
It is easy to see that the (z, y)-entries of EJRLEJ and E^FEJ are both equal to 1. Finally, the (z, y)-entry of E^F2E\ is equal to the number of neighbours of z in D ^ that is to (B j )z .It now follows from the above comments that
a 1 + (a 1 — 1 — (Bj)z )v2 + (B2j)z = M 1 (a 1 — (Bj )z — 1) + M2 + M3 + M4(Bj )z.
204
Ars Math. Contemp. 18 (2020) 187-210
This shows that
(B2j )z = a(Bj )z + £
for some scalars a, £, which are independent of the choice of vertices y, z. This proves that r has property P3.	□
We now assume that r has properties P1, P2 and P3. We will show that this implies that r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1.
Definition 10.7. With reference to Definition 10.3, assume that r has properties P1, P2 and P3, and recall that X = r(x). Recall also that for any y, z G X with d(y, z) G {0,2}, the number of walks of length 3 from y to z in A is a constant number, which depends just on the distance between y and z. We denote this number by w0 if y = z and by w2 if d(y, z) = 2. Recall that A = A(x) G Mat^ (C) denotes the adjacency matrix of A. Furthermore, let I denote the identity matrix of Mat % (C) and let J denote the all-ones matrix of Mat^ (C).
We now display the entries of A, At2 and At3.
Proposition 10.8. With reference to Definition 10.7, the following (i)-(iii) hold for all
z, y g X.
(i)
(A)
zy
1 if d(y,z) = 1, 0 otherwise.
(ii)
where B = B(y).
(iii)
(A2)zy
Wo
ai if y = z, (Bj )z if d (y, z) = 1, v2 if d (y, z) = 2,
if y = z
(A-3)zy H ai + V2(ai - 1) + (Bj)z(a - V2) + £ if d(y, z) = 1,
if d(y, z) = 2,
, W2
where B = B (y) and a, £ are from Definition 10.3.
Proof. Recall that for i > 0, the (z, y)-entry of A1 is equal to the number of walks of length i from y to z in A. Parts (i), (ii) follow. We now prove part (iii).
Note that the result is clear if y = z or if d(y, z) = 2. Therefore, assume d(y, z) = 1. Similarly as in the proof of Theorem 10.6, we split the walks of length 3 between y and z into three types, depending on whether the third vertex of the walk is equal to y, or is a neighbour of y, or is at distance 2 from y. There are a1 walks of the first type, (B2 j)z walks of the second type, and (a1 - 1 - (Bj)z)v2 walks of the third type. Recall that by property P3 we have B2 j = aBj + , and so the result follows.	□
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 
205
Proposition 10.9. With reference to Definition 10.7, we have
A3 = (a - V2)A2 + (a1 + P + V2(a1 - 1 + a - V2) - W2)A
+ (wo - W2 + (a - V2)(v2 - a1))1 + (W2 - (a - V2)V2) J,
where a, P are from Definition 10.3.
Proof. Pick y, z G X. It follows from Proposition 10.8 that the (z, y)-entry of the left side and the right side of (10.3) agree. This proves the proposition.	□
Theorem 10.10. With reference to Definition 10.7, A has exactly four distinct eigenvalues.
Proof. Observe that A is connected and regular with valency a1, so a1 is an eigenvalue of A with multiplicity 1. The corresponding eigenvector is the all-ones vector in CX, which we denote by j. Let 0 denote an eigenvalue of A which is different from a1, and let w denote a corresponding eigenvector. Note that w and j are orthogonal, and so applying (10.3) to w we get
03w = (a - v2)02w + (a1 + P + v2(a1 - 1 + a - v2) - w2)0w + (wo - W2 + (a - V2)(v2 - a1))w.
As w is nonzero, we have
03 = (a - V2)02 + (a1 + P + V2(a1 - 1 + a - V2) - W2)0 + wo - W2 + (a - V2)(v2 - a1).
This shows that A could have at most four different eigenvalues. Now if A has fewer than four different eigenvalues, then A is strongly regular [8, Chapter 10, Lemma 1.5], and so (Bj)z is constant for every y, z G X with z G r(y), where B = B(y) and j is from Definition 10.1. By Lemma 10.2, K1 is constant for every y G X, contradicting property P1.	□
Theorem 10.11. With reference to Definition 10.7, r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1.
Proof. Recall that r is 1-thin with respect to x by Theorem 8.5. The result now follows from Theorems 4.3, 4.4, and 10.10.	□
11 Example: Johnson graphs
Pick a positive integer n > 2 and let m denote an integer (0 < m < n). The vertices of the Johnson graph J (n, m) are the m-element subsets of {1,2,..., n}. Vertices x, y are adjacent if and only if the cardinality of x n y is equal to m - 1. It follows that if x, y are arbitrary vertices of J (n, m), then d (x, y) = m — |x n y|. Therefore, the diameter D of J (n, m) is equal to min{m, n — m}. Recall that J (n, m) is distance-transitive (see [2, Theorem 9.1.2]), and so it is also distance-regular. It is well known that J (n, m) is isomorphic to J (n, n — m), so we will assume that m < n/2, which implies D = m. In fact, if n is even and m = n/2, then J(2m, m) is 1-homogeneous (see [ ]), and so we assume from here on that m < n/2. As we are also assuming that D > 3, we therefore have m > 3, n > 7. For more details on Johnson graphs, see [2, Section 9.1].
206
Ars Math. Contemp. 18 (2020) 187-210
Pick adjacent vertices x, y of J(n, m), and let Dj = Dj (x, y) be as defined in Definition 6.1. For 1 < i < D let maps H, K and Vj be as defined in Definition 6.4. The main purposes of this section are to describe maps H, K and Vj in detail and to show J(n, m) satisfies the assumptions of Definitions 6.6 and 10.7. As J (n, m) is distance-transitive, it is also arc-transitive, and so we can assume that x = {1,2,..., m}, y = {2, 3,..., m + 1}. We start with a description of the sets Dj.
Proposition 11.1. Pick positive integers n and m with n > 7, 3 < m < n/2, and let x = {1, 2,..., m}, y = {2, 3,..., m +1} be adjacent vertices of J (n, m). Let Dj = Dj (x, y) be as defined in Definition 6.1. Then for 1 < i < D, the set Dj-1 (Dj_ respectively) consists of vertices of the form {1} U A U B ({m + 1} U A U B, respectively), where A Ç {2, 3,..., m} with |A| = m — i and B Ç {m + 2, m + 3,..., n} with |B| = i — 1.
Proof. Routine.
To describe sets Dii, we need the following definition.
□
Definition 11.2. Pick positive integers n and m with n > 7, 3 < m < n/2, and let x = {1,2,..., m}, y = {2,3,..., m + 1} be adjacent vertices of J(n, m).
(i)	For 1 < i < D — 1,define set D?(0) to be the set of vertices of the form {1,m + 1}U AuB, where A C {2,3,..., m} with | A| = m—i —1 and B C {m+2, m+3,..., n} with |B| = i — 1. We define D0(O) = D£(0) = 0.
(ii)	For 1 < i < D, define set D?(1) to be the set of vertices of the form A U B, where
A C {2, 3,..., m} with |A| = m — i, andB C {m + 2, m + 3,... ,n} with |B| = i. We define D0(1) = 0.
Please refer to Figure 2 for a diagram of this partition.
Figure 2: The partition with reference to Definition 11.2. For further information about which sets in the diagram are connected by edges, please refer to the propositions and corollaries later in this section.
Proposition 11.3. Pick positive integers n and m with n > 7, 3 < m < n/2, and let x = {1, 2,..., m}, y = {2, 3,..., m +1} be adjacent vertices of J(n, m). Let Dj = Dj(x,y) be as defined in Definition 6.1 and let D|(0), D|(1) be as in Definition 11.2. Then for 1 < i < D — 1 we have that D\ is a disjoint union of D\ (0) and D?(1). Moreover,
DD = DD (1).
Proof. Routine.	□
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 207
We now first describe the maps V.
Proposition 11.4. With the notation of Proposition 11.3, let the maps V be as defined in Definition 6.4. Then for 1 < i < D and any z e Dii_1 U Di—1 we have
Vi(z) = 2(i - 1).
In particular, the maps Vi are constant.
Proof. Note that the result is clear for i = 1, so pick 2 < i < D and assume z e D]—1 (case z e Di-1 is treated similarly and we omit the details). First recall that by the definition of map Vi and by Proposition 11.3 we have
Vi(z) = |r(z) n Di—11 = \r(z) n D^m + \r(z) n d—(1)1
Recall also that by Proposition 11.1 there exist subsets A Ç {2,3,... ,m} with |A| = m-i and B Ç {m + 2,m + 3,..., n} with |B| = i - 1, such that z = {1} U A U B .We first count the number of neighbours of z in D\—\(1). As vertices contained in Di—^) do not contain the number 1 as an element, vertex w e D*—1^) will be adjacent with z if and only if
w = A U B U {i}
for some i e {2,3,..., m} \ A. Therefore, there are exactly m — 1 — (m — i) = i — 1 neighbours of z in D]—^^. We now count the number of neighbours of z in D'—^O). As vertices contained in D\—\(0) contain numbers 1 and m +1 as elements, vertex w e D\—\(0) will be adjacent with z if and only if
w = ({1,m + 1}U A U B) \{i}
for some i e B. Therefore, there are exactly i - 1 neighbours of z in Di—1(0). The result follows.	□
Proposition 11.5. With the notation of Proposition 11.3, for 1 < i < D — 1 and for any z e Di(0) the following (i), (ii) hold.
(i)	|r(z) n d]—1(0)| = i(i — 1).
(ii)	|r(z) n d]—1 (1) | =0.
Proof. Note that the result is clear for i = 1, so pick 2 < i < D — 1 and z e D\(0). Recall that z = {1,m + 1} U A U B for some subsets A Ç {2, 3,..., m} with |A| = m — i — 1 and B Ç {m + 2, m + 3,... ,n} with |B| = i — 1.
(i):	Note that w e Di—1(0) is adjacent with z if and only if w = {1,m + 1} U A' U B', where A' = A U{i1} for some i1 e {2, 3,. ..,m}\A and B' = B\{i2} for some i2 e B. We have m — 1 — (m — i — 1) = i choices for i1 and i — 1 choices for i2. It follows that z has i(i — 1) neighbours in D\—\(0).
(ii):	Recall that if w is an element of D\—\(1), then 1 and m +1 are not elements of w. On the other hand, 1 and m +1 are elements of z, and so z and w are not adjacent. □
Proposition 11.6. With the notation of Proposition 11.3, for 1 < i < D and for any z e Di(1) the following (i), (ii) hold.
208
Ars Math. Contemp. 18 (2020) 187-210
(i)	|r(z) nDizi(i)| = i(i - 1).
(ii)	|r(z) n d— (0)| = 0.
Proof. Similar to the proof of Proposition 11.5.	□
Corollary 11.7. With the notation of Proposition 11.3, let the maps Hi be as defined in Definition 6.4. Then for 1 < i < D and any z G Di we have
Hi(z) = i(i - 1).
In particular, the maps Hi are constant.
Proof. Immediate from Propositions 11.5 and 11.6 and since Di is a disjoint union of Di(0) and Di(1).	□
Proposition 11.8. With the notation of Proposition 11.3, for 1 < i < D — 1 and for any z G D|(0) the following (i), (ii) hold.
(i)	|r(z) n D]+11(0)| = (m — i — 1)(n — m — i).
(ii)	|r(z) n Di+1(1)| = 0.
Proof. Pick 1 < i < D — 1 and z G D*(0). Recall that z = {1, m + 1} U A U B for some subsets A Ç {2, 3,..., m} with |A| = m — i — 1 and B Ç {m + 2, m + 3,..., n} with |B| = i — 1.
(i):	Note that w G Di+1 (0) is adjacent with z if and only if w = {1, m + 1} U A' U B', where A' = A \ {£1} for some £1 G A and B' = B U {t2} for some t2 G {m + 2, m + 3,... ,n}\B. We therefore have m—i —1 choices for i1 and (n—m—1) —(i —1) = n—m—i choices for l2. It follows that z has (m — i — 1)(n — m — i) neighbours in D]+1(0).
(ii):	Immediate from Proposition 11.6(ii).	□
Proposition 11.9. With the notation of Proposition 11.3, for 1 < i < D — 1 and for any z G D|(1) the following (i), (ii) hold.
(i)	|r(z) n Di+1(1)| = (m — i)(n — m — i — 1).
(ii)	|r(z) n DXi(0)| = 0.
Proof. Similar to the proof of Proposition 11.8.	□
Corollary 11.10. With the notation of Proposition 11.3, let the maps Ki be as defined in Definition 6.4. Then for 1 < i < D — 1 and any z G D| we have
K (z) i (m — i — 1)(n — m — i) if z G D| (0), i	[ (m — i)(n — m — i — 1) if z G D| (1).
In particular, maps Ki are not constant.
Proof. The first part of the corollary follows immediately from Propositions 11.8 and 11.9 and since D| is a disjoint union of D|(0) and D|(1). For the second part, observe that if Ki is a constant, then we have n = 2m, contradicting our assumption m < n/2.	□
Proposition 11.11. With the notation of Proposition 11.3, the following (i)-(iii) hold.
M. S. MacLean and S. Miklavic:: On a certain class of 1-thin distance-regular graphs 209
(i)	Every z G D{ has 1 neighbourin D{(0), 1 neighbour in D {(1), and n—4 neighbours in D2.
(ii)	Every z G D {(0) has n — m — 1 neighbours in D{, m — 2 neighbours in D {(0), and
no neighbours in D {(1).
(iii) Every z G D {(1) has m — 1 neighbours in D{, n — m — 2 neighbours in D {(1), and no neighbours in D {(0).
Consequently, the partition {{y}, D {(0), D {(1), D{ } of r(x) is equitable.
Proof. First observe that it follows from the proof of Proposition 11.4 that each z e D| has 1 neighbour in D ^0) and 1 neighbour in D ^1). Consequently, z has a 1 - 2 = n - 4 neighbours in D1. Next observe that each vertex from D ^0) contains 1 and m +1 as elements, while 1 and m +1 are not elements of any vertex from D 1(1). Consequently, there are no edges between vertices of D 1(0) and D 1(1). Furthermore, by Corollary 11.10, each vertex in D 1 (0) has (m — 2)(n — m — 1) neighbours in D2, while each vertex in D 1 (1) has (m — 1)(n — m — 2) neighbours in D^ The other claims of the above proposition now follow from the fact that intersection numbers a 1 and b 1 of J (n, m) are equal to n — 2 and (m — 1)(n — m — 1), respectively.	□
Theorem 11.12. Pick positive integers n and m with n > 7, 3 < m < n/2, and let r = J (n, m). Pick x e V (r) and lei T = T (x). Then r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1, and these modules are all thin.
Proof. As r is arc transitive, it follows from Proposition 11.4 and Corollary 11.7 that maps V and Hi (2 < i < D) are constant for every y e r(x), and that these constants are nonzero and independent of the choice of y. By Theorem 8.5, r is 1-thin. By Corollary 11.10, the map K1 is not constant for any y e r(x). Pick y, z e r(x) and let B = B(y) be as defined in Definition 10.1. It follows from Proposition 11.11 that the number of walks of length 3 from y to z in A = A(x) depends only on the distance between y and z when d(y, z) e {0, 2}. Finally, by Proposition 11.11 we also have that B2j = aBj + pj, where a = n — 4, p = —(n — m — 2)(m — 2), and j is from Definition 10.1. Therefore r has properties P1, P2 and P3, and so, by Theorem 10.11, r has (up to isomorphism) exactly three irreducible T-modules with endpoint 1.	□
ORCID iDs
Mark S. MacLean ©https://orcid.org/0000-0002-1727-1777 Stefko Miklavic © https://orcid.org/0000-0002-2878-0745
References
[1]	E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, The Ben-jamin/Cummings Publishing, Menlo Park, CA, 1984.
[2]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin, 1989, doi: 10.1007/978-3-642-74341-2.
[3] B. Curtin, Bipartite distance-regular graphs, Part I, Graphs Combin. 15 (1999), 143-158, doi: 10.1007/s003730050049.
210
Ars Math. Contemp. 18 (2020) 187-210
[4]	B. Curtin and K. Nomura, 1-homogeneous, pseudo-1-homogeneous, and 1-thin distance-regular graphs, J. Comb. Theory Ser. B 93 (2005), 279-302, doi:10.1016/j.jctb.2004.10.003.
[5]	E. S. Egge, A generalization of the Terwilliger algebra, J. Algebra 233 (2000), 213-252, doi: 10.1006/jabr.2000.8420.
[6]	J. T. Go, The Terwilliger algebra of the hypercube, European J. Combin. 23 (2002), 399-429, doi:10.1006/eujc.2000.0514.
[7]	J. T. Go and P. Terwilliger, Tight distance-regular graphs and the subconstituent algebra, European J. Combin. 23 (2002), 793-816, doi:10.1006/eujc.2002.0597.
[8]	C. D. Godsil, Algebraic Combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993.
[9]	A. Jurisic, J. Koolen and P. Terwilliger, Tight distance-regular graphs, J. Algebraic Combin. 12 (2000), 163-197, doi:10.1023/a:1026544111089.
[10]	S. Miklavic, Q-polynomial distance-regular graphs with ai = 0 and a2 = 0, European J. Combin. 30 (2009), 192-207, doi:10.1016/j.ejc.2008.02.001.
[11]	P. Terwilliger, The subconstituent algebra of an association scheme (Part I), J. Algebraic Combin. 1 (1992), 363-388, doi:10.1023/a:1022494701663.
[12]	P. Terwilliger, The subconstituent algebra of an association scheme (Part II), J. Algebraic Combin. 2 (1993), 73-103, doi:10.1023/a:1022480715311.
[13]	P. Terwilliger, The subconstituent algebra of an association scheme (Part III), J. Algebraic Combin. 2 (1993), 177-210, doi:10.1023/a:1022415825656.
[14]	P. Terwilliger, The subconstituent algebra of a distance-regular graph; thin modules with endpoint one, Linear Algebra Appl. 356 (2002), 157-187, doi:10.1016/s0024-3795(02)00376-2.