Distance-Regular Graphs Related to the Quantum Enveloping Algebra of sl ( 2 )

(1)

Distance-Regular Graphs Related to the Quantum Enveloping Algebra of sl ( 2 )

Department of Mathematics, University of California, Berkeley CA 94720, USA

College of Liberal Arts and Sciences, Tokyo Medical and Dental University, Kohnodai, Ichikawa, 272 Japan Received May 5, 1998; Revised April 21, 1999

Abstract. We investigate a connection between distance-regular graphs and Uq(sl(2)), the quantum universal enveloping algebra of the Lie algebra sl(2). Let0be a distance-regular graph with diameter d≥3 and valency k≥3, and assume0is not isomorphic to the d-cube. Fix a vertex x of0, and letT =T(x) denote the Terwilliger algebra of0with respect to x. Fix any complex number q6∈ {0,1,−1}. ThenTis generated by certain matrices satisfying the defining relations of Uq(sl(2))if and only if0is bipartite and 2-homogeneous.

Keywords: distance-regular graph, Terwilliger algebra, quantum group

1. Introduction

We investigate a connection between distance-regular graphs and U_q(sl(2)), the quantum universal enveloping algebra of the Lie algebra sl(2). It is well-known that there is a

“natural” sl(2)action on the d-cubes (see Proctor [9] or Go [4]). Here we describe the distance-regular graphs with a similar natural U_q(sl(2))action. We show that these graphs are precisely the bipartite distance-regular graphs which are 2-homogeneous in the sense of [7, 8], excluding the d-cubes. To state this precisely, we recall some definitions.

Let U(sl(2))denote the unital associative C-algebra generated by X⁻, X⁺, and Z subject to the relations

Z X⁻−X⁻Z =2X⁻, Z X⁺−X⁺Z = −2X⁺, X⁻X⁺−X⁺X⁻=Z. (1) U(sl(2))is called the universal enveloping algebra of sl(2). For any complex number q satisfying

q 6=1, q 6=0, q 6= −1, (2)

let U_q(sl(2))denote the unital associative C-algebra generated by X⁻, X⁺, Y , and Y⁻¹ subject to the relations

Y Y⁻¹ =Y⁻¹Y =1, (3)

Y X⁻ =q²X⁻Y, Y X⁺=q⁻²X⁺Y, X⁻X⁺−X⁺X⁻= Y−Y⁻¹

q−q⁻¹. (4)

(2)

Uq(sl(2))is called the quantum universal enveloping algebra of sl(2). For more on Uq(sl(2)) and its relation to U(sl(2))see [5, 6].

