Rectagraphs from root systems

Lenny Chastkofsky proposes the following construction:

Given a root system Φ with collection of positive roots Φ⁺, and a target vector u in the span of Φ, consider all subsets X₁,...,X_n of Φ⁺ with the property that the elements of X_i sum to u (for each i). Join X_i and X_j when their symmetric difference has size 3. This gives a bipartite graph Γ.

If Φ has simply laced diagram, and Γ is not empty, then Γ is a rectagraph (that is, Γ is connected and any two vertices have 0 or 2 common neighbours).

Proof of connectedness.
Note that the roots are precisely the vectors of squared norm 2 in the lattice spanned by Φ and that for two roots r, s their sum r+s is a root when (r,s) = –1 while the difference r–s is a root 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 is positive. 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. QED

Proof of (0,2) property.
Two sets A and B of sizes m+2 and m have 0 or 2 common neighbours: Put Z = A ∩ B. 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 is a root, precisely two of the inner products (a,b),(a,c),(b,c) are –1 (and the third is 0).
Two sets A and B of the same size have 0 or 2 common neighbours: If their symmetric difference 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 and Z is their intersection, so that A = Z ∪ {a+b,c} and B = Z ∪ {a,b+c}, then the common neighbours are (i) Z ∪ {a,b,c} if b ∉ Z and Z\{b} ∪ {a+b,b+c} otherwise, and (ii) Z ∪ {a+b+c} if a+b+c ∉ Z and Z\{a+b+c} ∪ {a,a+b,b+c,c} otherwise. QED

Choice of target vector - dot action of W

The map sending each set of positive roots to its complement induces an isomorphism from the graph Γ(u) defined by the target vector u to the graph Γ(2ρ–u) where 2ρ is the sum of the positive roots.

Let w be an element of the Weyl group W, and let A be the set of positive roots mapped to negative ones by w. The graph Γ(u) is mapped isomorphically onto the graph Γ(w(u–α)), where α = Σ A, by the map that sends each set X of positive roots to w(X\A) ∪ –w(A\X), that is, to the union of w(X) and w(–A) 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ρ = ρ + wα, so ρ – w(u–α) = wμ.)
It follows that we may choose u = ρ – μ where μ is a dominant weight.

The number of vertices

Let ρ be half the sum of the positive roots, and let μ be a dominant weight. The number of vertices of the graph Γ defined by the target vector u = ρ – μ equals the multiplicity of the weight μ in the module V_ρ.

Proof.
This is Lemma 5.9 in Bertram Kostant, Lie algebra cohomology and the generalized Borel-Weil theorem, Ann. Math. 74 (1961) 329-387.
Or, from Weyl's character formula: the formal character of V_ρ equals A_2ρ/A_ρ = e(–ρ) Π_α(e(α)+1) where α runs over Φ⁺, so that the multiplicity of μ equals the number of ways to write ρ + μ as sum of positive roots. QED

Now Freudenthal's formula gives a straightforward way to compute the number of vertices.

The valency

The valency of the graph Γ(u) is (u,2ρ–u)/2. When u is written on the basis of fundamental roots, this equals Σ u_i – Σ u_i² + Σ_e u_iu_j, where the last sum is over all edges e = ij in the Coxeter diagram.

Proof.
Let A be a vertex, and B = Φ⁺\A its complement. Compute (Σ A, Σ B). If a ∈ A and b ∈ B with (a,b) ≠ 0, then either (a,b) = –1, and then (a+b,b) = (a,a+b) = 1 so that the contribution of pairs in a,b,a+b to (Σ A, Σ B) vanishes, or (a,b) = 1, and, say, a = b + c for some c ∈ Φ⁺. In the latter case (b,c) = –1, and either c ∈ A, again with vanishing contribution from pairs in a,b,c, or c ∈ B, in which case a,b,c contribute (a,b) + (a,c) = 2. So, we only find a nonzero contribution (of 2) for each neighbour A\{a} ∪ {b,c} of A (or neighbour B\{b,c} ∪ {a} of B).
On the basis of fundamental roots inner products are given by the Cartan matrix, and (u,u)/2 = Σ u_i² – Σ_e u_iu_j, and (u,ρ) = Σ u_i. QED

