Revista Colombiana de Matemáticas Volumen 32 (1998), páginas 1–12

On the graph on a Weyl group being an interval graph

Hemendra K. Patel Suresh G. Hulsurkar Indian Institute of Technology, Kharagpur, INDIA

Abstract. We consider the graph on a Weyl group whose associated root system is arbitrary. It is shown that such a graph is an interval graph only when the associated root systems are of some particular types. Key Words and Phrases: root systems, Weyl groups, interval graph. 1991 Mathematics Subject Classification. Primary 20F55.

1. Introduction

The graphs on Weyl groups were defined and studied in [1]. The basic idea was to define the graph on Weyl groups using a relation on the Weyl groups introduced in [6]. The relation on Weyl groups arose due to the technique used in proving the Verma’s conjecture on Weyl’s dimension polynomial. This new relation on Weyl groups gives rise to a partial order in a very natural manner. This partial order or the incidence matrix of our graph on Weyl groups has applications in the representation of algebraic Chevally groups [7]. Several problems on the graph on Weyl groups have been solved: [2], [3], [4], [5]. In this paper we determine the Weyl groups for which the associated graph is an interval graph. Here we take the root system to be arbitrary and show that the graph on the Weyl group with such a root system is an interval graph only when the root system is essentially of the type A_{2}, A_{3}, B_{2}, A_{3} ×A_{3}, A_{3} ×B_{2} or B_{2} × B_{2}. We summarize below few facts about root systems and Weyl groups but for details we refer to [8].

Let E be a Euclidean space of dimension n with a positive definite inner product ( , ). For any vector α ∈ E we can define a reflection R_{α} whose action on λ ∈ E is given by λR_{α} = λ − (λ, α^{∨})α. Suppose Φ is a root system in E. Then the reflections R_{α}, α ∈ Φ generate the finite group called Weyl group W (Φ) associated with the root system Φ. If α_{1}, α_{2}, …, α_{n} are the simple roots in Φ then R_{α_{i}}, i = 1, 2, …, n, generate the Weyl group W (Φ). Let R_{α_{i}} = R_{i} for i = 1, 2, …, n. Then the elements of the Weyl group W (Φ) can be written as the product of the generators R_{1}, R_{2},…,R_{n}. In general, for any element σ in W, the expression σ = R_{i_{1}}R_{i_{2}} ⋯ R_{i_{k}} is not unique. The minimum value of k in all such expressions for a given σ ∈ W (Φ) is called the length l(σ) of σ. There exists a unique element σ_{0} in W (Φ) which has maximum length. Let λ_{1}, λ_{2}, …, λ_{n} be the fundamental weights of Φ. Then we have by definition (λ_{i}, α_{j}^{∨}) = δ_{ij} (Kronecker delta) for i, j = 1, 2, …, n. The action of R_{i} on λ_{j} is given by λ_{j}R_{i} = λ_{j} − δ_{ij}α_{i}. For σ ∈ W (Φ), define I_{σ} = { i | 1 ≤ i ≤ n, l(σR_{i}) < l(σ)}. Let δ_{σ} = ∑_{i∈I_{σ}} λ_{i} and ε_{σ} = δ_{σ}σ^{−1}. We also write W for W (Φ).

2. The graph on Weyl group

A point λ ∈ E is called W -regular iff λ lies in the interior of a Weyl chamber relative to the root system Φ. It can be shown that the point λ ∈ E is W - regular iff D(λ) ≠ 0 where D(λ) is the Weyl’s dimension polynomial. This enables us to define a new relation ⟶ on W. For σ, τ ∈ W, define σ ⟶ τ iff −ε_{σσ_{0}} + ε_{τ} is W -regular. The relation ε_{σσ_{0}} = −(δ − δ_{σ})σ^{−1} for σ ∈ W, proved in [6], shows that σ ⟶ σ. It is shown [6] that only one of σ ⟶ τ and τ ⟶ σ holds if σ ≠ τ. We define the graph Γ(W (Φ)) whose vertices are the elements of the Weyl group W (Φ) and for distinct σ, τ ∈ W (Φ) the unordered pair (σ, τ) is an edge iff either σ ⟶ τ or τ ⟶ σ holds. This gives a graph in the usual sense [9]. The definition of an edge in Γ(W (Φ)) shows that the graph depends upon Φ also. We write Γ(W) or Γ(Φ) for the graph Γ(W (Φ)).

Let J be a subset of I = {1, 2, …, n}. Then the roots { α_{j} | j ∈ J } give a root system Φ_{J} and the group W_{J} generated by R_{j}, j ∈ J is the Weyl group of Φ_{J}. It is easy to see that W = W_{I}. We have the following result on W_{J} proved in [3]. Lemma 1. For distinct σ, τ ∈ W_{J}, the unordered pair (σ, τ) is an edge in Γ(W_{J}) iff (σ, τ) is an edge in Γ(W). In particular, Γ(W_{J}) is an induced subgraph of Γ(W).

3. Irreducible root systems