Let0=(X,R)denote a finite, undirected, connected graph without loops or multiple edges and having vertex set X , edge set R, distance function∂, and diameter d.0is said to be distance-regular whenever for all integers`, i , j(0≤`,i, j≤d)there exists a scalar p_{i j}^` such that for all x, y∈X with∂(x,y)=`,|{z∈ X|∂(x,z)=i, ∂(y,z)= j}| = p_{i j}^`. Assume that 0 is distance-regular. Set c₀ = 0, c_i = p_1iⁱ₋₁ (1 ≤ i ≤ d), a_i = p_1iⁱ (0 ≤ i ≤ d), b_i = p_1iⁱ₊₁ (0 ≤ i ≤ d −1), and b_d = 0. 0 is regular with valency k =b0 = p₁₁⁰ , and ci+ai+bi =k(0 ≤i ≤ d). 0is bipartite precisely when ai =0 (0≤i ≤d).

Let0=(X,R)denote a bipartite distance-regular graph. 0is said to be 2-homogeneous whenever for all integers i(1 ≤ i ≤ d)there exists a scalar γi such that for all x, y, z∈ X with∂(x,y)=i ,∂(x,z)=i ,∂(y,z)=2,|{w∈ X|∂(x, w) =i−1, ∂(y, w) = 1, ∂(z, w) = 1}| = γi. 0may be 2-homogeneous despite the fact that some structure constantγi is not uniquely determined: This occurs when there are no x, y, z ∈ X with

∂(x,y) = i , ∂(x,z) = i , ∂(y,z) = 2. It is known that γd is not uniquely determined when0is 2-homogeneous [8]. The d-cube is the graph with vertex set X = {0,1}^d (the d-tuples with entries in{0,1}) such that two vertices are adjacent if and only if they differ in precisely one coordinate. The d-cube is a 2-homogeneous bipartite distance-regular graph withγi =1(1≤i ≤d −1). The 2-homogeneous bipartite distance-regular graphs have been studied in [3, 8, 11].

Let Mat_X(C) denote the C-algebra of matrices with rows and columns indexed by X . Let A∈MatX(C) denote the adjacency matrix of0. For the rest of this section fix x∈ X . For all i (0 ≤i ≤ d), define E_i^∗=E_i^∗(x)to be the diagonal matrix in MatX(C) such that for all y ∈ X , E_i^∗ has(y,y)-entry equal to 1 if∂(x,y)=i , and 0 otherwise. LetT =T(x) denote the subalgebra of MatX(C) generated by A, E₀^∗,E₁^∗, . . . ,E^∗_d.

Set L=Pd−1

i=0 E_i^∗AE_i^∗₊₁and R=Pd

i=1E_i^∗AE_i^∗₋₁. Proctor [9] showed that if0is iso- morphic to the d-cube, then the matrices X⁻ =L, X⁺ = R, and Z =Pd

i=0(d −2i)E_i^∗ satisfy the relations of (1) (see also Go [4]). We must slightly relax the form of these matrices to admit a Uq(sl(2))structure. Specifically, we consider matrices of the form:

X⁻=

d−1

X

i=0

x_i⁻E_i^∗AE_i^∗₊₁, X⁺= Xd

i=1

x_i⁺E_i^∗AE_i^∗₋₁, Y = Xd

i=0

y_iE^∗_i, (5)

where x_i⁻(0 ≤i ≤d −1), x_i⁺ (1 ≤ i ≤ d), and y_i (0 ≤ i ≤d)are arbitrary complex scalars. Y is invertible if and only if y_i 6=0(0≤i ≤d), in which case Y⁻¹=Pd

i=0y_i⁻¹E^∗_i. Theorem 1.1 Let0=(X,R)denote a distance-regular graph with diameter d ≥3 and valency k ≥ 3. Assume that0is not isomorphic to the d-cube. Fix x ∈ X,and write E_i^∗=E^∗_i(x) (0≤i ≤d)andT =T(x). Let X⁻,X⁺,and Y be any matrices of the form (5),and let q be any nonzero complex number. Then the following are equivalent.

(i) Y is invertible,X⁻,X⁺,Y,Y⁻¹generateT,and(2)–(4)hold.

(ii) 0is bipartite and 2-homogeneous, (q+q⁻¹)² =c²₂b⁻₂¹(k−2)(c2−1)⁻¹,and there

(3)

exists²∈ {1,−1}such that

yi =²q^d⁻²ⁱ (0≤i ≤d),

x_i⁻x_i⁺₊₁ =²q⁻²ⁱ⁺¹(q^d+q²ⁱ)(q^d+q²ⁱ⁺²)(q^d+q²)⁻² (0≤i≤d−1).

The condition (i) of Theorem 1.1 means that the Terwilliger algebraT is a homomorphic image of Uq(sl(2)). The factor of²appears in (ii) because the defining relations of Uq(sl(2)) are invariant under changing the signs of any two of X⁻, X⁺, and Y .

2. Background

Throughout this section, let0=(X,R)denote a distance-regular graph with diameter d.

Let Mat_X(C) denote the C-algebra of matrices with rows and columns indexed by X . For all i (0 ≤ i ≤ d), define A_i to be the matrix in Mat_X(C) such that for all y, z ∈ X the (y,z)-entry of Ai is 1 if∂(y,z)=i and 0 otherwise. Observe that A0 = I (the identity matrix), A := A1 is the adjacency matrix of0, and Pd

i=0Ai = J (the all 1’s matrix).

Observe that AiAj = AjAi =Pd

`=0p_ij^`A_`(0≤i, j ≤d). It follows that the linear span Mof A0, A1, . . . ,Ad is a commutative subalgebra of MatX(C). The algebraMis called the Bose-Mesner algebra of0. It is known thatMis generated by A. See [1, 2] for more on distance-regular graphs and their Bose-Mesner algebras.