Valency bound

Assume (as we may) that u is chosen such that u = ρ – μ where μ is a dominant weight. Then the valency of Γ(u) is at least Σu/2, with equality if and only if u = ρ.

Proof.
We have been expressing u in root coordinates (on the basis consisting of the fundamental roots), but ρ, and the fact that μ is a dominant weight, are better expressed in terms of weight coordinates (on the basis consisting of the fundamental weights). Conversion is done via the Cartan matrix C. In weight coordinates u becomes Cu, and ρ = 1 and we find that Cu ≤ 1. Now the valency is Σu – u'Cu/2, and the inequality just found implies u'Cu ≤ Σu, so that we find that the valency of Γ(u) is at least Σu/2, with equality if and only if u = ρ. QED

Direct products

Let us write things like Γ(E₆,112321) for the graph with target vector 112321 on the root system E₆.

If the Coxeter diagram is disconnected (or the support of u is), then the corresponding graph is the direct product of the graphs for the components. For example, Γ(D₈,22320111) is the direct product Γ(D₄,2232) × Γ(A₃,111) (where that latter factor is just K₂ × K₂).

If the target vector contains a 1 on a nonterminal position p, 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 p, preserving a copy of p in each component. For example, Γ(A₇,1221221) is the direct product Γ(A₄,1221) × Γ(A₄,1221). And Γ(D₅,11121) is the direct product Γ(A₂,11) × Γ(A₂,11) × Γ(A₃,121). (And Γ(A₂,11) is a single edge K₂, and Γ(A₃,121) is a 4-gon, so this product is a 4-cube.)

Proof.
The isomorphism is clear.

In particular, Γ(A_n+1,11...1) is the n-cube.

Example: A₄

Take the root system of type A₄, with the 10 positive roots 0001,0010,0100,1000,0011,0110,1100,0111,1110,1111. Take target vector 1221. In order to save space, write the positive roots as a,b,c,d,ab,bc,cd,abc,bcd,abcd. There are 14 ways to write the target vector as sum of positive roots: abcd+bc, abcd+b+c, bcd+abc, bcd+bc+a, bcd+ab+c, bcd+a+b+c, abc+cd+b, abc+bc+d, abc+b+c+d, ab+bc+cd, ab+bc+c+d, ab+cd+b+c, bc+cd+a+b, bc+a+b+c+d. (With 2,6,5,1 sums of 2,3,4,5 terms, respectively.) The graph Γ is the rectagraph on 14 vertices: the nonincidence graph of the points and lines of the Fano plane PG(2,2).

For the target vector 2222 we obtain the same graph, this time on the 14 sums abcd+abc+d, abcd+bcd+a, abcd+ab+cd, abcd+a+bc+d, abcd+ab+c+d, abcd+cd+a+b, abcd+a+b+c+d, abc+bcd+a+d, abc+ab+cd+d, abc+cd+a+b+d, bcd+ab+cd+a, bcd+ab+a+c+d, ab+bc+cd+a+d, ab+cd+a+b+c+d. (With 3,6,4,1 sums of 3,4,5,6 terms, respectively.) The combinatorics is rather different, but the graph is the same.

In this example ρ = 2332 and u = 1221, 2222 so that μ = ρ - u = 1111, 0110, respectively. And both belong to the same W-orbit, since both are roots.

In the first case we have u = 1,2,2,1 with valency 6–10+8 = 4. In the second case we have u = 2,2,2,2 with valency 8–16+12 = 4.

Nonexample: C₃

Take the root system of type C₃ with the 9 positive roots 100, 010, 001, 110, 011, 111, 021, 121, 221 and take target vector 121. We find the six vertices 121, 100+021, 010+111, 110+011, 100+010+011, 010+001+110 and Γ is not a (0,2)-graph. (It is K_3,3 minus an edge.)

Small rectagraphs

Since we elsewhere have a classification of all (0,2)-graphs of valency at most 8, it is natural to check which of those are found here. First of all, the hypercube of valency k is found using the target vector 111...1 of length k+1 (for A_k+1, say). Apart from the hypercubes we have