In general, a root system Φ is a union of irreducible root systems. So first we consider Γ(Φ) when Φ is an irreducible root system. The irreducible root systems are of the following types: A_{n} for n ≥ 1, B_{n} for n ≥ 2, C_{n} for n ≥ 3, D_{n} for n ≥ 4, E_{6}, E_{7}, E_{8}, F_{4} and G_{2}.

If the root system is of the type X, we write Γ(X) for Γ(Φ). For example Γ(B_{2}) means a graph on a Weyl group whose associated root system is of the type B_{2}. The fact that the graph Γ(Φ) depends on the root system Φ also and not merely on the Weyl group is best illustrated by the root systems of the type B_{n} and C_{n}. The graphs Γ(B_{n}) and Γ(C_{n}) for n ≥ 3 are distinct although the Weyl groups W (B_{n}) and W (C_{n}) are isomorphic.

We describe briefly an interval graph. An intersection graph Ω(F) for the family F = {S_{1}, S_{2}, …, S_{m}} of subsets S_{i} of a set S is a graph whose vertices are S_{1}, S_{2}, …, S_{m} and for i ≠ j, S_{i} is said to be adjacent to S_{j} iff S_{i} ∩S_{j} is not a null set. An interval graph is defined to be a graph which is isomorphic to an intersection graph Ω(F), where F is some family of intervals on the real line [9]. One can easily replace the real line by any linearly ordered set and the intervals on it in the definition of interval graphs in order to make it more general. In fact, with this definition the characterization of interval graphs have been given by Gilmore and Hoffman [11]. We do not need those characterizations in full form. In fact, it is enough for our purpose to know that a graph G cannot be an interval graph if it has a cycle of length 4 as an induced subgraph [9] The interval graphs have also been studied by Boland and Lekkerkerker [10]. We require some definitions from the graph theory. A cycle in a graph Γ means any finite sequence of vertices σ_{1}σ_{2} ⋯ σ_{k} of Γ with the following conditions:

(i) The edges (σ_{i}, σ_{i+1}) for 1 ≤ i ≤ k are in Γ where σ_{k+1} = σ_{1}. (ii) For any two vertices τ and ρ and integers i, j < k, i ≠ j the relation

τ = σ_{i} = σ_{j}, ρ = σ_{i+1} = σ_{j+1} or τ = σ_{i} = σ_{k}, ρ = σ_{i+1} = σ_{1} does not hold.

A cycle σ_{1}σ_{2} ⋯ σ_{k} is called odd or even depending on whether k is odd or even. This definition of cycle allows the repetition of vertices i.e. all the vertices in a cycle need not be distinct. Let σ_{1}σ_{2} ⋯ σ_{k} be a cycle. Then the edges (σ_{i}, σ_{i+2}), 1 ≤ i ≤ k − 2 , (σ_{k−1}, σ_{1}) and (σ_{k}, σ_{2}) are called triangular chords of the cycle σ_{1}σ_{2} ⋯ σ_{k}. With these definitions we have the following theorem of Gilmore and Hoffman: A graph Γ is an interval graph iff every quadrilateral in Γ has a diagonal and every odd cycle in Γ^{c}, the complementary graph of Γ, has a triangular chord [11].

We show that the graph Γ(Φ) on a Weyl group corresponding to an irreducible root system Φ has a cycle of length 4 as an induced subgraph except in few cases. First we show that a cycle of length 4 occurs as an induced subgraph in the graphs Γ(A_{4}), Γ(B_{3}), Γ(C_{3}), Γ(D_{4}) and Γ(G_{2}). Next we show that for an irreducible root system Φ the graph Γ(Φ), when Φ is not a root system of type A_{1}, A_{2}, A_{3} and B_{2}, has one of the graphs Γ(A_{4}), Γ(B_{3}), Γ(C_{3}), Γ(D_{4}) and Γ(G_{2}) as an induced subgraph. Before going into the details of the method we describe briefly the graph Γ(Φ) on a Weyl group for root systems Φ of low orders. The graphs Γ(A_{1}) and Γ(A_{2}) are totally disconnected and have 2 and 6 vertices respectively. The graph Γ(A_{3}) has 24 vertices in which 8 are isolated and has 8 disjoint edges. The graph Γ(B_{2}) has 8 vertices with 4 disjoint edges. This leaves the following graphs on Weyl groups corresponding to an irreducible root system:

\begin{matrix}Γ(A_{n}) for n ≥ 4, & Γ(B_{n}) for n ≥ 3, & Γ(C_{n}) for n ≥ 3, \\ Γ(D_{n}) for n ≥ 4, & Γ(E_{6}) , & Γ(E_{7}), \\ Γ(E_{8}) , & Γ(F_{4}) , & Γ(G_{2}). \end{matrix} \} (∗)