For the rest of this section fix x ∈ X . For all i (0 ≤ i ≤ d), define E_i^∗ = E_i^∗(x) to be the diagonal matrix in MatX(C) such that for all y ∈ X , the (y,y)-entry of E_i^∗ is E_i^∗(y,y)= Ai(x,y). Observe that E_i^∗E^∗_j =δijE^∗_i (0≤ i, j ≤ d)andP_d

i=0E_i^∗ = I . It follows that the linear spanM^∗ =M^∗(x)of E₀^∗, E^∗₁,. . ., E_d^∗is a commutative subalgebra of MatX(C). The algebraM^∗is called the dual Bose-Mesner algebra of0with respect to x.

LetT =T(x)denote the subalgebra of Mat_X(C) generated byM∪M^∗. The algebraT is called the Terwilliger algebra of0with respect to x. See [10] for more on Terwilliger algebras.

Fix`, i , j (0≤`,i, j≤d). Observe that for all y, z∈ X , the(y,z)-entry of E_i^∗A_`E^∗_j is 0 or 1, and it is equal to 1 if and only if∂(x,y)=i ,∂(y,z)=`and∂(x,z)= j . Thus, considering the positions of the nonzero entries,

{E_i^∗A_`E^∗_j 6=0|0≤`,i,j ≤d}is linearly independent, (6) E_i^∗A_`E^∗_j 6=0 if and only if p^`_{i j}6=0. (7) Observe that p_{i j}^` =0 if one of`, i , j is greater than the sum of the other two, and p^`_ij6=0 if one of`, i , j is equal to the sum of the other two. It follows that E_i^∗AE^∗_j =E^∗_jAE_i^∗=0 whenever|i−j|>1. Hence A=P_d

i=0

P_d

j=0E_i^∗AE^∗_j =L+F+R, where L =

d−1

X

i=0

E_i^∗AE_i^∗₊₁, F = Xd

i=0

E^∗_iAE_i^∗, R= Xd

i=1

E_i^∗AE^∗_i₋₁.

Observe that E_i^∗AE_i^∗=0 if and only if a_i =0, so0is bipartite if and only if F=0.

We wish to emphasize the following combinatorial interpretation of L and R. For all i (0 ≤ i ≤ d)and for all y ∈ X , let0i(y) = {z ∈ X|∂(y,z) = i}. Identify each

(4)

vertex with its characteristic column vector, and note that MatX(C) acts on the vertices by left multiplication. For all i (0 ≤ i ≤ d)and all y ∈ 0i(x), L y =P

w∈01(y)∩0i−1(x)w, R y = P

w∈01(y)∩0i+1(x)w, and E^∗_jy =δijy(0 ≤ j ≤ d). Fix i (0 ≤ i ≤ d). For all y, z∈0i(x), set

β(y,z)= |01(y)∩01(z)∩0i+1(x)|, γ (y,z)= |01(y)∩01(z)∩0i−1(x)|. (8) Observe that for all y, z∈0i(x),

(LRE^∗_i)(y,z)=β(y,z), (RLE^∗_i)(y,z)=γ (y,z). (9) In particular,(LRE^∗_i)(y,y)=bi,(RLE^∗_i)(y,y)=ci, and when∂(y,z) >2,(LRE^∗_i)(y,z)= (RLE^∗_i)(y,z)=0.

3. Construction of U(sl(2)) and Uq(sl(2)) structures

In this section, we construct a U(sl(2))structure on the d-cubes and a Uq(sl(2))structure on the remaining 2-homogeneous bipartite distance-regular graphs. Throughout this section, let0=(X,R)denote a distance-regular graph with diameter d ≥ 3 and valency k ≥3.

Fix x∈ X , and write E_i^∗=E_i^∗(x) (0≤i ≤d),M^∗=M^∗(x),T =T(x). Lemma 3.1 Let z0, z1, . . . ,zd denote distinct complex scalars. Then Z = Pd

i=0ziE_i^∗ generatesM^∗.

