# $W$-graphs

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\langle q\rangle$ 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 $T_s$ of $H$ associated with an element $s\in S$ on a basis element $v$ is given by

$$
v*T_s = \cases{
    (-q^{-1})*v & if $s$ is in the descent set of $v$,\\
    q*v + \sum' (m*u)&if $s$ is not in the descent set of $v$,\\}
$$

where $\sum'$ 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\in S$ act on the set of elementary roots (see [[Brink, 1998](../../references.md#cite-brink98)]).

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\in \{1, \dots, r\}$ and $j\in \{1, \dots, 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, \dots,r\}$ (corresponding to words in $S$).

## `SetVerbose("WGraph", v): MonStgElt, RngIntElt`

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)]];`

## `Mij2EltRootTable(seq): SeqEnum -> SeqEnum[SeqEnum[RngIntElt]]`

Return the elementary root action table for the Coxeter group defined by the given mij-sequence.

## `Name2Mij(name): MonStgElt -> SeqEnum`

The mij-sequence of the Coxeter groups of type name.

## `Example: mijseq (ex-320506)`

```magma
> 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

```

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\in 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) \mapsto sv$ from $S \times P$ to $P$ such that the action of $H$ on GSM(P) satisfies the following rules (for all $s \in S$ and $v \in P$):

$$
v*T_s = \cases{
  sv                   &if $sv > v$,\\
  sv + (q-q^{-1})*v    &if $sv < v$,\\
  -q^{-1}*v            &if $sv = v$ and $s\in D(v)$,\\
  q*v + q*\langle\hbox{earlier}\rangle &if $sv = v$ and $s \in A(v)$,\\}
$$

where $\langle$earlier$\rangle$ denotes a linear combination of $\{u \in P \mid u < v\}$ with coefficients that are polynomials in $q$. For each $s \in A(v)$ either $sv = v$ or $sv > v$, and for each $s \in 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,\dots,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 \in A(v)$) it is not proved that the polynomial coefficients of $\{u \in P \mid 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) \mapsto sv$ from $S \times 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$).

## `Partition2WGtable(pi): SeqEnum -> SeqEnum, GrpFPCox`

Returns the $W$-graph table and the Weyl group for the partition `pi`, where `pi` is a nonincreasing sequence $[a_1,a_2,\dots,a_k]$ 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 $A_n$, where $n+1 = \sum a_i$.

## `WGtable2WG(table): SeqEnum -> GrphUnd`

Convert a $W$-graph table to a $W$-graph.

## `TestWG(W, wg): GrpFPCox, GrphUnd -> .`

## `TestWG(W, wg): GrpFPCox, GrphDir -> .`

## `TestWG(tp, wg): MonStgElt, GrphDir -> .`

## `TestWG(tp, wg): MonStgElt, GrphDir -> .`

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,

## `Example: Specht Wgraph (ex-8afb5c)`

```magma
> SetVerbose("WGraph",1);
> wtable, W :=Partition2WGtable([4,4,3,1]);
> wg := WGtable2WG(wtable);
> TestWG(W,wg);

```

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\in W$, let $P$ be the set $\{x\in W \mid \hbox{length}(wx^{-1}) = \hbox{length}(w) - \hbox{length}(x)\}$, considered as a poset under the Bruhat order on $W$. Given also a subset $J$ of $\{t\in S \mid \hbox{length}(wt) > \hbox{length}(w)\}$, for each $x\in P$ we define $D(x)$ to be union of $\{s\in S \mid \hbox{length}(sx) < \hbox{length}(x)\}$ and $\{s \in S \mid sx = xt \hbox{ for some } t \in 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 $A_n$, 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 \in 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 $W_K$ (where the set $J$ may be taken to be either $K$ or the empty set).

## `WGelement2WGtable(g, K): GrpFPCoxElt, SetEnum -> SeqEnum, SeqEnum`

Returns the $W$-graph table and $W$-graph ideal of a $W$-graph determining element $g$, subset $K$.

## `Example: B5Wgraph (ex-0bb421)`

```magma
> 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

```

## `GetCells(wg): GrphUnd -> SeqEnum`

## `GetCells(wg): GrphDir -> SeqEnum`

Return the cells of the $W$-graph.

## `InduceWG(W, wg, seq): GrpFPCox, GrphUnd, SeqEnum -> GrphUnd`

## `InduceWG(W, wg, seq): GrpFPCox, GrphDir, SeqEnum -> GrphDir`

Induce a $W$-graph from a standard parabolic subgroup.

## `InduceWGtable(J, table, W): SeqEnum, SeqEnum, GrpFPCox -> SeqEnum[SeqEnum[RngIntElt]]`

Returns the table of the $W$-graph induced from the table of a parabolic subgroup defined by $J$.

## `IsWGsymmetric(dwg): GrphDir -> BoolElt, GrphDir`

Test a $W$-graph for symmetry. If the graph is symmetric the second return value is the undirected version of the $W$-graph.

## `MakeDirected(uwg): GrphUnd -> GrphDir`

Convert an undirected $W$-graph to a directed $W$-graph.

## `TestHeckeRep(W, r): GrpFPCox, SeqEnum -> .`

Tests whether the matrices in r satisfy the defining relations of the Hecke algebra of the Coxeter group $W$.

## `WG2GroupRep(wg): GrphUnd -> SeqEnum`

## `WG2GroupRep(wg): GrphDir -> SeqEnum`

The matrix representation of a $W$-graph.

## `WG2HeckeRep(W, wg): GrpFPCox, GrphUnd -> SeqEnum`

## `WG2HeckeRep(W, wg): GrpFPCox, GrphDir -> SeqEnum`

Returns a sequence of sparse matrices that satisfy the defining relations of the Hecke algebra.

## `WGidealgens2WGtable(dgens, K): SeqEnum, SetEnum -> SeqEnum[SeqEnum[RngIntElt]], SetIndx`

Returns the $W$-graph table and $W$-graph ideal of a $W$-graph determining generators dgens and subset $K$.

## `Example: Wgraph Ideal (ex-8bb5d1)`

In type $E_6$ we start with a rank 3 standard parabolic subgroup. The set of minimal coset representatives is a (single-generator) $W$-graph ideal, corresponding to the representation induced from the trivial representation of the parabolic. We compute the $W$-graph and find the cells. The bottom cell is necessarily an ideal in the weak order. It turns out that 3 elements are required to generate it; we can use them to test the function `WGidealgens2WGtable`.

```magma
> 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

```

## `WriteWG(file, uwg): MonStgElt, GrphUnd -> .`

## `WriteWG(file, dwg): MonStgElt, GrphDir -> .`

Writes the $W$-graph to a file.