According to the method described before, now we prove the following. Proposition. The graphs Γ(A_{4}), Γ(B_{3}), Γ(C_{3}), Γ(D_{4}) and Γ(G_{2}) are not interval graphs. Proof. We show that each of the graphs in the statement has a cycle of length 4 as an induced subgraph. In each case we display the 4 elements of the relevant group which gives a cycle of length 4 as an induced subgraph. We give a table displaying the elements σ of a Weyl group along with ε_{σ} and ε_{σσ_{0}}. It is easy to verify that D(−ε_{σσ_{0}} + ε_{τ}) is zero or not for a given pair of elements σ, τ in this table. The elements of the Weyl group are of the form R_{i_{1}}R_{i_{2}} ⋯ R_{i_{k}} and for convenience we write this as i_{1}i_{2} ⋯ i_{k}. For example we write 2312 for R_{2}R_{3}R_{1}R_{2}. The identity element of a Weyl group is written as id.

(i) The graph Γ(A_{4}) has 120 vertices and 180 edges. For λ ∈ E we have λ = xλ_{1} + yλ_{2} + zλ_{3} + tλ_{4} and the Weyl’s dimension polynomial D(λ) in this case is \frac{ϕ(x,y,z,t)}{ϕ(1,1,1,1)} where

ϕ(x, y, z, t) = xyzt(x + y)(y + z)(z + t)(x + y + z)(y + z + t)(x + y + z + t).

The four elements σ_{1}, σ_{2}, σ_{3} and σ_{4} which give the edges (σ_{1}, σ_{2}), (σ_{2}, σ_{3}), (σ_{3}, σ_{4}) and (σ_{4}, σ_{1}) making a cycle of length 4 as an induced subgraph are listed below. We conclude that Γ(A_{4}) is not an interval graph.

\begin{matrix}S. No. & σ & ε_{σ} & ε_{σσ_{0}} \\ 1 & σ_{1}= id & 0 & −λ_{1} − λ_{2} − λ_{3} − λ_{4} \\ 2 & σ_{2}= 324 & λ_{1} + λ_{2} − 2λ_{3} + λ_{4} & −λ_{1} − λ_{2} + λ_{3} − λ_{4} \\ 3 & σ_{3} = 4321 & −λ_{4} & −λ_{1} − λ_{2} − λ_{3} + 3λ_{4} \\ 4 & σ_{4} = 14232 & −2λ_{1} + λ_{2} + λ_{3} − 2λ_{4} & λ_{1} − λ_{2} − λ_{3} + λ_{4} \end{matrix}

(ii) The graph Γ(B_{3}) has 48 vertices and 100 edges. For λ ∈ E, λ = xλ_{1} + yλ_{2} +zλ_{3} and the Weyl’s dimension polynomial D(λ) is given by \frac{ϕ(x,y,z)}{ϕ(1,1,1)} where

ϕ(x, y, z) = xyz(x + y)(y + z)(2y + z)(x + y + z)(x + 2y + z)(2x + 2y + z).

The four elements σ_{1}, σ_{2}, σ_{3} and σ_{4} which give the edges (σ_{1}, σ_{2}), (σ_{2}, σ_{3}), (σ_{3}, σ_{4}) and (σ_{4}, σ_{1}) making a cycle of length 4 are listed below. This cycle is also an induced subgraph. It shows that Γ(B_{3}) is not an interval graph.

\begin{matrix}S. No. & σ & ε_{σ} & ε_{σσ_{0}} \\ 1 & σ_{1}= id & 0 & −λ_{1} − λ_{2} − λ_{3} \\ 2 & σ_{2}= 321 & λ_{2} − 2λ_{3} & −λ_{1} − 2λ_{2} + 3λ_{3} \\ 3 & σ_{3} = 2323 & 3λ_{1} − λ_{2} − λ_{3} & −λ_{1} \\ 4 & σ_{4} = 213 & λ_{1} − 2λ_{2} + 3λ_{3} & −λ_{1} + λ_{2} − 2λ_{3} \end{matrix}

(iii) The graph Γ(C_{3}) has 48 vertices and 96 edges. For λ ∈ E, λ = xλ_{1} +yλ_{2} + zλ_{3} and the Weyl’s dimension polynomial D(λ) is given by \frac{ϕ(x,y,z)}{ϕ(1,1,1)} where

ϕ = xyz(x + y)(y + z)(y + 2z)(x + y + z)(x + y + 2z)(x + 2y + 2z).

We give below the 4 elements σ_{1}, σ_{2}, σ_{3} and σ_{4} which make a cycle of length 4 whose edges are (σ_{1}, σ_{2}), (σ_{2}, σ_{3}), (σ_{3}, σ_{4}) and (σ_{4}, σ_{1}) and which is also an induced subgraph of Γ(C_{3}). This proves that Γ(C_{3}) is not an interval graph.

\begin{matrix}S. No. & σ & ε_{σ} & ε_{σσ_{0}} \\ 1 & σ_{1}= id & 0 & −λ_{1} − λ_{2} − λ_{3} \\ 2 & σ_{2}= 2132 & λ_{1} − 2λ_{2} + λ_{3} & −2λ_{1} + 3λ_{2} − 2λ_{3} \\ 3 & σ_{3} = 1231213 & −λ_{1} − 2λ_{2} + λ_{3} & λ_{1} + λ_{2} − λ_{3} \\ 4 & σ_{4} = 1232 & −2λ_{1} − λ_{2} & 3λ_{1} − λ_{2} − λ_{3} \end{matrix}

