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 X1,...,Xn of Φ+ with the property that the elements of Xi sum to u (for each i). Join Xi and Xj 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/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 Σ ui – Σ ui2 + Σe uiuj, 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 = Σ ui2 – Σe uiuj, and (u,ρ) = Σ ui. 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 Cu1. Now the valency is Σuu'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 Γ(E6,112321) for the graph with target vector 112321 on the root system E6.

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, Γ(D8,22320111) is the direct product Γ(D4,2232) × Γ(A3,111) (where that latter factor is just K2 × K2).

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, Γ(A7,1221221) is the direct product Γ(A4,1221) × Γ(A4,1221). And Γ(D5,11121) is the direct product Γ(A2,11) × Γ(A2,11) × Γ(A3,121). (And Γ(A2,11) is a single edge K2, and Γ(A3,121) is a 4-gon, so this product is a 4-cube.)

Proof.
The isomorphism is clear.

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

Example: A4

Take the root system of type A4, 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: C3

Take the root system of type C3 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 K3,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 Ak+1, say). Apart from the hypercubes we have

valency#verticesdiagram target vectorrectagraph
414A412214.1
524A423325.2
528A5112215.3
640D422326.7
648A5122216.10
648A711023326.11
656A61112216.12
764D433537.22
780A5123327.33
780D722320117.34
796A61122217.37
796D62231117.38
7112A711112217.39
8128D733530118.77
8132D5223218.89
8132A5233328.90
8160D8223201118.95
8160A61123328.97
8164A61222218.98
8192D722311118.100
8192A711122218.101
8196A712212218.102
8224A8111112218.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 Ci = ⋀i Φ+ be the i-th exterior power of the k-vectorspace with basis Φ+. Consider the cochain complex ... ← Ci+1 ← Ci ← ... with coboundary operator d defined by
di(a1 ∧ ... ∧ ai) = Σj Σaj=b+c (–1)j f(b,c) a1 ∧ ... ∧ aj–1bcaj+1 ∧ ... ∧ ai,
where f(b,c)=–f(c,b) and the sum is over unordered pairs of positive roots {b,c} with b+c = aj. One checks that indeed di+1di = 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: [er,es] = f(r,s)er+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.