# (0, 2)-Graphs and Root Systems

Authors: Andries E. Brouwer; Leonard Chastkofsky
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

We construct (0, 2)-graphs from root systems with simply laced diagram and study their properties.


---

## Body

## 1. Introduction

In the study of the modp cohomology of the Lie algebra of the unipotent radical U of groups of Lie type with simply laced diagram, it was found that the connected components of the Hasse diagram of the Koszul complex are (0,2)-graphs. This note is the result of an attempt to understand these (0, 2)-graphs.


## 2. (0, 2)-Graphs

A(0,2)-graph is a connected graph with the property that any two vertices have either 0 or 2 common neighbours. The first thing one shows (cf. [10]) is that two adjacent vertices have the same number of neighbours, so that a (0,2)-graph is regular of some valency k (finite or infinite). For a classification of the (0,2)-graphs of valency at most 8, see [2, 5].A(0,2)-graph without triangles is known as a rectagraph. Rectagraphs play a role in diagram geometry, cf., for example, [11].Asemibiplane is a connected incidence structure with points and blocks, where any two points are together in 0 or 2 blocks, and any two blocks meet in 0 or 2 points. Thus, the incidence graph of a semibiplane is a bipartite (0,2)-graph, and conversely any bipartite (0,2)-graph defines a semibiplane, up to duality (i.e., up to the choice which part of the bipartition is the set of points and which part is the set of blocks). Semibiplanes were first introduced in order to study projective planes with involution, see [8].Given a nonbipartite(0,2)-graph, its bipartite double (the unique bipartite 2-cover, cf. [4]) is a bipartite (0,2)-graph.A(0,2)-graph of finite valency k has at most 2k vertices, and the k-cube is the unique (0,2)-graph for which equality holds (see [11]).A(0,2)-graph is called signable if it is possible to label its edges with ±1 in such a way that the product of the signs of the four edges of a quadrangle is always −1. Clearly, a (0,2)-graph with more than one edge is signable if and only if it has a 2-cover without quadrangles. It is known ([7]) that hypercubes are signable, and ([4, page 372]) that the Gewirtz graph is not.


## 3. (0, 2)-Graphs from Root Systems

LetΦ be a finite root system with simply laced diagram, and let Φ+ be the collection of positive roots (for some choice of fundamental roots). For any vector u (the target vector) in the span of Φ, we define the graph Γ=Γ(u)=Γ(Φ,u) as follows: the vertices of Γ are the subsets A of Φ+ such that ∑A(=∑a∈Aa)=u. Two vertices A and B are adjacent when their symmetric difference AΔB has size 3 (Smaller is impossible: if the symmetric difference has size 0, then A=B; it cannot have size 1 since ∑A=∑B=u; it cannot have size 2 since A,B are sets of positive roots).Theorem 1.
IfΓ(u) has a nonempty vertex set, it is a bipartite (0,2)-graph.Proof.
ThatΓ is bipartite follows since adjacent vertices are sets of roots of which the sizes have different parity.
We show thatΓ is connected. Since Φ has simply laced diagram (so that all connected components of the diagram are of type An, Dn or Em, m=6,7,8), we may assume that all roots have the same length 2. Now the roots are precisely the vectors of squared norm 2 in the (integral) lattice spanned by Φ and for r,s∈Φ we have r+s∈Φ when (r,s)=-1 and r-s∈Φ when (r,s)=1. Let A and B be two vertices of Γ. We want to join them by a path. Use induction on the size of the symmetric difference. Let v=∑‍A∖B=∑‍B∖A. Suppose r∈A∖B and s∈B∖A with (r,s)=1. Now r-s is a root, and either r-s or s-r is positive. Say t=r-s∈Φ+. If t∉A, then C=A∖{r}∪{s,t} is a vertex adjacent to A and we are done by induction. If t∈B, then D=B∖{s,t}∪{r} is a vertex adjacent to B and we are done by induction. This means that in the remaining case whenever r∈A∖B and s∈B∖A with (r,s)=1 we have either r-s∈A∖B or s-r∈B∖A. Since (r-s,s)=-1 or (r,s-r)=-1, and the pair r,s can be retrieved from the pair r-s,s or r,s-r, there is a contribution of -1 for each contribution of 1 in the expanded inner product (v,v)=(∑‍A∖B,∑‍B∖A), so that (v,v)≤0 and hence (v,v)=0, so that A=B. This proves connectedness.
We show thatΓ is a (0,2)-graph. Let A,B be two vertices with at least one common neighbour, and put Z=A∩B. Since neighbours have sizes that differ by 1, the sizes of A and B differ by 0 or 2. Suppose first that |A|=|B|+2. If A=Z∪{a,b,c,d} and B=Z∪{a+b,c+d}, then the common neighbours are Z∪{a+b,c,d} and Z∪{a,b,c+d}. If A=Z∪{a,b,c} and B=Z∪{a+b+c} and (a,b)=(b,c)=-1, then the common neighbours are (i) Z∪{a+b,c} if a+b∉Z and Z∖{a+b}∪{a,b,a+b+c} otherwise, and (ii) Z∪{a,b+c} if b+c∉Z and Z∖{b+c}∪{b,c,a+b+c} otherwise. Note that since a+b+c∈Φ, so that (a+b+c,a+b+c)=(a,a)=(b,b)=(c,c)=2, precisely two of the inner products (a,b),(a,c),(b,c) are -1 (and the third is 0). Now suppose that |A|=|B|. If the symmetric difference of A and B has size 6, so that A=Z∪{a,b,c+d} and B=Z∪{a+b,c,d}, then the common neighbours are Z∪{a,b,c,d} and Z∪{a+b,c+d}. If their symmetric difference has size 4, then A=Z∪{a,b} and B=Z∪{c,d}, where a+b=c+d. If a+b∈Φ+, then one common neighbour is Z∪{a+b} if a+b∉Z and Z∖{a+b}∪{a,b,c,d} otherwise. If ±(c-a)∈Φ, say c-a∈Φ+, then one common neighbour is Z∪{a,c-a,d} if c-a∉Z and Z∖{c-a}∪{b,c} otherwise. In this way, we find one common neighbour for each of c-a=b-d and c-b=a-d that is in Φ, that is, for each inproduct (a,c), (a,d) that equals 1. Now (a,c)+(a,d)=(a,a+b)=2+(a,b), and (a,b),(a,c),(a,d)∈{-1,0,1}. If (a,b)=-1, then a+b∈Φ+ and precisely one of (a,c), (a,d) is 1, and we find two common neighbours. If (a,b)=0, then (a,c)+(a,d)=2 so that (a,c)=(a,d)=1, again two common neighbours. Finally, if (a,b)=1, then (a,c)+(a,d)=3, impossible.