Proof: Observe that Z^j = Pd

i=0z_i^jE_i^∗ (0 ≤ j ≤ d), where the j = 0 equation is interpreted as I = Pd

i=0E^∗_i. Viewing E₀^∗, E₁^∗, . . . ,E_d^∗ as unknowns, this is a system of linear equations with Vandermonde (hence invertible) coefficient matrix. Thus E_i^∗ ∈ span{Z^j|0≤ j ≤d}(0≤i ≤d), so Z generatesM^∗. 2 Lemma 3.2 [4, 9] Suppose0is isomorphic to the d-cube. Then X⁻=L,X⁺ =R and Z =P_d

i=0(d−2i)E^∗_i generateT and satisfy(1).

Proof: Observe that Z generatesM^∗ by Lemma 3.1. Observe that F = 0 since0is bipartite, so A=L+R. A generatesM, so L, R, and Z generateT.

The relations Z L −L Z = 2L and Z R− R Z = −2R are easily verified using the definitions of L, R, and Z and the fact that E_i^∗E^∗_j =δijE_i^∗ (0 ≤i, j ≤ d). It remains to verify LR−RL=Z . SincePd

i=0E_i^∗ =I , it is enough to show that for all i(0≤i ≤d)

LRE^∗_i −RLE^∗_i =(d−2i)E_i^∗. (10)

Fix i (0 ≤i ≤d), and pick y, z ∈0i(x). Let r , s, t denote the(y,z)-entries of LRE^∗_i, RLE^∗_i, and E_i^∗, respectively. From (8), (9) we find the following. Suppose∂(y,z) > 2.

Then r =s =t =0. Suppose∂(y,z) =2. Then r = c₂−γi = 1, s = γi =1, and t =0. The case∂(y,z)=1 does not occur since a_i =0. Finally suppose y =z. Then r=bi=d−i , s=ci =i , and t=1. In all cases r−s=(d−2i)t, so (10) holds. 2

(5)

Theorem 3.3 ([3, Theorem 35]) Suppose0is not isomorphic to the d-cube. Then0is bipartite and 2-homogeneous if and only if there exists a complex scalar q 6∈ {0,1,−1} such that

ci =ei[ i ], bi =ei[ d−i ] (0≤i ≤d), (11) where

ei =qⁱ⁻¹(q^d+q²)(q^d+q²ⁱ)⁻¹, [ i ]=(qⁱ−q⁻ⁱ)(q−q⁻¹)⁻¹ (12) for all integers i . Suppose the above equivalent conditions hold. Then

γi=e2eie⁻_i₊¹₁ (1≤i ≤d−1). (13)

Corollary 3.4 ([3, Corollary 36]) Suppose0is bipartite and 2-homogeneous,but not isomorphic to the d-cube. Then any complex scalar q6∈ {0,1,−1}satisfying(11)and(12) is real and

(q+q⁻¹)²=c₂²b⁻₂¹(b0−2)(c2−1)⁻¹. (14) The set of q satisfying (14) is of the form{λ, λ⁻¹,−λ,−λ⁻¹}for some real number λ >1. When d is even, all such q satisfy (11). When d is odd, only q ∈ {λ, λ⁻¹}satisfy (11) since q+q⁻¹=c2γr⁻¹>0, where r=(d−1)/2 (see [3, Corollary 36]).

Lemma 3.5 Suppose0is bipartite and 2-homogeneous but not isomorphic to the d-cube.

Let q 6∈ {0,1,−1}be any complex scalar such that(11), (12)hold,and let ei(0≤i ≤d) be as in(12). Then the matrices

X⁻=

d−1

X

j=0

e⁻_j¹E^∗_jAE^∗_j₊₁, X⁺= Xd

j=1

e⁻_j¹E^∗_jAE^∗_j₋₁, Y = Xd

j=0

q^d⁻^{2 j}E^∗_j

generateT and satisfy(4).

Proof: Observe that Y generatesM^∗ by Lemma 3.1. Now L = (P_d₋₁

i=0 eiE_i^∗)X⁻ and R =(Pd

i=1e_iE_i^∗)X⁺are in the algebra generated by Y , X⁻and X⁺. Observe that F =0 since0is bipartite, so A=L+R. A generatesM, so X⁻, X⁺, and Y generateT.

