Given a Coxeter system (W, S), a W-graph is a (directed or undirected) graph with vertex labels and edge weights. The label attached to a vertex v is a subset of S (called the descent set of v) and the edge weights are scalars (usually integers).
A W-graph must determine a representation of the Hecke algebra H = H< q > of the associated Coxeter system. The vertices of the W-graph can be identified with basis elements of the representation space, and by the conventions adopted here the action of the generator Ts of H associated with an element s∈S on a basis element v is given by
v * Ts = cases(
( - q - 1) * v & if s is in the descent set of v,
q * v + ∑' (m * u)&if s is not in the descent set of v,
)
where ∑' indicates the sum over all edges with terminal vertex equal to v for which s is in the descent set of the initial vertex u, and m is the weight of the edge.
For the Coxeter group calculations involved in these functions we need to know how the generators s∈S act on the set of elementary roots (see [Bri98]).
Magma has a function ReflectionTable that provides the necessary information. Specifically, let W be a finitely presented Coxeter group with N elementary roots (numbered from 1 to N) and r simple reflections (numbered 1 to r). If we define
{eltroots:=ReflectionTable(W);}
then for i∈{1, ..., r} and j∈{1, ..., N}, eltroots[i,j] = k if the i-th simple reflection takes the j-th elementary root to the k-th elementary root, or to a non-elementary root if k = 0, or to a negative root if k < 0. (This last alternative occurs if and only if j = i and k = - i.) Knowing the table eltroots makes it quick and easy to do symbolic computation with elements of W, represented as sequences of integers in {1, ..., r} (corresponding to words in S).
The functions defined in this section
are mainly concerned with W-graph posets. The
motivating example for this concept is the set of all standard
tableaux corresponding to a given partition, the partial order
being dominance. By definition, if P is a W-graph poset then P
must be in one-to-one correspondence with a basis for an H-module
V (where H is the Hecke algebra associated with the given
Coxeter system). In the standard tableaux example, this module
is the Specht module; hence in the general case we refer to the
module V as GSM(P) (for generalized Specht module). For each
v∈P the set S must be the disjoint union of two sets A(v) and
D(v), the ascents and descents of v. There must be a function
(s, v) |-> sv from S x P to P such that the action of H on
GSM(P) satisfies the following rules (for all s ∈S and v ∈P):
v * Ts = cases(
sv &if sv > v,
sv + (q - q - 1) * v &if sv < v,
- q - 1 * v &if sv = v and s∈D(v),
q * v + q * < earlier > &if sv = v and s ∈A(v),
)
where < earlier > denotes a linear combination of {u ∈P | u < v} with coefficients that are polynomials in q. For each s ∈A(v) either sv = v or sv > v, and for each s ∈D(v) either sv < v or sv = v. This (admittedly strange) definition is motivated by the fact that Specht modules satisfy it. If v is a standard tableau corresponding to a partition of n then a number i in {1, ..., n - 1} is an ascent of v if i + 1 is in a later column of t than i, and is a descent of v if i + 1 is in a lower row of t than i. The fact that Specht modules satisfy the formulas above is proved in the literature (e.g. Mathas' book), except that in the "weak ascent" case (sv = v and s ∈A(v)) it is not proved that the polynomial coefficients of {u ∈P | u < v} are all divisible by q. The fact that they are is a theorem of V. M. Nguyen (PhD thesis, University of Sydney, 2010). It turns out that there is an algorithm by which a W-graph may be constructed from a W-graph poset, the W-graph being uniquely determined by the function (s, v) |-> sv from S x P to P and the descent/ascent sets. The polynomial coefficients in the weak ascent case are not required. Of course the H-module determined by the resulting W-graph is isomorphic to GSM(P). which should cause the word true to be printed 66 times (as the defining relations of the Hecke algebra are checked).
Given a Coxeter system (W, S) and an element w∈W, let P be the set {x∈W | length(wx - 1) = length(w) - length(x)}, considered as a poset under the Bruhat order on W. Given also a subset J of {t∈S | length(wt) > length(w)}, for each x∈P we define D(x) to be union of {s∈S | length(sx) < length(x)} and {s ∈S | sx = xt for some t ∈J }. If P is now a W-graph poset with the sets D(x) as the descent sets then we say that w is a W-graph determining element relative to J.
For example, suppose that (W, S) is of type An, and given a partition of n + 1 let t be the (unique) standard tableau whose column group is generated by a subset of S. Let w be the maximal length element such that the tableau wt is standard. Then w is a W-graph determining element with respect to the set J consisting of those s ∈S that are in the column stabilizer of t.
Other examples (for any Coxeter system with finite W) are provided by the distinguished left coset representatives of maximal length for standard parabolic subgroups WK (where the set J may be taken to be either K or the empty set).
Set the verbose printing to level v for all W-graph related functions. A level of 2 means that informative messages and progress information will be printed durng a computation.
Sometimes it is convenient to use `mij-sequences' to specify Coxeter groups. The mij-sequence consists of the on or below diagonal entries in the Coxeter matrix. Thus if seq is the mij-sequence and M the Coxeter matrix then
M := SymmetricMatrix(seq);
and
seq := &cat[[M[i,j] : j in [1..i]] : i in [1..Rank(W)]];
Return the elementary root action table for the Coxeter group defined by the given mij-sequence.
The mij-sequence of the Coxeter groups of type name.
> e6:=[1,3,1,2,3,1,2,3,2,1,2,2,2,3,1,2,2,3,2,2,1]; > E6 := CoxeterGroup(GrpFPCox, SymmetricMatrix(e6) ); > ReflectionTable(E6) eq Mij2EltRootTable(e6); true
Returns the W-graph table and the Weyl group for the partition pi, where pi is a nonincreasing sequence [a1, a2, ..., ak] of positive integers. It returns the table corresponding to the W-graph poset of standard tableaux of the given shape and the finitely presented Coxeter group of type An, where n + 1 = ∑ai.
Convert a W-graph table to a W-graph.
This procedure can be used to test whether a presumed undirected or directed W-graph is indeed a W-graph, where W is a finitely presented Coxeter group of type tp. Two input values are required: the Coxeter group W (or its type) and the W-graph. When applied to the W-graph produced by the WGtable2WG function, this tests whether the input table did genuinely correspond to a W-graph poset.For example,
> SetVerbose("WGraph",1);
> wtable, W :=Partition2WGtable([4,4,3,1]);
> wg := WGtable2WG(wtable);
> TestWG(W,wg);
Returns the W-graph table and W-graph ideal of a W-graph determining element g, subset K.
> b5 := [1,4,1,2,3,1,2,2,3,1,2,2,2,3,1]; > b5mat := SymmetricMatrix(b5); > W := CoxeterGroup(GrpFPCox, b5mat ); > table, _ := WGelement2WGtable(W![5,4,3,2,1,2,3,4,5],); > wg := WGtable2WG(table); > TestWG(W,wg); true <1, 2> 4 true <2, 3> 3 true <3, 4> 3 true <4, 5> 3
Return the cells of the W-graph.
Induce a W-graph from a standard parabolic subgroup.
Returns the table of the W-graph induced from the table of a parabolic subgroup defined by J.
Test a W-graph for symmetry. If the graph is symmetric the second return value is the undirected version of the W-graph.
Convert an undirected W-graph to a directed W-graph.
Tests whether the matrices in r satisfy the defining relations of the Hecke algebra of the Coxeter group W.
The matrix representation of a W-graph.
Returns a sequence of sparse matrices that satisfy the defining relations of the Hecke algebra.
Returns the W-graph table and W-graph ideal of a W-graph determining generators dgens and subset K.
> mij:=[1,3,1,2,3,1,2,3,2,1,2,2,2,3,1,2,2,3,2,2,1];
> E6 := CoxeterGroup(GrpFPCox, SymmetricMatrix(mij) );
> J := {1,3,5};
> drs := Transversal(E6,J);
> ttt := WGidealgens2WGtable([drs[1398],drs[156],drs[99]],J);
> nwg := WGtable2WG(ttt);
> TestWG(E6,nwg);
true <1, 2> 3
true <2, 3> 3
true <2, 4> 3
true <4, 5> 3
true <3, 6> 3
Writes the W-graph to a file.