valency #vertices diagram target vector rectagraph

4 14 A4 1221 4.1

5 24 A4 2332 5.2

5 28 A5 11221 5.3

6 40 D4 2232 6.7

6 48 A5 12221 6.10

6 48 A7 1102332 6.11

6 56 A6 111221 6.12

7 64 D4 3353 7.22

7 80 A5 12332 7.33

7 80 D7 2232011 7.34

7 96 A6 112221 7.37

7 96 D6 223111 7.38

7 112 A7 1111221 7.39

8 128 D7 3353011 8.77

8 132 D5 22321 8.89

8 132 A5 23332 8.90

8 160 D8 22320111 8.95

8 160 A6 112332 8.97

8 164 A6 122221 8.98

8 192 D7 2231111 8.100

8 192 A7 1112221 8.101

8 196 A7 1221221 8.102

8 224 A8 11111221 8.103

valency	#vertices	diagram	target vector	rectagraph
4	14	A4	1221	4.1
5	24	A4	2332	5.2
5	28	A5	11221	5.3
6	40	D4	2232	6.7
6	48	A5	12221	6.10
6	48	A7	1102332	6.11
6	56	A6	111221	6.12
7	64	D4	3353	7.22
7	80	A5	12332	7.33
7	80	D7	2232011	7.34
7	96	A6	112221	7.37
7	96	D6	223111	7.38
7	112	A7	1111221	7.39
8	128	D7	3353011	8.77
8	132	D5	22321	8.89
8	132	A5	23332	8.90
8	160	D8	22320111	8.95
8	160	A6	112332	8.97
8	164	A6	122221	8.98
8	192	D7	2231111	8.100
8	192	A7	1112221	8.101
8	196	A7	1221221	8.102
8	224	A8	11111221	8.103

(For the numbering of fundamental roots, see the diagrams below.)

The above list is complete: no rectagraphs of valency at most 8 other than hypercubes and the above ones arise from this construction.

(This can be seen by the valency bound. First suppose that the graph is not a direct product, so that u does not have interior coefficients 0 or 1. Then the valency bound shows that it suffices to look at diagrams of rank at most 8. Do so. Then add the direct products of smaller examples.)

I do not know whether it is possible to recognize the rectagraphs that arise from this construction. But all of these graphs are signable.

Signable (0,2)-graphs

A (0,2)-graph is called signable if it is possible to assign signs +1/–1 to the edges in such a way that the product of the four edges of a quadrangle is always –1. Equivalently, a (0,2)-graph is signable if it has a 2-cover without quadrangles. The edges of the (0,2)-graphs obtained from simply laced root systems have signs given by a trivial cohomology coboundary operator d (see the next page), and checking the cases found in the proof of the (0,2)-property we find that the graph is signable.

The signable bipartite (0,2)-graphs of valency at most 8 are the hypercubes (0.1, 1.1, 2.1, 3.1, 4.2, 5.4, 6.13, 7.40, 8.104) and the graphs 4.1, 5.2-3, 6.7-8, 6.10-12, 7.2, 7.10, 7.18-19, 7.22, 7.24-28, 7.33-35, 7.37-39, 8.2, 8.6, 8.11, 8.13, 8.30-32, 8.36, 8.38, 8.47-62, 8.71, 8.76-90, 8.95-98, 8.100-103.

The n-cube, with n at least 2, has a unique 2-cover without quadrangles (BCN, p. 267). The Gewirtz graph is not signable and hence has no 2-cover without quadrangles (BCN, p. 372).

Data

Some numerical info. Diagram, target vector, number of vertices v, graph valency k (each rectagraph is regular).

A1
0: v=1, k=0

A2
11: v=2, k=1

A3
111: v=4, k=2

A4
1111: v=8, k=3
1221: v=14, k=4
2332: v=24, k=5

A5
11111: v=16, k=4
11221: v=28, k=5
12221: v=48, k=6
12332: v=80, k=7
23332: v=132, k=8