The relations Y X⁻=q²X⁻Y and Y X⁺=q⁻²X⁺Y are easily verified using the defini- tions of X⁻, X⁺, and Y and the fact that E_i^∗E^∗_j =δijE_i^∗(0≤i, j ≤d). It remains to verify X⁻X⁺−X⁺X⁻=(Y−Y⁻¹)/(q−q⁻¹). Observe that for all i(0≤i ≤d), X⁻X⁺E_i^∗ = e⁻_i¹e⁻_i₊¹₁LRE^∗_i, X⁺X⁻E_i^∗ =e⁻_i₋¹₁e_i⁻¹RLE^∗_i, and(Y −Y⁻¹)/(q −q⁻¹)E_i^∗ = [ d−2i ]E^∗_i. Thus, since I =Pd

i=0E_i^∗, it is enough to show that for all i(0≤i ≤d)

e⁻_i¹e⁻_i₊¹₁LRE^∗_i −e⁻_i₋¹₁e_i⁻¹RLE^∗_i = [ d−2i ]E_i^∗. (15)

(6)

Fix i(0≤i≤d), and pick y, z∈0i(x). Let r , s, and t denote the(y,z)-entries of LRE^∗_i, RLE^∗_i, and E_i^∗, respectively. From (8), (9) we find the following. Suppose∂(y,z) > 2.

Then r = s =t = 0. Suppose∂(y,z) =2. Then by the definition of 2-homogeneous, r =c₂−γi, s =γi, and t =0. It can be verified by a direct computation using (11)–(13) that e⁻_i ¹e_i⁻₊¹₁(c₂−γi)−e_i⁻₋¹₁e⁻_i ¹γi =0. The case∂(y,z)=1 does not occur since a_i =0.

Finally suppose y = z. Then r = b_i, s = c_i, and t =1. It can be verified by a direct (albeit long) computation using (11), (12) that e⁻_i¹e⁻_i₊¹₁b_i −e_i⁻₋¹₁e⁻_i ¹c_i = [ d−2i ]. In all cases e⁻_i ¹e_i⁻₊¹₁r−e⁻_i₋¹₁e⁻_i¹s= [ d−2i ]t , so (15) holds. 2 The U(sl(2))structure on the d-cube is very similar to the Uq(sl(2))structure on the remaining 2-homogeneous bipartite distance-regular graphs. In the sequel, we exploit this similarity to prove the following result and Theorem 1.1 simultaneously.

Theorem 3.6 Let0=(X,R)denote a distance-regular graph with diameter d ≥3 and valency k ≥3. Fix x ∈ X,and write E_i^∗ =E^∗_i(x) (0≤i ≤d),T =T(x). Let X⁻,X⁺, and Z be of the form X⁻=Pd−1

i=0 x_i⁻E_i^∗AE^∗_i₊₁,X⁺=Pd

i=1x_i⁺E_i^∗AE^∗_i₋₁,Z =Pd i=0ziE_i^∗ for some complex scalars x_i⁻(0≤i ≤d−1),x_i⁺(1≤i ≤d),zi (0≤i ≤d). Then the following are equivalent.

(i) X⁻,X⁺,and Z generateT and satisfy(1). (ii) 0is isomorphic to the d-cube,and

x_i⁻x_i⁺₊₁ =1 (0≤i ≤d−1), zi =d−2i (0≤i ≤d).

As in Theorem 1.1, The condition (i) of Theorem 3.6 means that the Terwilliger algebraT is a homomorphic image of U(sl(2)).

4. Combinatorial structure

We show that the U(sl(2))and Uq(sl(2))structures of Lemmas 3.2 and 3.5 can only occur on a 2-homogeneous bipartite distance-regular graph. Specifically, we show the following.

Theorem 4.1 Let0=(X,R)denote a distance-regular graph with diameter d ≥3 and valency k ≥ 3. Fix x ∈ X,and write E_i^∗ = E_i^∗(x) (0 ≤ i ≤ d),T = T(x). Suppose thatT is generated by{X⁻,X⁺} ∪M^∗ and that X⁻X⁺−X⁺X⁻ = Z,where X⁻ and X⁺are of the form(5)and Z is of the form Z =Pd

