`Coxeter`

### Cells and W-graphs

The program provides commands for the computation and printout of the
Kazhdan-Lusztig cells and the corresponding W-graphs, for finite groups. The
computation is possible for left-, right- and two-sided cells. One should
distinguish between the determination of the cells simply as subsets of
the groups, which in some cases can be effected without computing
*any* Kazhdan-Lusztig polynomials, and the determination of the
corresponding W-graph, which requires the determination of the mu-coefficients.

It is also possible to print out the set of cells as a poset; for finite
Weyl groups, it is known that the poset of left cells, say, is isomorphic
to the poset of primitive ideals with trivial infinitesimal character, in
the enveloping algebra of the corresponding semisimple Lie algebra.

The algorithm for left cells starts out by computing two partitions, the first
one, sometimes called "coplactic equivalence", being finer than the left
cell partition, and the second one, Vogan's "generalized tau-invariant"
partition, being coarser. Both can be computed by elementary means, in
terms of descent sets. Clearly if a class in the coarser partition is also
a single class in the finer one, then it has to be a left cell; in particular,
when the two partitions coincide --- as happens, for instance, in type A ---
we conclude immediately. If not, we have to refine the coarse cells which are
not single fine cells, by computing the necessary mu-coefficients.

The algorithm for one-sided cells is fairly satisfactory. The algorithm for
two-sided cells, on the other hand (which should be an easier problem), is
not, due to lack of knowledge on my part. Currently the partition is computed
by brute force, finding the full W-graph of the group. Clearly this needs more
work.

The three kinds of cells are determined also for the unequal parameter
situation; here, one has to determine directly the preorder relation
analogous to the one which comes from the W-graph in the equal-parameter
case, and find the corresponding equivalence classes. To this end, the program
uses the well-known Tarjan algorithm as explained to me by Bill Casselman;
this is also what is used in the equal-parameter case, when it is required
to find the order relation on the set of all left cells.

Back to the Coxeter home page.