(iv) The graph Γ(D_{4}) has 192 vertices and 624 edges. For λ ∈ E, λ = xλ_{1} + yλ_{2} +zλ_{3} +tλ_{4} and the Weyl’s dimension polynomial D(λ) is given by \frac{ϕ(x,y,z,t)}{ϕ(1,1,1,1)} where

ϕ(x, y, z, t) =

xyzt(x+y)(y+z)(y+t)(x+y+z)(x+y+t)(y+z+t)(x+y+z+t)(x+2y+z+t).

The required 4 elements σ_{1}, σ_{2}, σ_{3} and σ_{4} are listed below. These give an induced subgraph of Γ(D_{4}) which is a cycle of length 4 with edges (σ_{1}, σ_{2}), (σ_{2}, σ_{3}), (σ_{3}, σ_{4}) and (σ_{4}, σ_{1}). This shows that Γ(D_{4}) is not an interval graph.

\begin{matrix}S. No. & σ & ε_{σ} & ε_{σσ_{0}} \\ 1 & σ_{1}= id & 0 & −λ_{1} − λ_{2} − λ_{3} − λ_{4} \\ 2 & σ_{2}= 24312 & λ_{1} − 2λ_{2} + λ_{3} + λ_{4} & −2λ_{1} + 3λ_{2} − 2λ_{3} − 2λ_{4} \\ 3 & σ_{3} = 324312134 & λ_{1} − 2λ_{2} − λ_{3} + λ_{4} & −λ_{1} + λ_{2} + λ_{3} − λ_{4} \\ 4 & σ_{4} = 32412 & λ_{2} − 2λ_{3} & −λ_{1} − λ_{2} + 3λ_{3} − λ_{4} \end{matrix}

(v) The graph Γ(G_{2}) has 12 vertices and 12 edges. For λ ∈ E, λ = xλ_{1} + yλ_{2} and the Weyl’s dimension polynomial D(λ) is given by \frac{ϕ(x,y)}{ϕ(1,1)} where

ϕ = xy(x + y)(x + 2y)(x + 3y)(2x + 3y).

We list below 4 elements σ_{1}, σ_{2}, σ_{3} and σ_{4}. These elements give a cycle of length 4 with edges (σ_{1}, σ_{2}), (σ_{2}, σ_{3}), (σ_{3}, σ_{4}) and (σ_{4}, σ_{1}) which is also an induced subgraph of Γ(G_{2}).

\begin{matrix}S. No. & σ & ε_{σ} & ε_{σσ_{0}} \\ 1 & σ_{1}= id & 0 & −λ_{1} − λ_{2} \\ 2 & σ_{2}= 121 & −2λ_{1} + λ_{2} & 3λ_{1} − 2λ_{2} \\ 3 & σ_{3} = 121212 & −λ_{1} − λ_{2} & 0 \\ 4 & σ_{4} = 212 & 3λ_{1} − 2λ_{2} & −2λ_{1} + λ_{2} \end{matrix}

Therefore we conclude that Γ(G_{2}) is not an interval graph. □ ✓

We now come to our main result. Theorem 1. Let Φ be an irreducible root system. The only graphs Γ(Φ) on the Weyl groups which are interval graphs are Γ(A_{1}), Γ(A_{2}), Γ(A_{3}) and Γ(B_{2}). Proof. Recall that the graphs Γ(A_{1}), Γ(A_{2}), Γ(A_{3}) and Γ(B_{2}) have the connected components as isolated vertices and disjoint edges. An isolated vertex and a disjoint edge are the interval graphs of a single interval and two intersecting intervals on a real line respectively. Therefore, the union of appropriate number of disjoint single intrevals and two intersecting intervals on a real line gives the graphs on Γ(A_{1}), Γ(A_{2}), Γ(A_{3}) and Γ(B_{2}). This proves that these graphs are interval graphs.

Next we show that the remaining graphs on Weyl groups, which are precisely those listed in (∗), are not interval graphs. Our method of proof is to show that each of the graphs in (∗) has one of the graphs Γ(A_{4}), Γ(B_{3}), Γ(C_{3}), Γ(D_{4}) and Γ(G_{2}) as an induced subgraph. Then by Lemma 1, and the proposition it follows that the graphs in (∗) are not interval graphs. For each of the graph in (∗) we exhibit a proper choice of J so that Γ(W_{J}) is one of the graphs in the proposition. For the explicit choice of J we refer to the Dynkin diagrams of the irreducible root system given in [9, p. 58]. For the graph Γ(A_{n}) for n ≥ 4 choose J = {1, 2, 3, 4} to get Γ(A_{4}) as an induced subgraph. In the case of Γ(B_{n}) for n ≥ 3 and Γ(F_{4}) choose J = {n − 2, n − 1, n} and J = {1, 2, 3} respectively to get an induced subgraph Γ(B_{3}). The graph Γ(C_{3}) is an induced subgraph of Γ(C_{n}) for n ≥ 3 with J = {n − 2, n − 1, n}. The graphs Γ(D_{n}) for n ≥ 4, Γ(E_{6}), Γ(E_{7}) and Γ(E_{8}) have Γ(D_{4}) as an induced subgraph with J = {n − 3, n − 2, n − 1, n} for Γ(D_{n}) and J = {2, 3, 4, 5} for the rest. The graph Γ(G_{2}) is not an interval graph by the proposition. This complete the proof. □ ✓