i=0z_iE^∗_i for some complex scalars z_i (0≤i ≤d). Then0is bipartite and 2-homogeneous.

The hypotheses of this result are met by both Theorems 1.1(i) and 3.6(i). Throughout this section, we adopt the notation and assumptions of Theorem 4.1 as we prove this result in a series of lemmas. The first step in our proof of Theorem 4.1 is to show that ai =0 (1≤i ≤d−1). To do so, we consider certain matrices in the left idealTE^∗₁ofT:

Ki =E_i^∗JE^∗₁ (0≤i≤d),

N0=0, Ni =E_i^∗Ai−1E₁^∗ (1≤i ≤d).

(7)

Lemma 4.2 LK0=0,LKi =bi−1Ki−1(1≤i ≤d),RKi =ci+1Ki+1(0≤i ≤d−1), RKd =0,and X⁻K0 =0,X⁻Ki =x_i⁻₋₁bi−1Ki−1(1≤ i ≤ d), X⁺Ki =x_i⁺₊₁ci+1Ki+1

(0≤i ≤d−1),X⁺K_d =0.

Proof: Clearly LK₀ =LE^∗₀K₀ = 0. Fix i (1 ≤i ≤d). Fix y, z ∈ X , and let r and s denote the(y,z)-entries of LK_i and K_i₋₁, respectively. Observe that r = s = 0 unless y∈0i−1(x)and z∈01(x), so suppose y∈0i−1(x)and z ∈01(x). Then

r =(E_i^∗₋₁AE^∗_iJE^∗₁)(y,z)=X

p∈X

E_i^∗₋₁(y,y)A(y,p)E_i^∗(p,p)J(p,z)E₁^∗(z,z)

=X

p∈X

A(y,p)E_i^∗(p,p)= |01(y)∩0i(x)| =b_i₋₁, s =(E_i^∗₋₁JE^∗₁)(y,z)=E_i^∗₋₁(y,y)J(y,z)E₁^∗(z,z)=1.

In all cases r =b_i₋₁s, so LK_i =b_i₋₁K_i₋₁. The equations for RK_i are proved similarly.

The equations involving X⁻ and X⁺ follow since X⁻E_i^∗ = x_i⁻₋₁LE^∗_i (1 ≤ i ≤ d)and

X⁺E_i^∗=x_i⁺₊₁RE^∗_i (0≤i ≤d−1). 2

Lemma 4.3 x_i⁻ 6=0 and x_i⁺₊₁ 6=0(0 ≤ i ≤ d−1). In particular,si := x_i⁻x_i⁺₊₁ 6=0 (0≤i ≤d−1).

Proof: Suppose x_i⁻=0 for some i (0 ≤i ≤d−1), and set U =span{Kh |i+1≤h

≤d}. ThenUis closed under left multiplication by the generators X⁻, X⁺, andM^∗ofT by Lemma 4.2 and construction. HenceUis a left ideal ofT. However, LKi+1=biKi 6=0 and Ki 6∈U, a contradiction. Hence x_i⁻6=0(0≤i ≤d−1). A similar argument shows

that x_i⁺₊₁6=0(0≤i≤d−1). 2

Lemma 4.4 X⁺N_i =x⁺_i₊₁c_iN_i₊₁(1≤i ≤d−1)and X⁺N_d =0.

Proof: Fix i (1≤i ≤d−1). Pick y, z∈ X , and let r and s denote the(y,z)-entries of X⁺Ni and Ni+1, respectively. Observe that r =s=0 unless y ∈0i+1(x)and z∈01(x), so suppose y∈0i+1(x)and z∈01(x). Then

r =x_i⁺₊₁(E^∗_i₊₁AE_i^∗Ai−1E₁^∗)(y,z)

=x_i⁺₊₁X

p∈X

E^∗_i₊₁(y,y)A(y,p)E_i^∗(p,p)A_i₋₁(p,z)E^∗₁(z,z)

