Given a root system Φ with collection of positive roots Φ^{+}, and a target vectoruin the span of Φ, consider all subsetsX_{1},...,X_{n}of Φ^{+}with the property that the elements ofX_{i}sum tou(for eachi). JoinX_{i}andX_{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

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.

**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.

**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}^{2} – Σ_{e}
*u*_{i}*u*_{j},
and (*u*,ρ) = Σ *u*_{i}. QED

**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 C*u*, and ρ = **1**
and we find that C*u* ≤ **1**.
Now the valency is Σ*u* – *u*'C*u*/2, and the inequality
just found implies *u*'C*u* ≤ Σ*u*, so that we find
that the valency of Γ(*u*) is at least Σ*u*/2,
with equality if and only if *u* = ρ. QED

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_{8},22320111)
is the direct product
Γ(D_{4},2232) × Γ(A_{3},111)
(where that latter factor is just K_{2} × K_{2}).

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_{7},1221221) is the direct product
Γ(A_{4},1221) × Γ(A_{4},1221).
And Γ(D_{5},11121) is the direct product
Γ(A_{2},11) × Γ(A_{2},11)
× Γ(A_{3},121).
(And Γ(A_{2},11) is a single edge K_{2},
and Γ(A_{3},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.

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.

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*.

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).

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=14and 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=11and 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=13and 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=13and 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=11and 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=12and 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=12and 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=11and also v=1056, 1064, 1088, 1120, 1616, ..., 235377394371444230194469748736.

whered_{i}(a_{1}∧ ... ∧a_{i}) = Σ_{j}Σ_{aj=b+c}(–1)^{j}f(b,c)a_{1}∧ ... ∧a_{j–1}∧b∧c∧a_{j+1}∧ ... ∧a_{i},

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.