°c 1998 Kluwer Academic Publishers. Manufactured in The Netherlands.
On Symmetric Association Schemes with k 1 = 3
NORIO YAMAZAKI∗ norio@math.kyushu-u.ac.jp
Graduate School of Mathematics, Kyushu University, Fukuoka 812, Japan Received January 2, 1996; Revised March 31, 1997
Abstract. In this paper, we have a classification of primitive symmetric association schemes with k1=3.
Keywords: distance-regular graph, P-polynomial association scheme, circuit chasing technique
1. Introduction
Let X be a finite set and Ri(i =0,1, . . . ,d)be subsets of X×X with the properties that (i) R0= {(x,x)|x∈ X};
(ii) X×X =R0∪ · · · ∪Rd, Ri∩Rj = ∅if i6= j ;
(iii) tRi =Ri0 for some i0∈ {0,1, . . . ,d}, wheretRi = {(x,y)|(y,x)∈ Ri};
(iv) for i,j,k∈ {0,1, . . . ,d}, the number of z∈ X such that(x,z)∈Riand(z,y)∈ Rj
is constant whenever(x,y)∈ Rk. This constant is denoted by pik,j.
Such a configurationX =(X,{Ri}0≤i≤d)is called an association scheme of class d on X . Association schemes with the additional properties
(v) pik,j =pkj,ifor all i,j,k, and
(vi) for every i , i0=i , i.e., Riis a symmetric relation
are called commutative and symmetric, respectively. Remark that ifX is symmetric, then X is also commutative, and that a symmetric association scheme can be constructed from any commutative but non-symmetric association scheme by the symmetrization [1, p. 57].
The positive integer ki =p0i,i0is called the valency of Ri. It is clear that, for every i , the graph whose vertex set is X and edge set is Ri, is a ki-regular graph, and, moreover, if i =i0, then it is undirected. We call it the Ri-graph. Note that, if Y is a connected component of the Ri-graph for some i , thenY=(Y,{Ri∩(Y ×Y)}i∈3)is also an association scheme of class|3| −1, where3= {i|(x,y)∈ Ri, x,y∈Y}.If for any i with 1≤i ≤d, Ri-graph is connected, we say thatXis primitive.
Let0be a connected undirected finite simple graph. Forα, β∈V(0), let∂(α, β)be the distance betweenαandβ. Let d(0) be the maximal distance in0, called the diameter
∗Supported in part by a grant of Japan Society for Promotion of Sciences.
of 0. Let 0i(α) = {β ∈ V(0) | ∂(α, β) = i}, and let 0(α) = 01(α). For vertices α, β with∂(α, β) = i , let Ci(α, β) = 0i−1(α)∩0(β), Ai(α, β) = 0i(α)∩0(β)and Bi(α, β) = 0i+1(α) ∩0(β). Let ci(α, β) = |Ci(α, β)|, ai(α, β) = |Ai(α, β)| and bi(α, β) = |Bi(α, β)|. If ci(α, β), ai(α, β)and bi(α, β)depend only on i = ∂(α, β), we say ci, ai and bi exist, respectively. 0is said to be distance-regular if ci, ai and bi exist for all i with 0≤i ≤d(0). It is clear that a distance-regular graph is b0-regular. It is well known that, if0is distance-regular, thenX =(V(0),{Ri}0≤i≤d(0))is a symmet- ric association scheme (called P-polynomial with respect to R1), where Ri = {(x,y) ∈ V(0)×V(0)|∂(x,y)=i}(0≤i ≤d(0)).
In the study of association schemes, the following problems seem very important.
(1) Determine the graphs which can be the Ri-graphs of an association scheme.
(2) By giving a regular graph0, determine the association schemes such that0is the Ri-graph for some i .
In this paper, we study on the above problems, particularly (1), in the case when the case Xis symmetric and0is a connected cubic (3-regular) graph. We remark that, if R1-graph is a connected 2-regular graph, i.e., a polygon, then we easily see thatX is P-polynomial with respect to R1.
We shall show the following.
Theorem 1.1 IfX=(X,{Ri}0≤i≤d)is a symmetric association scheme such that the R1- graph0is a connected non-bipartite cubic graph,thenX is P-polynomial with respect to R1.
This immediately implies the following.
Corollary 1.2 IfX =(X,{Ri}0≤i≤d)is a primitive symmetric association scheme with k1=3,thenX is P-polynomial with respect to R1.
Remark that cubic distance-regular graphs have already been classified by several authors (see [5, 3, 2]). So, by the previous corollary, we have a classification of primitive symmetric association schemes with k1=3.
2. R1-graph
LetX =(X,{Ri}0≤i≤d)be a symmetric association scheme of class d. For verticesα, β ∈ X , let∂(α, β)ˆ be the index such that(α, β)∈ R∂(α,β)ˆ . Let Ri(α)= {β ∈X | ˆ∂(α, β)=i}. Pick any t with 0 ≤ t ≤ d and let0 = (X,Rt)be the Rt-graph. For a pair of vertices (x,y)in Ri, Pij,l(x,y)= {z∈ X|(x,z)∈ Rj, (z,y)∈ Rl}, and let C(x,y)= ˆCi(x,y)= C∂(x,y)(x,y), A(x,y) = ˆAi(x,y) = A∂(x,y)(x,y), B(x,y) = ˆBi(x,y) = B∂(x,y)(x,y). Let c(x,y)= ˆci(x,y) =c∂(x,y)(x,y), a(x,y) = ˆai(x,y)=a∂(x,y)(x,y)and b(x,y)= ˆbi(x,y)=b∂(x,y)(x,y).
Lemma 2.1 Let(X,{Ri}0≤i≤d)be a symmetric association scheme of class d. Pick any t with 1≤t≤d,and let0be the Rt-graph.
For0,the following hold.
(1) For any pair of verticesα, β∈ X, ∂(α, β)depends only on∂(α, β)ˆ . In particular,if0is connected,there exists a surjection
ϕ:{0,1, . . . ,d} → {0,1, . . . ,d(0)}
such that,for all i with 0≤i ≤d and for all x,y∈ X with∂(ˆ x,y)=i, ∂(x,y)= ϕ(i).
(2) For any pair of verticesα, β∈ X , c(α, β), a(α, β)and b(α, β)depend only on∂(α, β)ˆ . In particular,c(α, β)=c(β, α), a(α, β)=a(β, α)and b(α, β)=b(β, α).
(3) Let α, β and γ be vertices in X with γ ∈ B(α, β). Then c(α, β) ≤ c(α, γ ) and b(α, β)≥b(α, γ ).
Proof: Straightforward. 2
Remark From (1) and (2) in the previous lemma, we see that, if d =d(0), i.e., ifϕis bijective, then0is distance-regular. The converse does not necessarily hold.
We writecˆi,aˆiandbˆi for the parameters as in Lemma 2.1 (2).
From now on, letX =(X,{Ri}0≤i≤d)be a symmetric association scheme of class d such that R1-graph0is a connected cubic graph.
Lemma 2.2
(1) Let at exists and at =0. Then there exist no vertices x,y,z∈ X such that∂(z,x)=
∂(z,y)=t+1,∂(x,y)=1 and that c(z,x)=c(z,y)=2.
(2) Let j1,j2be integers such thatϕ(j1)=ϕ(j2)−1, p1j2,j
1=2,and that p1j1,j
1 =0. Then p1j2,j
2=0.
Proof:
(1) Suppose not. Note that, by Lemma 2.1(2), c(x,z)=c(y,z)=2. As k1=3, there must exist a vertex u∈ Ct+1(x,z)∩Ct+1(y,z). However, this implies that y ∈ At(u,x), which contradicts that at =0.
(2) Similar to (1). 2
Lemma 2.3
(1) Let at−2,atexists and at−2=at=0 for some t ≥2. Then there exist no vertices x,y and z such that∂(x,y)=1, ∂(z,x)=∂(z,y)=t−1 and ct−1(z,x)=ct−1(z,y)= bt−1(z,x)=bt−1(z,y)=1.
(2) Let j1,j2,j3be integers such thatϕ(j1)=ϕ(j2)−1=ϕ(j3)−2 and p1j2,j
1 =p1j2,j
2=
p1j2,j
3=1. Then p1j1,j
16=0 or p1j3,j
36=0.
Proof:
(1) By Lemma 2.1 (2), ct−1(x,z) = ct−1(y,z) = 1. Let{u} = Ct−1(x,z)and{v} = Ct−1(y,z). We see that u6=v. Otherwise, we have y∈ At−2(u,x), which contradicts that at−2=0. Since k1 =3 and bt−1(x,z)=bt−1(x,u)=1, there exists a vertexw in B(x,z)∩B(x,u). However, this implies that y ∈ As(w,x), which contradicts that at =0. Now we have the assertion.
(2) Similar to (1). 2
For the convenience, we number some indices of relations. If #{i | p11,i 6=0,i6∈ {0,1}} = 1, let p11,2 6=0. If #{i | p12,i 6=0, i 6∈ {1,2}} = 1, let p21,3 6=0. We repeat this, and let s be the maximal number such that, for i ≤ s, #{j | p1i−,j1 6=0, j 6∈ {i−2,i−1}} =1.
Note that, for every vertexαin X and for any i with 0≤i ≤s,0i(α)= Ri(α), and that ci,ai,biexist(0≤i ≤s).
In this paper, the distribution diagram with respect to R1acts an important role. For the definition of it, see [4, Section 2.9].
It is well known that, if the distribution diagram with respect to R1is linear, i.e., s =d, then0is distance-regular with diameter d. See [4, Proposition 2.9.1 (ii)].
Lemma 2.4 If s6=d,then s≥2.
Proof: Suppose s =1. Let x,y be vertices in X with∂(ˆ x,y)=1, z∈ P11,2(x,y), and u ∈ P11,3(x,y). Note that p11,2 = p11,3 =1.As P11,3(x,z)6= ∅,∂(ˆ z,u)=3. However, this implies that y,z∈ P11,3(x,u), which contradicts that p11,3=1. Now we have the assertion.
2
Lemma 2.5 Let s6=d. Then(ci,ai,bi)=(1,0,2) for 0≤i ≤s.
Proof: If s 6=d, then we easily haveˆbs =bs =2. Hencecˆs =cs =1. Therefore we
have the assertion by Lemma 2.1 (3). 2
The following lemma is clear.
Lemma 2.6 0is bipartite if and only if ai exists and ai =0 for any i with 0≤i ≤d(0). Letαandβ be vertices in X with∂(α, β)ˆ =i . Let0(α) = {x1,x2,x3}and0(β)= {y1,y2,y3}. Let Mi(α, β)be the 4×4-matrix whose rows and columns are indexed by (0(α)∪ {α})and(0(β)∪ {β}), respectively, such that
(Mi(α, β))u,v= ˆ∂(u, v)−s,
where u∈0(α)∪ {α}andv∈0(β)∪ {β}. We identify this up to the ordering of indices.
If Mi(α, β)does not depend on the choice of(α, β)∈ Ri, we write Mi =Mi(α, β), and say Miexists.
Suppose s6=d, and let ps1,s+1= ps1,s+2=1. Letα, β be vertices in X with∂(α, β)ˆ = s. Let0(α) = {x1,x2,x3}and0(β) = {y1,y2,y3}. As cs = 1, we may assume that
∂(α,ˆ y3)= ˆ∂(β,x3)=s−1 and that∂(ˆ x3,y3)=s−2.
Thus Ms(α, β)can be written as follows:
y1 β y2 y3
x1 i1 1 i2 0
α 1 0 2 −1
x2 i4 2 i3 0
x3 0 −1 0 −2
We may assume that 0≤i1,i2,i3≤5.
We have the following lemma.
Lemma 2.7 Let s6=d. For Ms(α, β)as above,the following hold.
(1) ps1+,s1+i
1,p1s+,s1+i
2,p1s+,s1+i
4, ps1+,s2+i
2,ps1+,s2+i
3,p1s+,s2+i
4are all nonzero. In particular,i2=i4. (2) #{j ∈ {1,2} |ij =0} = ˆcs+1−1 and #{j ∈ {2,3} |ij=0} = ˆcs+2−1.
(3) If i2=1,then i1=2. Similarly,if i2=2,then i3=1.
(4) If i1=2,then i2=1 or i3=1. Similarly,if i3=1,then i1=2 or i2=2.
Proof:
(1) The first claim is clear. The second immediately follows from 3=k1=Pd
j=0 p1s+,j1. (2) As y3 ∈Pss,+11(x1, β)∩Pss,+12(x2, β), it is clear.
(3) Let i2=1. Then we see thatα∈P1s,+s+12(x1,y2), so that p1s+,s1+26=0. Hence P1s,+s+12(β,x1) 6= ∅, so i1 =2. The latter assertion is proved similarly.
(4) Similar to the proof of (3). 2
By the same argument as in the previous lemma, we have the following lemma.
Lemma 2.8 Let j1,j2,j3be distinct integers such thatϕ(j1)≥1, ϕ(j1)=ϕ(j2)−1= ϕ(j3)−1,and that p1j1,j
2= p1j1,j
3 =1. Then the following hold.
(1) Ifcˆj2 = p1j2,j
1 =1,then there exists an integer j4(6=j1)such that both p1j2,j
4 and p1j3,j
4
are nonzero.
(2) Ifcˆj2 =p1j2,j
1,and if there exists no integer j4(6=j1)such that both p1j2,j
4and p1j3,j
4 are nonzero,then p1j2,j
1≥2.
Proof:
(1) Let j0be the integer such that p1j1,j
0 =1 and thatϕ(j0)=ϕ(j1)−1. Letα, βbe vertices in X with∂(α, β)ˆ = j1,0(α) = {x1,x2,x3}, and let0(β)= {y1,y2,y3}. Then we may assume that Mj1(α, β)is as follows:
y1 β y2 y3
x1 ∗ j2−s ∗ ∗
α j2−s j1−s j3−s j0−s
x2 ∗ j3−s ∗ ∗
x3 ∗ j0−s ∗ ∗
Ascˆj2=p1j2,j
1 =1, we have∂(ˆ x1,y3)= j1and∂(ˆ x1,y2)6= j1. Hence we may assume that∂(ˆ x1,y2)= j46= j1. It follows that y2∈ P1j,2j
4(β,x1)and x1∈ P1j,3j
4(α,y2), so that p1j2,j
46=0 and p1j3,j
4 6=0.
(2) It follows directly from (1). 2
By Lemma 2.7, we see that(i1,i2,i3)is one of the following:
(0,0,0), (0,0,2), (0,0,3), (0,2,1), (0,3,0), (0,3,2), (0,3,3), (0,3,4), (1,0,0), (1,0,2), (1,0,3), (1,2,1), (1,3,0), (1,3,2), (1,3,3), (1,3,4), (2,0,1), (2,1,0), (2,1,1), (2,1,2), (2,1,3), (2,2,1), (2,3,1), (3,0,0), (3,0,2), (3,0,3), (3,0,4), (3,2,1), (3,3,0), (3,3,2), (3,3,3), (3,3,4), (3,4,0), (3,4,2), (3,4,3), (3,4,4), (3,4,5), (4,3,4).
Note that, for example,(3,4,5), (3,5,4), (4,3,5)and(4,5,3)can be regarded as the same type.
Lemma 2.9 Let(i1,i2,i3)be one of the above. Then the following hold.
(1) Ms exists,except the case(i1,i2,i3)=(0,3,0), (3,0,3), (1,2,1), (2,1,2), (3,4,3) or(4,3,4). Moreover, (i1,i2,i3)=(0,3,0)or(3,0,3)if and only if(ps1+,s1,p1s+,s1+3, ps1+,s2,ps1+,s2+3)=(2,1,2,1),(i1,i2,i3)=(1,2,1)or(2,1,2)if and only if(p1s+,s1,p1s+,s1+1, ps1+,s1+2,ps1+,s2,ps1+,s2+1, ps1+,s2+2)=(1,1,1,1,1,1),and(i1,i2,i3)=(3,4,3)or(4,3,4) if and only if(p1s+,s1,ps1+,s1+3,p1s+,s1+4,ps1+,s2,ps1+,s2+3,pss,+s+24)=(1,1,1,1,1,1).
(2) If i16=i3,then(i1,i2,i3)and(i30,i20,i10)can be regarded as the same type,where for j =1,2,3,
i0j =
ij if ij 6∈ {1,2}, 2 if ij =1, 1 if ij =2. Proof:
(1) Straightforward. For example, (i1,i2,i3) = (0,3,4) if and only if (ps1+,s1,p1s+,s1+3, ps1+,s2,ps1+,s2+3,ps1+,s2+4)=(2,1,1,1,1).
(2) It is clear from the symmetry of indices of relations. 2
By (1) in the previous lemma, the type of(i1,i2,i3)can be regarded as ofX. Thus, if s6=d, the type ofXis one of the following.
(I) (i1,i2,i3)=(0,0,0), (1,2,1)or(2,1,2), (1,3,2), (2,3,1), (3,3,3), (0,3,0)or(3,0,3),
(IIA) (0,2,1), (0,3,3), (2,1,1),
(IIB) (0,0,2), (1,0,2), (1,0,3), (2,0,1), (IIC) (0,3,2), (3,3,2),
(IID) (0,0,3), (3,0,4), (0,3,4), (3,3,4), (3,4,3)or(4,3,4), (III) (1,3,4),
(IV) (2,1,3), (V) (3,4,5).
In the rest of this paper, we shall show that, if0is non-bipartite, thenX is not of any type in (I)–(V).
3. Circuit and profile
For fixed vertices u, v∈ X with(u, v)∈ R1, let Dij =Dij(u, v)=Pi1,j(u, v). For subsets A,B in X , let e(A,B)be the number of edges in0between A and B. For x ∈ X , write e(x,A)=e({x},A).
We easily have the following.
Lemma 3.1 Let s6=d and let(u, v)be any pair of adjacent vertices. Then the following hold.
(1) Dij 6= ∅if and only if p1i,j 6=0. In particular,Dii−16= ∅(1≤i ≤s+1),Dss+2 6= ∅, and Dii = ∅(1≤i ≤s).
(2) For 1≤i ≤s,e(Dii−1,Dii−1)=e(Dii−1,Dii−1)=e(Dii+1,Dii+1)=0.
(3) e(Dss+2,Dss+2)=0.
(4) For every x ∈Dii+1(1≤i ≤s),e(x,Dii−1)=1.
(5) For every x ∈Dss+2,e(x,Dss−1)=1.
(6) For every y∈Dii−1(1≤i ≤s−1),e(y,Dii+1)=2.
(7) For every y∈Dss−1,e(y,Dss+1)=e(y,Dss+2)=1.
Proof: Straightforward. 2
For x ∈Dss++ij, let Eij(x)=©
(i0,j0)¯¯e¡
x,Dss++ij00¢ 6=0ª
,
where Dmn = Dnm(u, v)for a given pair of adjacent vertices(u, v)in0. If Eij(x)depend only on i and j , we write Eij =Eij(x).
In this paper, a circuit in0is defined as a connected induced 2-regular subgraph.
Lemma 3.2 Let s 6=d and let{x0,x1, . . . ,xt−1,xt = x0}be a circuit of length t in0. Then,for any i,j with 0 ≤ i ≤ t−1 and with 1 ≤ j ≤ s,xi+j ∈ Djj−1(xi,xi+1)and xi−j+1∈ Djj−1(xi,xi+1),where indices are given by modulo t . In particular,t≥2s+2.
Proof: Immediate from Lemma 3.1. 2
Let C = {x0,x1, . . . ,xt}be a circuit of length t in0. Note that xu+s ∈ Dss−1(xu,xu+1) and xu+t−s+1∈Dss−1(xu,xu+1), where indices are given by modulo t. If xu+s+1∈Dss++lj1
1
(xu,xu+1), . . . ,xu+t−s ∈Dss++ljt−2s
t−2s(xu,xu+1), we call 0 j1 j2. . . jt−2s (−1)
(−1) l1 l2 . . .lt−2s 0
the profile of C with respect to(xu,xu+1). Note that l1= jt−2s =0. Let σC(xu)=(j1,j2, . . . ,jt−2s),
and, for e1, . . . ,en ∈ {1,2, . . . ,t−2s}, let σC(xu;e1, . . . ,en)=¡
je1, . . . ,jen
¢.
4. Type I, II
Lemma 4.1 Suppose thatXis of type I. Then0is distance-regular.
Proof: Suppose that(i1,i2,i3)=(0,0,0). Then we have that, for everyα∈X ,0s+1(α)= Rs+1(α)∪Rs+2(α), d=s+2 and that cs+1 =ps1+,s1= p1s+,s2=3. This implies that0is a bipartite distance-regular graph with d(0)=s+1 and with the intersection array
{3,2, . . . ,2;1, . . . ,1,3}.
Similarly, if(i1,i2,i3) =(1,2,1)or(2,1,2), then0is a distance-regular graph with d(0)=s+1 and with the intersection array
{3,2, . . . ,2;1, . . . ,1}.
Suppose that(i1,i2,i3)=(0,3,0)or(3,0,3). Then we see that0s+2(α)=Rs+3(α)for everyα∈ X , and that ci,ai,and bi exist for 0≤i ≤s+2. Note that(cs+1,as+1,bs+1)= (2,0,1)and that
ks+1=ks+2=ks+3· p1s+,s3+1=ks+3·p1s+,s3+2,
that is, cs+2=ps1+,s3+1+p1s+,s3+2=2. If d=s+3, then ps1+,s3+3 =1, and0is a non-bipartite distance-regular graph with d(0)=s+2 and with the intersection array
{3,2, . . . ,2,1;1, . . . ,1,2,2}.
Let d >s+3 and p1s+,si+i+1 6=0(3≤ i ≤ d−s−1). Then we have that0s+i(α)= Rs+i+1(α) (3 ≤i ≤ d −s−1)for everyα ∈ X , and that0is a distance-regular graph with d(0)=d−1. Moreover, by Lemma 2.2 (2),(pd1,d−1,p1d,d)=(3,0). Hence ai =0 for 0≤i ≤d(0)and0is bipartite. In the case(i1,i2,i3)=(3,3,3), the proof is similar.
Suppose that (i1,i2,i3) = (1,3,2). Then we see that0s+2(α) = Rs+3(α) for every α∈ X , and that ci,ai,bi exist for 0≤i ≤s+2. Note that(cs+1,as+1,bs+1)=(1,1,1) and cs+2 = ps1+,s3+1+ps1+,s3+2 = 2. Note that there exist x,y,z ∈ X such that∂(z,x)=
∂(z,y) =s+1 and∂(x,y) = 1. Since cs+1 = bs+1 = 1 and as = 0, it follows from Lemma 2.3 (1) that as+2 = ps1+,s3+3 =1, so that0is a non-bipartite distance-regular graph with d(0)=s+2=d−1 and with the intersection array
{3,2, . . . ,2,1;1, . . . ,1,2}.
The proof for the case(i1,i2,i3)=(2,3,1)is similar. 2 Lemma 4.2 Suppose thatXis of type I. Then0is bipartite.
Proof: By the list of cubic distance-regular graphs in [3], if (i1,i2,i3) = (1,2,1) or (2,1,2), then0has the intersection array
{3,2;1,1},
which contradicts Lemma 2.4. 2
If(i1,i2,i3)= (0,3,0), (3,0,3)or(3,3,3)and d =s+3 (see the proof of Lemma 4.1), then we cannot find the appropriate graphs in the list in [3].
Suppose that(i1,i2,i3)=(1,3,2). Then, by the list in [3],0has the intersection array {3,2,2,1;1,1,1,2},
so that s=2 and d=d(0)+1=5. We need two sublemmas as follows.
Sublemma 4.2.1 Suppose(i1,i2,i3)=(1,3,2). Then Ms+1and Ms+2exist as follows, respectively.
y1 β y2 y3
x1 0 1 3 1
α 1 1 3 0
x2 3 3 1 2
x3 1 0 2 −1
y1 β y2 y3
x1 0 2 3 2
α 2 2 3 0
x2 3 3 2 1
x3 2 0 1 −1
Proof: Let α, β ∈ X with ∂(α, β)ˆ = s+1, R1(α) = {x1,x2,x3}, and let R1(β) = {y1,y2,y3}. As cs+1 = ps1+,s1 = 1, we may assume that ∂(α,ˆ y3) = ˆ∂(β,x3) = s and
∂(ˆ x3,y3) = s −1. As p1s+,s1+1 = p1s+,s1+3 = 1, let ∂(α,ˆ y1) = ˆ∂(β,x1) = s+1 and
∂(α,ˆ y2)= ˆ∂(β,x2)=s+3. As ps1+,s2+1 =0, we have∂(ˆ x1,y3)= ˆ∂(x3,y1)=s+1 and
∂(ˆ x2,y3) = ˆ∂(x3,y2) =s+2. As ps1+,s3 = 0, we have∂(ˆ x1,y2)= ˆ∂(x2,y1) =s+3.
This immediately implies that∂(ˆ x1,y1)=s and∂(ˆ x2,y2)=s+1. Thus we see that Ms+1
exists as above.
Similarly, for Ms+2. 2
Sublemma 4.2.2 Suppose(i1,i2,i3)=(1,3,2). Then the following hold.
(1) E10= {(−1,0), (1,1), (2,3)}. (2) E20= {(−1,0), (1,3), (2,2)}. (3) E11= {(0,1), (1,0), (3,3)}. (4) E32= {(0,1), (2,3), (3,2)}. (5) E31= {(0,2), (1,3), (3,1)}. (6) E22= {(0,2), (2,0), (3,3)}. (7) E33= {(1,1), (2,2), (3,3)}. Proof:
(1) Let x∈ Dss+1. Then, for Ms, we may assume that u=α,v=x1and x=β. Then we see that y3∈ Dss−1, y1∈ Dss++11and y2∈Dss++32. Thus we have the assertion.
(2)–(6) Similar to (1).
(7) Let x∈Dss++33. As p1s+,s3+1=ps1+,s3+2 =ps1+,s3+3=1, we may assume that E33(x)= {(1,j1), (2,j2), (3,j3)} = {(j4,1), (j5,2), (j6,3)}.
From(1)to(6), it must hold that j1 = j4=1, j2= j5=2 and j3= j6=3, as desired.
2 Now we shall show that it is impossible that(i1,i2,i3)=(1,3,2). We use circuit chasing technique. Let C = {x0,x1, . . . ,x9,x10=x0}be a circuit of length 2s+6=10 in0such that the profile with respect to(x0,x1)is as follows:
0 1 1 3 3 1 0
0 1 3 3 1 1 0.
Note that the existence of this circuit is guaranteed by Lemma 3.1 and Sublemma 4.2.2,
∂(ˆ x0,x3)=s+1=3, and that x4∈ Dss+1(x1,x2)=D23(x1,x2). By Sublemma 4.2.2 (1), (4) and (3), we easily have that the profile of C with respect to(x1,x2)is
0 1 3 3 1 1 0
0 2 2 0 1 1 0.
Similarly, the profile of C with respect to(x2,x3)is
0 2 2 0 1 1 0
0 2 2 3 3 2 0.
This implies that∂(ˆ x3,x0)= s+2 =4, which is a contradiction. Thus we have the assertion.
Finally, we shall show that the case(i1,i2,i3)=(2,3,1)is impossible. In this case,0 has the same intersection array as the one in the case(i1,i2,i3)=(1,3,2). For the proof, we need the following.
Sublemma 4.2.3 Suppose(i1,i2,i3)=(2,3,1). Then the following hold.
(1) E10= {(−1,0), (1,2), (2,3)}. (2) E20= {(−1,0), (1,3), (2,1)}. (3) E21= {(0,1), (2,0), (3,3)}. (4) E31= {(0,2), (2,3), (3,1)}. (5) E32= {(0,1), (1,3), (3,2)}. (6) E33= {(1,2), (2,1), (3,3)}.
Proof: Similar to the proof of Sublemma 4.2.2. 2
We use circuit chasing technique again. Let C= {x0,x1, . . . ,x9,x10 =x0}be a circuit of length 2s+6=10 in0such that the profile with respect to(x0,x1)is as follows:
0 1 2 3 3 1 0
0 1 3 3 2 1 0.
Note that∂(ˆ x0,x3)=s+1=3. By Sublemma 4.2.3, we see that the profile of C with respect to(x2,x3)is
0 2 1 0 2 1 0
0 2 1 3 3 2 0.
This implies that∂(ˆ x3,x0)= s+2 =4, which is a contradiction. Thus we have the assertion.
Now we conclude the proof of Lemma 4.2.
Lemma 4.3 It is impossible thatXis of type IIA.
Proof: Suppose that(i1,i2,i3)= (0,2,1). Then we see that ps1+,s1 = 2 and p1s+,s1+2 = p1s+,s2 = p1s+,s2+1 = 1. By using the formula kl · pli,j = ki · pil,j, these imply that ks = 2·ks+1=ks+2and ks+1=ks+2. These are impossible.