A6
111111: v=32, k=5
111221: v=56, k=6
112221: v=96, k=7
112332: v=160, k=8
122221: v=164, k=8
123321: v=266, k=9
122332: v=272, k=9
134431: v=424, k=10
123332: v=436, k=10
134432: v=688, k=11
233332: v=712, k=11
234432: v=1112, k=12
245542: v=1720, k=13
356653: v=2640, k=14

A7
1111111: v=64, k=6
1111221: v=112, k=7
1112221: v=192, k=8
1221221: v=196, k=8
1112332: v=320, k=9
1122221: v=328, k=9
1123321: v=532, k=10
1122332: v=544, k=10
1222221: v=560, k=10
1134431: v=848, k=11
1123332: v=872, k=11
1223321: v=904, k=11
1222332: v=928, k=11
1134432: v=1376, k=12
1233321: v=1440, k=12
1223332: v=1480, k=12
2332332: v=1536, k=12
1234431: v=2256, k=13
1233332: v=2348, k=13
1344431: v=3504, k=14
1234432: v=3640, k=14
1344332: v=3664, k=14
2333332: v=3824, k=14

and also v=5584, 5632, 5904, 8576, 9040, 12960, 13712, 20640, 20676, 30960, 46144.

A8
11111111: v=128, k=7
11111221: v=224, k=8
11023332: v=264, k=9
11112221: v=384, k=9
11221221: v=392, k=9
11112332: v=640, k=10
11122221: v=656, k=10
12212221: v=672, k=10
11123321: v=1064, k=11
11122332: v=1088, k=11
11222221: v=1120, k=11

and also v=1696, 1744, 1808, 1856, 1912, 2752, 2880, 2960, 3072, 3084, 3168, 4512, 4696, 4888, 5048, 5104, 5248, 7008, 7280, 7328, 7648, 7744, 7968, 8352, 11168, 11264, 11918, 12064, 12336, 12608, 17152, 18136, 18404, 18896, 19324, 19432, 19616, 20520, 25920, 27792, 28316, 29528, 29800, 31320, 31584, 42440, 44416, 44688, 45368, 47792, 63144, 66804, 67104, 67728, 68416, 72224, 72656, 93360, 99760, 100368, 101528, 108032, 108288, 109408, 149664, 151120, 159456, 161704, 219360, 221728, 237408, 240320, 241312, 323600, 351168, 352472, 357600, 512184, 519968, 740880, 752464, 765120, 1084320, 1102824, 1583360, 2265200, 3230080.

    O 2
    |
O---O---O
1   3   4

D4
1111: v=8, k=3
1121: v=14, k=4
1232: v=24, k=5
2232: v=40, k=6
3353: v=64, k=7

    O 2
    |
O---O---O---O
1   3   4   5

D5
11111: v=16, k=4
11211: v=28, k=5
11221: v=48, k=6
11332: v=80, k=7
12332: v=132, k=8
22431: v=210, k=9
22332: v=216, k=9
33531: v=328, k=10
22432: v=340, k=10
23542: v=528, k=11
33542: v=808, k=12
44752: v=1216, k=13
33653: v=1224, k=13
44753: v=1824, k=14
55974: v=2688, k=15

    O 2
    |
O---O---O---O---O
1   3   4   5   6

D6
111111: v=32, k=5
111221: v=56, k=6
112211: v=96, k=7
123211: v=160, k=8
112221: v=164, k=8
223211: v=264, k=9
113321: v=266, k=9
112332: v=272, k=9
224311: v=420, k=10
113332: v=436, k=10
223221: v=448, k=10
335311: v=656, k=11
124431: v=688, k=11
123332: v=712, k=11
124432: v=1112, k=12
223332: v=1160, k=12
235421: v=1712, k=13
135542: v=1720, k=13
224431: v=1724, k=13
224332: v=1804, k=13

and also v=2608, 2632, 2768, 2784, 3904, 3984, 4208, 5934, 6352, 8744, 8760, 9420, 9520, 9528, 12792, 13840, 14044, 18496, 20528, 20800, 29744, 30244, 42688, 42816, 43616, 61040, 62496, 86400, 88736, 89040, 125688, 176320, 177192, 247392, 343680.

    O 2
    |
O---O---O---O---O---O
1   3   4   5   6   7