=x_i⁺₊₁|01(y)∩0i(x)∩0i−1(z)|, s =(E_i^∗₊₁A_iE₁^∗)(y,z)=A_i(y,z).

Observe that r =s=0 when∂(y,z)6=i , and r =x_i⁺₊₁ci, s =1 when∂(y,z)=i . In all cases r =x_i⁺₊₁cis, so X⁺Ni =x_i⁺₊₁ciNi+1. Clearly X⁺Nd =X⁺E_d^∗Nd =0. 2 Lemma 4.5 X⁻Ni ∈span{Ni−1, Ki−1}(1≤i ≤d).

(8)

Proof: It is easy to show that X⁻N1 = x⁻₀K0 by entry-wise computation. We proceed by induction: Fix i (2≤i ≤d), and assume X⁻Ni−1 =g Ni−2+h Ki−2for some scalars g, h. We compute

X⁻X⁺Ni−1= X⁻(x_i⁺ci−1Ni)=x_i⁺ci−1(X⁻Ni),

X⁺X⁻Ni−1= X⁺(g Ni−2+h Ki−2)=gx_i⁺₋₁ci−2Ni−1+hx_i⁺₋₁ci−1Ki−1, Z Ni−1=zi−1Ni−1.

Now we may apply the relation X⁻X⁺−X⁺X⁻= Z to Ni−1 and solve to find X⁻Ni ∈ span{Ni−1, Ki−1}since x_i⁺ci−16=0. The result follows by induction. 2 Lemma 4.6 a_i =0 (1≤i ≤d−1).

Proof: By Lemmas 4.2–4.5 and construction,U =span{Ki|0≤i ≤d} +span{Ni|1≤ i ≤ d}is a left ideal ofT. In fact, U = TE^∗₁ since E₁^∗ = N1. Now fix i (1 ≤ i ≤ d−1). Then E_i^∗TE₁^∗ = E_i^∗U = span{E_i^∗Ki, E_i^∗Ni}, so dimCE_i^∗TE₁^∗ ≤ 2. Observe that the subspace E_i^∗TE^∗₁ contains E_i^∗AjE₁^∗ (j = i−1,i,i+1), and E_i^∗Ai−1E^∗₁ 6=0, E_i^∗Ai+1E^∗₁ 6=0 by (7). If E_i^∗AiE₁^∗ 6=0, then these three matrices are linearly independent by (6), contradicting dimCE_i^∗TE₁^∗≤2. Thus E_i^∗AiE^∗₁ =0, so ai =0 by (7). 2

We show that a_d =0 by showing that there is a unique vertex at distance d from x.

Lemma 4.7 Set si = x_i⁻x_i⁺₊₁ (0 ≤ i ≤ d−1)and s₋1 = sd = 0. Then for all i (0≤i ≤d),

siLRE^∗_i −si−1RLE^∗_i =ziE_i^∗, (16)

siβ(y,z)−si−1γ (y,z)=δyzzi (y, z∈0i(x)), (17) whereβ(y,z)andγ (y,z)are as in(8). In particular, β(y,z)=0 if and only ifγ (y,z)=0 for any distinct y,z∈0i(x).

Proof: Fix i (0≤ i ≤ d). Apply the relation X⁻X⁺−X⁺X⁻ = Z to E_i^∗ to get (16).

Fix y, z∈0i(x). Computing the(y,z)-entry of (16) gives (17) by (9). It is clear from (17) and Lemma 4.3 thatβ(y,z)=0 if and only ifγ (y,z)=0 when y, z are distinct. 2 Lemma 4.8 |0d(x)| =1 and0is bipartite.

Proof: By a down-up walk of length 2` (1 ≤ ` ≤d), we mean a sequence of vertices v0,v1, . . . , v2`such thatvi andvi+1 are adjacent(0≤ i ≤ 2`−1),vi,v2`−i ∈0d−i(x) (0≤i ≤`), andv06=v2`. Assume|0d(x)| ≥2. For all distinct y, z∈0d(x)there exists a down-up walk of length 2d (takingv0 = y,vd =x,v2d =z), but there is no down-up walk of length 2 since|0d−1(x)∩01(y)∩01(z)| =0 by Lemma 4.7.

Fix a down-up walkv0,v1,. . .,v2`of minimal length 2`. By minimality of the length of this down-up walk,v_`−1andv_`+1∈0d−`+1(x)are distinct. Letγ (v_`−1, v_`+1),β(v_`−1, v_`+1)