4. Arbitrary root systems

Let Φ be a root system. If Φ is not irreducible then it is a union of irreducible root systems. It is known that the Dynkin diagram of Φ is connected iff Φ is irreducible root system. If Φ is reducible and is union of irreducible root systems Φ_{1}, Φ_{2}, …, Φ_{k} then the connected components of the Dynkin diagram of Φ are precisely the Dynkin diagram of each irreducible component Φ_{i} of Φ. The Dynkin diagram also determines the Weyl group uniquely. The Weyl group W (Φ) is the direct product of the Weyl groups W (Φ_{i}), i = 1, 2, …, k. If any one of the root system Φ_{i} is of the type given in (∗) then the graph Γ(Φ) cannot be an interval graph by Lemma 1. Therefore we can assume that Φ is a union of the root systems of the type A_{1}, A_{2}, A_{3} and B_{2} where repetitions are allowed. We require some results to analyze such a root system Φ. Suppose Φ is a union of two root systems Φ_{1} and Φ_{2} which are not necessarily irreducible. In this case we write Φ = Φ_{1} ×Φ_{2} and if Φ_{1} = Φ_{2} then Φ = (Φ_{1})^{2}. The Weyl group W of Φ is the direct product of the Weyl groups W_{1} and W_{2} of the root systems Φ_{1} and Φ_{2} respectively. Since W = W_{1} × W_{2} (direct product), every element ρ ∈ W can be written uniquely as ρ = στ with σ ∈ W_{1} and τ ∈ W_{2}. Also I_{ρ} = I_{σ} ∪ I_{τ} (disjoint union) and ε_{ρ} = ε_{σ} ⊕ ε_{τ} (direct sum). This shows that ε_{στ} = ε_{σ} ⊕ ε_{τ} for σ ∈ W_{1} and τ ∈ W_{2}. If δ, δ_{1} and δ_{2} are the fundamental weights of the root systems Φ, Φ_{1} and Φ_{2} respectively then δ = δ_{1} ⊕ δ_{2}. It is easy to see that if σ_{0}, σ0^{′} and σ0^{′′} are the unique elements of maximal length in W, W_{1} and W_{2} respectively then σ_{0} = σ0^{′}σ0^{′′}. Similar relations hold if Φ is a union of more than two root systems.

With above notations we prove the following results. Lemma 2. Let σ_{1}, σ_{2} ∈ W_{1} and τ_{1}, τ_{2} ∈ W_{2}. The relations σ_{1} ⟶ σ_{2} in W_{1} and τ_{1} ⟶ τ_{2} in W_{2} hold iff σ_{1}τ_{1} ⟶ σ_{2}τ_{2} in W = W_{1} ×W_{2} holds. If σ_{1} ⟶ σ_{2} in W_{1} with σ_{1} ≠ σ_{2} and τ_{1} ⟶ τ_{2} in W_{2} with τ_{1} ≠ τ_{2} then σ_{1}τ_{2} ↛ σ_{2}τ_{1} and σ_{2}τ_{1} ↛ σ_{1}τ_{2} in W. Proof. For the first part of the statement see [5]. The proof for the second is by contradiction. Suppose σ_{1}τ_{2} ⟶ σ_{2}τ_{1}. The result in the first part implies that σ_{1} ⟶ σ_{2} in W_{1} and τ_{2} ⟶ τ_{1} in W_{2}. But by assumption τ_{1} ⟶ τ_{2} in W_{2}. But both τ_{1} ⟶ τ_{2} and τ_{2} ⟶ τ_{1} in W_{2} cannot be true [6]. Therefore σ_{1}τ_{2} ↛ σ_{2}τ_{1}. Similarely σ_{2}τ_{1} ↛ σ_{1}τ_{2} can be proved. □ ✓

Remark. The lemma can be generalized when W = W_{1} × W_{2} × ⋯ × W_{k}.