D7
1111111: v=64, k=6
1111221: v=112, k=7
3353011: v=128, k=8
1112221: v=192, k=8
1121221: v=196, k=8
1112332: v=320, k=9
2231221: v=336, k=9
1133211: v=532, k=10
1232211: v=544, k=10
1122221: v=560, k=10
2243111: v=840, k=11
1233211: v=872, k=11
2232211: v=896, k=11
1123321: v=904, k=11
1122332: v=928, k=11
3353111: v=1312, k=12
1244311: v=1376, k=12
2233211: v=1424, k=12
1133321: v=1440, k=12
1123332: v=1480, k=12
2232221: v=1528, k=12
1232332: v=1536, k=12
2243211: v=2224, k=13
1134431: v=2256, k=13
1133332: v=2348, k=13
2233221: v=2416, k=13
2232332: v=2528, k=13

and also v=3424, 3440, 3448, 3640, 3664, 3768, 3824, ..., 194010624.

    O 2
    |
O---O---O---O---O---O
1   3   4   5   6   7

D8
11111111: v=128, k=7
11111221: v=224, k=8
33530111: v=256, k=9
11112221: v=384, k=9
11211221: v=392, k=9
22332011: v=432, k=10
11112332: v=640, k=10
11212221: v=672, k=10
22432011: v=680, k=11
11222211: v=1120, k=11

and also v=1056, 1064, 1088, 1152, 1616, ..., 458377052160.

        O 2
        |
O---O---O---O---O
1   3   4   5   6   

E6
111111: v=32, k=5
111211: v=56, k=6
111221: v=96, k=7
111332: v=160, k=8
112221: v=164, k=8
121332: v=264, k=9
112321: v=266, k=9
113431: v=424, k=10
112332: v=436, k=10
213431: v=688, k=11
122332: v=712, k=11
123431: v=1072, k=12
223421: v=1112, k=12
223332: v=1160, k=12

and also v=1644, ..., 13697920.

        O 2
        |
O---O---O---O---O---O
1   3   4   5   6   7   

E7
1111111: v=64, k=6
1111221: v=112, k=7
1112211: v=192, k=8
1213211: v=320, k=9
1113321: v=532, k=10
1112332: v=544, k=10
1122221: v=560, k=10
1134311: v=848, k=11
1113332: v=872, k=11
1123221: v=904, k=11
1122332: v=928, k=11
1123321: v=1440, k=12

and also v=1376, 1424, 1480, 2144, ..., 76578485178240.

        O 2
        |
O---O---O---O---O---O---O
1   3   4   5   6   7   8   

E8
11111111: v=128, k=7
11111221: v=224, k=8
11112221: v=384, k=9
11121221: v=392, k=9
22332011: v=432, k=10
11112332: v=640, k=10
11221221: v=672, k=10
22342011: v=680, k=11

and also v=1056, 1064, 1088, 1120, 1616, ..., 235377394371444230194469748736.

Cohomology

Let k be any field, and let C_i = ⋀ⁱ Φ⁺ be the i-th exterior power of the k-vectorspace with basis Φ⁺. Consider the cochain complex ... ← C_i+1 ← C_i ← ... with coboundary operator d defined by

d_i(a₁ ∧ ... ∧ a_i) = Σ_j Σ_{a_j=b+c} (–1)^j f(b,c) a₁ ∧ ... ∧ a_j–1 ∧ b ∧ c ∧ a_j+1 ∧ ... ∧ a_i,

where f(b,c)=–f(c,b) and the sum is over unordered pairs of positive roots {b,c} with b+c = a_j. One checks that indeed d_i+1d_i = 0 provided that f(b,c)f(b+c,d) = f(b,c+d)f(c,d). (For a simply laced root system one can find such an f that only takes the values 1 or –1, e.g. by borrowing it from the corresponding Lie algebra: [e_r,e_s] = f(r,s)e_r+s.)

This complex is the direct sum of such complexes where the basis vectors are restricted to (the exterior products of the elements of) the vertices of Γ(u). For each u we can ask for the cohomology of this complex. Some data are given on the next page.

Reference

[BCN] Brouwer, Cohen & Neumaier, Distance-regular graphs, Springer, 1989.