## 4. Isomorphisms

Different choices foru may yield isomorphic graphs Γ(u).The mapA↦Φ+∖A sending each set of positive roots to its complement induces an isomorphism from the graph Γ(u) onto the graph Γ(2ρ-u), where 2ρ is the sum of the positive roots.LetW be the Weyl group (generated by the reflections in the elements of Φ), let w∈W, and let N=Φ+∖w-1Φ+ be the set of positive roots made negative by w. The graph Γ(u) is mapped isomorphically onto the graph Γ(w(u-n)), where n=∑‍N, by the map A↦w(A∖N)∪-w(N∖A) that sends A to the union of w(A) and w(-N) with pairs of opposite elements removed. If we parametrize the graphs Γ(u) using μ=ρ-u instead of u, this means that Γμ is mapped isomorphically onto Γwμ. (Indeed, wρ=ρ+wn, so ρ-w(u-n)=wμ). It follows that we may choose u=ρ-μ, where μ is a dominant weight.


## 5. The Number of Vertices

Letρ=(1/2)∑‍Φ+ be half the sum of the positive roots.Proposition 2.
The number of vertices of the graphΓ(u), where u=ρ-μ and μ is a dominant weight, equals the multiplicity of the weight μ in the Verma module Vρ.Proof.
This is Lemma 5.9 in [9]. Or, from Weyl’s character formula: the formal character of Vρ equals A2ρ/Aρ=e(-ρ)∏a∈Φ+‍(e(a)+1), so that the multiplicity of μ equals the number of ways to write ρ+μ as sum of positive roots.Now Freudenthal's formula gives a straightforward way to compute the number of vertices for any givenu.


## 6. The Valency

LetΠ={α1,…,αn} be the set of fundamental roots.Proposition 3.
The graphΓ(u) has valency k=(u,2ρ-u)/2. For u=∑‍uiαi, this becomes k=∑i‍ui-∑i‍ui2+∑e‍uiuj, where the last sum is over all edges e=ij in the Coxeter diagram.Proof.
LetA be a vertex, and B=Φ+∖A its complement. Compute (∑‍A,∑‍B) (which equals (u,2ρ-u)). If r,s are distinct positive roots with (r,s)≠0, then r and s determine a root system of type A2 with a unique third positive root t, and w.l.o.g. t=r+s, so that (r,t)=(s,t)=1, (r,s)=-1. The pairs taken from {r,s,t} only contribute to (∑‍A,∑‍B) when r,s∈A, t∈B or r,s∈B, t∈A (and then the contribution is 2). This means that we find a nonzero contribution (of 2) for each neighbour A∖{r,s}∪{t} or A∖{t}∪{r,s} of A. This proves the formula for the valency k. On the basis Π of fundamental roots, inner products are given by the Cartan matrix, and (u,u)/2=∑‍ui2-∑e‍uiuj, and (u,ρ)=∑‍ui.Lemma 4.
Letu=∑‍uiαi=ρ-μ, where μ is a dominant weight. Then, the graph Γ(u) has valency k≥(1/2)∑‍ui.Proof.
LetC be the Cartan matrix. A vector is converted from root coordinates to weight coordinates by multiplication by C. In weight coordinates ρ=1 and μ≥0, so that Cu≤1, and k=∑‍ui-(1/2)u⊤Cu≥(1/2)∑‍ui.