Lemma 3. Let (σ_{1}, σ_{2}) be an edge in Γ(W_{1}) and (τ_{1}, τ_{2}) be an edge in Γ(W_{2}). Then the induced subgraph for the 4 vertices σ_{i}τ_{j}, i, j = 1, 2, in Γ(W_{1} × W_{2}) is a quadrilateral with a diagonal. More precisely, if σ_{1} ⟶ σ_{2} in W_{1} and τ_{1} ⟶ τ_{2} in W_{2} then following are the only edges joining the vertices σ_{i}τ_{j}, i, j = 1, 2 in Γ(W_{1} × W_{2}): (σ_{1}τ_{1}, σ_{2}τ_{1}), (σ_{1}τ_{2}, σ_{2}τ_{2}), (σ_{1}τ_{1}, σ_{1}τ_{2}), (σ_{2}τ_{1}, σ_{2}τ_{2}) and (σ_{1}τ_{1}, σ_{2}τ_{2}). Proof. If W is any Weyl group then for σ ∈ W we always have σ ⟶ σ [6]. Therefore, σ_{i} ⟶ σ_{i} for i = 1, 2 in W_{1} and τ_{i} ⟶ τ_{i} for i = 1, 2 in W_{2}. The result follows by applying Lemma 2 to σ_{1} ⟶ σ_{2} in W_{1}, τ_{1} ⟶ τ_{2} in W_{2} and to σ_{i} ⟶ σ_{i} for i = 1, 2 in W_{1} and τ_{i} ⟶ τ_{i} for i = 1, 2 in W_{2}. □ ✓

In a graph Γ, we shall call a vertex isolated if it is not adjacent to any other vertex and an edge disjoint if it is not adjacent to any other edge. With these definitions we prove the following. Lemma 4. Let σ ∈ W_{1} and τ ∈ W_{2}. Then σ and τ are isolated vertices in Γ(W_{1}) and Γ(W_{2}) respectively iff στ is an isolated vertex in Γ(W_{1} × W_{2}). Proof. We show that if neither σ is an isolated vertex in Γ(W_{1}) nor τ is an isolated vertex in Γ(W_{2}) then στ is not an isolated vertex in Γ(W_{1} × W_{2}). Suppose σ is not an isolated vertex in Γ(W_{1}). Then for some σ_{1} ∈ W_{1}, (σ, σ_{1}) is an edge in Γ(W_{1}). By Lemma 2, (στ, σ_{1}τ) is an edge in Γ(W_{1} × W_{2}) as σ ⟶ σ_{1} in W_{1}. This shows that στ is not an isolated vertex. Same result can be proved if we assume that τ is not an isolated vertex in Γ(W_{2}).

Conversely, suppose στ is not an isolated vertex in Γ(W_{1} × W_{2}). Then for some ρ ∈ W_{1}×W_{2}, ρ ≠ στ, the unordered pair (στ, ρ) is an edge in Γ(W_{1}×W_{2}). Now ρ ∈ W_{1} × W_{2} implies that ρ = σ_{1}τ_{1} for unique σ_{1} ∈ W_{1} and τ_{1} ∈ W_{2}. Therefore, (στ, σ_{1}τ_{1}) is an edge in Γ(W_{1} × W_{2}) and this gives στ ⟶ σ_{1}τ_{1} which in turn gives σ ⟶ σ_{1} in W_{1} and τ ⟶ τ_{1} in W_{2}. Since ρ = σ_{1}τ_{1} ≠ στ, we must have either σ ≠ σ_{1} or τ ≠ τ_{1}. Therefore, either σ ⟶ σ_{1} with σ ≠ σ_{1} or τ ⟶ τ_{1} with τ ≠ τ_{1}. We conclude that either (σ, σ_{1}) is an edge in Γ(W_{1}) or (τ, τ_{1}) is an edge in Γ(W_{2}). This shows that either σ is not an isolated vertex in Γ(W_{1}) or τ is not an isolated vertex in Γ(W_{2}). □ ✓ Corollary. The graphs Γ(W_{1}) and Γ(W_{2}) are totally disconnected if and only if Γ(W_{1} × W_{2}) is totally disconnected. Remark. This corollary has obvious generalization to the direct product of more than two Weyl groups.

Next we need a result proved in [3] which is stated below.

Lemma 5. If Γ(W_{1}) is totally disconnected and Γ(W_{2}) is any graph on a Weyl group W_{2} then Γ(W_{1} × W_{2}) consists of |W_{1}| number of disjoint copies of the graph Γ(W_{2}).

The following result will be required in the proof of our main result.

Lemma 6. Suppose the graphs Γ(W_{1}) and Γ(W_{2}) are such that their connected components are isolated vertices or disjoint edges or both. Then the graph Γ(W_{1} × W_{2}) is an interval graph.

Proof. We have shown in Lemma 4, that if σ ∈ W_{1} and τ ∈ W_{2} are isolated vertices in Γ(W_{1}) and Γ(W_{2}) then στ is an isolated vertex in Γ(W_{1} × W_{2}).