(9)

be as in (8). Observe thatγ (v`−1, v`+1) > 0, soβ(v`−1, v`+1) > 0 by Lemma 4.7. Fix w∈0d−`+2(x)∩01(v`−1)∩01(v`+1). Fix a pathwd−`+2=w,wd−`+3,. . .,wdsuch that wi ∈ 0i(x)(such a path exists since b_i >0(0 ≤i ≤ d−1)). Supposewd 6=v0. Then v0, . . ., v_`−1, wd−`+2, . . ., wd is a down-up path of length 2`−2, contradicting the minimality of length 2`. Thuswd =v0. Similarly,v2` =wd, contradictingv0 6=v2`. It follows that|0d(x)| =1, so a_d =0. Hence0is bipartite in light of Lemma 4.6. 2 Lemma 4.9 0is 2-homogeneous.

Proof: By [3, Theorem 16] it is enough to show that for all i(1≤i ≤d)and for all y, z∈0i(x)with∂(y,z)=2, the numberγ (y,z)of (8) is independent of the choice of y, z.

Fix i (1 ≤ i ≤ d−1), and pick any y, z ∈ 0i(x)with∂(y,z)=2. By Lemma 4.8, 0 is bipartite, soβ(y,z)+γ (y,z) = c2. By (17), siβ(y,z)−si−1γ (y,z) = 0. Thus (si+si−1)γ (y,z)=c2si. Since si 6=0 by Lemma 4.3, the right side is nonzero and hence the left side is also nonzero. Thus we may solve this equation forγ (y,z)independent of y and z. Observe that when i =d there is nothing to show by Lemma 4.8. 2 5. Proof of Theorem 1.1

In this section we prove Theorems 1.1 and 3.6. We continue with the notation and assumptions of Theorem 4.1 throughout this section. We begin by considering the uniqueness of the U(sl(2))and U_q(sl(2))structures.

Lemma 5.1 Set si =x_i⁻x_i⁺₊₁(0≤i ≤d−1). Then the scalars si (0≤i ≤d−1)and z_i(0≤i ≤d)are uniquely determined up to the same scalar multiple.

Proof: Observe that for all i (0 ≤ i ≤ d)and for all y ∈ 0i(x),β(y,y) = bi and γ (y,y)=ci, whereβ(y,y)andγ (y,y)are as in (8). Thus applying (17) with y=z gives s0=z0b⁻₀¹, sibi−si−1ci=zi (1≤i ≤d−1), sd−1cd= −zd. (18) Applying the relation X⁻X⁺−X⁺X⁻ = Z to K_i (1≤i ≤d−1)and simplifying with Lemma 4.2 gives

s_ib_ic_i₊₁−s_i₋₁b_i₋₁c_i =z_i (1≤i ≤d−1). (19) Fix i (1≤i ≤d−1). Subtracting (18) from (19) gives sibi(ci+1−1)=si−1ci(bi−1−1). Since si, si−1are nonzero by Lemma 4.3, bi−1=1 if and only if ci+1=1. Suppose bi−1 = ci+1=1. Then 1≤bi≤bi−1=1 and 1≤ci≤ci+1 =1 since the ciform a nondecreasing sequence and the biform a nonincreasing sequence by [2, Proposition 4.1.6]. Thus k=ci+ b_i =2, a contradiction. Thus we may solve for s_ias s_i =c_i(b_i₋₁−1)s_i₋₁/(b_i(c_i₊₁−1)). In particular, since s₀ = z₀b⁻₀¹, the numbers s_j (0 ≤ j ≤ d−1) are determined by the intersection numbers and z₀. The numbers z_j (1 ≤ j ≤ d) are determined by (18). In these formulas z₀ is a factor of s_j (0 ≤ j ≤ d−1) and z_j (1 ≤ j ≤ d), so the result

follows. 2