## 7. Direct Products

Let us write things likeΓ(E6,112321) for the graph Γ(Φ,u) where Φ is a root system of type E6 and u=(ui)i=(1,1,2,3,2,1) on the root basis, where fundamental roots are numbered as in Bourbaki [1].If the Coxeter diagram is disconnected (or the support ofu is), then clearly the corresponding graph is the direct product of the graphs for the components. For example, Γ(D8,11102322) is the direct product Γ(A3,111)×Γ(D4,2322).If the target vectoru contains a 1 on a nonterminal position i, then the graph is the direct product of the two or three graphs that arise by splitting the Coxeter diagram (and target vector) into components at i, preserving a copy of i in each component. For example, Γ(A7,1221221) is the direct product Γ(A4,1221)×Γ(A4,1221). And Γ(D5,12111) is the direct product Γ(A3,121)×Γ(A2,11)×Γ(A2,11). (Proof: Since ui=1, each vertex A contains a unique root r involving αi. Let the projection πA on one of the components consist of the roots in A with support in that component, together with the projection of r on that component. This establishes an isomorphism).In particular,Γ(An+1,11…1) is the n-cube.This discussion, together with Lemma4, implies that one can identify all graphs Γ(Φ,u) with valency at most k0 with a finite amount of work. For the results up to k0=8, see [3].
(1)Valency012345678(0,2)-graphs1112382496301Bipartite1111241340104Signable11112361750fromrootsystem1111235711


## 8. Signability

Theorem 5.
The graphsΓ(Φ,u) are signable.Proof.
LetL=H⊕⨁r∈Φ〈er〉 be a semisimple complex Lie algebra with Cartan subalgebra H and root system Φ, where the structure constants are chosen such that [er,es]=±er+s for r,s,r+s∈Φ (this is possible because Φ is simply laced—see, e.g., [6, Theorem 4.2.1]).
Letk be a field, and let V be the k-vector space with basis Φ+. Let < be an arbitrary fixed total order on Φ+ and identify each vertex A={a1,…,am}, where a1<⋯<am, with the exterior product a1∧⋯∧am∈⋀V. Give the edge joining A and B, where B=A∖{r+s}∪{r,s}, the sign εη (with ε,η=±1) if εA=(r+s)∧a1∧⋯∧am and ηB=r∧s∧a1∧⋯∧am, where [er,es]=er+s. We show that this assignment of signs has the property that the product of the signs on the four edges of a quadrangle is always -1. Note that if ABCD is a quadrangle, we may choose the ordering of the roots at these four vertices independently (since each of these vertices is on two edges of the quadrangle), and invariant tails in the exterior products can be ignored.
Examine the possible shapes of a 4-gonABCD, as found in the proof of the (0,2)-property. Define f(r,s)=±1 by [er,es]=f(r,s)er+s.
IfA=(a+b)∧(c+d), B=(a+b)∧c∧d, C=a∧b∧c∧d, and D=a∧b∧(c+d), then the edges AB,BC,CD, and DA have signs -f(c,d), f(a,b), f(c,d), and f(a,b) with product -1, as desired.
IfA=a+b+c, B=(a+b)∧c, C=a∧b∧c, and D=a∧(b+c), then the signs are f(a+b,c), f(a,b), -f(b,c), and f(a,b+c) with product -1, since the Jacobi identity [[ea,eb],ec]+[[eb,ec],ea]+[[ec,ea],eb]=0 reduces to f(a,b)f(a+b,c)+f(b,c)f(b+c,a)=0 (note that a+c∉Φ).
That covers the case where|A|=|C|±2 (or |B|=|D|±2). Remains the case where |A|=|C| and |B|=|D| and, say, |A|=|B|-1.
IfA=a∧b∧(a+b), B=a∧b∧c∧d, C=c∧d∧(a+b), and D=a∧(c-a)∧d∧(a+b), with a+b=c+d, then the signs are f(c,d), f(a,b), f(a,c-a), and f(d,c-a) with product -1 since the Jacobi identity [[ec-a,ea],ed]+[[ea,ed],ec-a]+[[ed,ec-a],ea]=0 reduces to f(c-a,a)f(c,d)+f(d,c-a)f(b,a)=0.
IfA=a∧b, B=a∧(c-a)∧d, C=c∧d, and D=a∧(d-a)∧c (or D=(a-d)∧d∧b), with a+b=c+d, then the signs are f(d,b-d), f(a,c-a), -f(a,d-a) (or -f(a-d,b)), and f(c,b-c) (or f(a-d,d)) with product -1 by the Jacobi identity on ea,ed-a,eb-d (or ed,ea-d,ec-a).
That covers all cases.



---

*Source: 140537-2013-01-10.xml*