Next we prove that an isolated vertex σ ∈ W_{1} in Γ(W_{1}) and a disjoint edge (τ_{1}, τ_{2}) in Γ(W_{2}) for τ_{1}, τ_{2} ∈ W_{2} gives a disjoint edge (στ_{1}, στ_{2}) in Γ(W_{1}×W_{2}). Suppose (στ_{1}, στ_{2}) is not a disjoint edge in Γ(W_{1} × W_{2}). Then either for some ρ ≠ στ_{2}, the pair (στ_{1}, ρ) or for ρ ≠ στ_{1} the pair (στ_{2}, ρ) is an edge in Γ(W_{1} × W_{2}). Suppose (στ_{1}, ρ) with ρ ≠ στ_{2} is an edge in Γ(W_{1} × W_{2}). This gives ρ ∈ W_{1} ×W_{2} and ρ = σ_{1}τ_{3} with unique σ_{1} ∈ W_{1} and τ_{3} ∈ W_{2} and ρ ≠ στ_{1} and ρ ≠ στ_{2} i.e. στ_{1} ≠ σ_{1}τ_{3} and στ_{2} ≠ σ_{1}τ_{3}. The last part shows that either σ ≠ σ_{1} or τ_{1} ≠ τ_{3} and τ_{2} ≠ τ_{3}. If (στ_{1}, σ_{1}τ_{3}) is an edge in Γ(W_{1} × W_{2}) then στ_{1} ⟶ σ_{1}τ_{3}. By Lemma 2, σ ⟶ σ_{1} and τ_{1} ⟶ τ_{3}. Therefore, if σ ≠ σ_{1} then (σ, σ_{1}) is an edge in Γ(W_{1}) and if τ_{1} ≠ τ_{3} then (τ_{1}, τ_{3}) where τ_{3} ≠ τ_{2} is an edge in Γ(W_{2}). This shows that either σ is not an isolated vertex or (τ_{1}, τ_{2}) is not a disjoint edge. A contradiction. Similar contradiction is arrived at if (στ_{2}, ρ) with ρ ≠ στ_{1} is an edge in Γ(W_{1} × W_{2}). We conclude that (στ_{1}, στ_{2}) is a disjoint edge in Γ(W_{1} × W_{2}).

Next suppose (σ_{1}, σ_{2}) and (τ_{1}, τ_{2}) are disjoint edges in Γ(W_{1}) and Γ(W_{2}) respectively. Lemma 3 shows that the 4 vertices σ_{i}τ_{j}, i, j = 1, 2 in Γ(W_{1} ×W_{2}) give a quadrilateral with a diagonal. Again we can show that this quadrilateral with a diagonal is a connected component of the graph Γ(W_{1} × W_{2}) by the arguments similar to those used in the previous paragraph.

This shows that a connected component of the graph Γ(W_{1} × W_{2}) is either a vertex or an edge or else a quadrilateral with a diagonal. The first two are interval graphs where we can take a single interval or two intersecting intervals on the real line. For the last one take intervals as given below: let x_{1}, x_{2}, …, x_{8} be real number with x_{1} < x_{2} < x_{3}< x_{4} < x_{5} <x_{6} < x_{7} < x_{8} and a = [x_{3}, x_{7}], b = [x_{5}, x_{8}], c = [x_{2}, x_{6}] and d = [x_{1}, x_{4}] be the 4 intervals. These give a quadrilateral abcd with diagonal ac. This proves that Γ(W_{1} × W_{2}) is an interval graph. □ ✓

Lemma 7. Let Φ_{1}, Φ_{2} and Φ_{3} be root systems such that each of Γ(Φ_{1}), Γ(Φ_{2}) and Γ(Φ_{3}) has at least one edge. Then Γ(Φ_{1} × Φ_{2} × Φ_{3}) is not an interval graph.

Proof. Let W_{i} = W (Φ_{i}), i = 1, 2, 3. Suppose σ_{1}, σ_{2} ∈ W_{1}; τ_{1}, τ_{2} ∈ W_{2}; ρ_{1}, ρ_{2} ∈ W_{3} and (σ_{1}, σ_{2}), (τ_{1}, τ_{2}) and (ρ_{1}, ρ_{2}) are edges in Γ(Φ_{1}), Γ(Φ_{2}) and Γ(Φ_{3}) respectively. Therefore, we also have σ_{1} ⟶ σ_{2} in W_{1}, τ_{1} ⟶ τ_{2} in W_{2} and ρ_{1} ⟶ ρ_{2} in W_{3}. If W = W (Φ_{1} × Φ_{2} × Φ_{3}) then the 8 elements σ_{i}τ_{j}ρ_{k}, i, j, k = 1, 2 are in W. Put σ_{1}τ_{1}ρ_{1} = o, σ_{2}τ_{1}ρ_{1} = a, σ_{1}τ_{2}ρ_{1} = b, σ_{1}τ_{1}ρ_{2} = c, σ_{2}τ_{2}ρ_{1} = d, σ_{1}τ_{2}ρ_{2} = e, σ_{2}τ_{1}ρ_{2} = f, σ_{2}τ_{2}ρ_{2} = g. By the repeated application of the Lemma 2 to the edges (σ_{1}, σ_{2}), (τ_{1}, τ_{2}) and (ρ_{1}, ρ_{2}) we get the following 19 edges in Γ(W) i.e., Γ(Φ_{1} × Φ_{2} × Φ_{3}): oa, ob, oc, od, oe, of, og, ce, be, cf, af, cg, dg, bd, eg, bg, ad, fg and ag. The induced subgraph Γ_{1} of these 8 vertices o, a, b, c, d, e, f and g in Γ(W) is shown in Figure 1.

[figure: o; g; f; e; d; c; b; a]

Figure 1. The graph Γ_{1}.

It is easy to see that every quadrilateral in Γ_{1} has a diagonal. In any case, we consider the graph Γ_{1}^{c}, the complementary graph of Γ_{1}, shown in Figure 2.

The graph Γ_{1}^{c} has an odd cycle α = eabfbcdca which has no triangular chord. The cycle α is also an odd cycle with no triangular chord in Γ^{c}(W) as Γ_{1} is an induced subgraph of Γ(W). Therefore, by the theorem of Gilmore and Hoffman [11] the graph Γ(W) i.e. Γ(Φ_{1} × Φ_{2} × Φ_{3}) is not an interval graph. □ ✓

[figure: e; f; d; a; b; c]

Figure 2. The graph Γ_{1}^{c}.

Theorem 2. Let Φ be any root system. The graph Γ(Φ) is an interval graph iff Φ is equal to Φ_{1} or Φ_{2} or else Φ_{1} × Φ_{2} where Φ_{1} is a root system of type (A_{1})^{k_{1}} × (A_{2})^{k_{2}} where k_{1}, k_{2} are nonnegative integers with at least one of k_{1}, k_{2} nonzero, and Φ_{2} is any one of the following root systems: A_{3}, B_{2}, A_{3} × A_{3}, A_{3} × B_{2} and B_{2} × B_{2}. Proof. The graphs Γ(A_{1}) and Γ(A_{2}) are totally disconnected. By Lemma 4, the graph Γ(A_{1}^{k_{1}} × A_{2}^{k_{2}}) is also totally disconnected. Therefore Γ(Φ_{1}) is an interval graph as an isolated vertex can be obtained by a single interval on a real line. As mentioned earlier we have shown that Γ(A_{3}) and Γ(B_{2}) are interval graphs. The connected components of the graphs Γ(A_{3}) and Γ(B_{2}) are isolated vertices and disjoint edges. Therefore by Lemma 6, the graphs Γ(A_{3} × A_{3}), Γ(A_{3} × B_{2}) and Γ(B_{2}×B_{2}) are interval graphs. This shows that Γ(Φ_{2}) is an interval graph. Next, the graph Γ(Φ_{1}) is totally disconnected and hence by Lemma 5 the graph Γ(Φ_{1} × Φ_{2}) has |W (Φ_{1})| number of disjoint copies of the graph Γ(Φ_{2}). Here |W (Φ_{1})| is the number of elements in W (Φ_{1}) i.e. number of vertices in Γ(Φ_{1}). This shows that the graph Γ(Φ_{1} × Φ_{2}) is an interval graph as Γ(Φ_{2}) is an interval graph.

Next we prove the converse. The Theorem 1 shows that if Φ contains any root system given in (∗), then Γ(Φ) is not an interval graph by Lemma 1. Suppose Φ does not contain any of the root systems given in (∗) and Φ_{2}. Then Φ is union of at least 3 root systems of type A_{3} and B_{2} with repetitions. Since Γ(A_{3}) and Γ(B_{2}) are not totally disconnected, by Lemma 7 the graph Γ(Φ) is not an interval graph. □ ✓

References

[1] Samy A. Youssef, The graphs on Weyl groups, Ph.D. Thesis, Indian Institute of Technology, Kharagpur, 1992.

[2] Samy A. Youssef & S. G. Hulsurkar, On automorphisms of a graph on Weyl groups, J. Math. Phy. Sci. 26 (1992), 419–423.

[3] Samy A. Youssef & S. G. Hulsurkar, On planarity of graphs on Weyl groups, Tamkang Journal of Mathematics 26(1995), 365–373.

[4] Samy A. Youssef & S. G. Hulsurkar, On connectedness of graphs on Weyl groups of type A_{n}(n ≥ 4), Archivum Mathematicum 31 (1995), 163–170.

[5] Samy A. Youssef & S. G. Hulsurkar, More on the girth of the graphs on Weyl groups, Archivum Mathematicum 29 (1993), 19–23.

[6] S. G. Hulsurkar, Proof of Verma’s conjecture on Weyl’s dimension polynomial, Inventiones Math. 27 (1974), 45–52.

[7] L. Chaskofsky, Variation on Hulsurkar’s matrix with applications to representation of algebraic Chevally groups, J. Algebra 82 (1983), 255–274.

[8] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Springer Verlag, New York, 1972.

[9] F. Harary, Graph Theory, Addison Wesley, 1972.

[10] C. G. Lekkerkerker & J. Ch. Boland, Representation of a finite graph by a set of intervals in the real line, Fund. Math. 51 (1962), 45–64.

[11] P. C. Gilmore & A. J. Hoffman, A characterrization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964), 539–548.

(Recibido en febrero de 1996, revisado en diciembre de 1996 y julio de 1997)

Departament of Mathematics Indian Institute of Technology

Kharagpur 721 302, INDIA e-mail: sghulsur@maths.iitkgp.ernet.in