W-graph ideals

Robert B. Howlett, Van Minh Nguyen

Abstract

We introduce a concept of a W-graph ideal in a Coxeter group. The main goal of this paper is to describe how to construct a W-graph from a given W-graph ideal. The principal application of this idea is in type A, where it provides an algorithm for the construction of W-graphs for Specht modules.

Introduction

In the study of representation theory, particularly for Coxeter groups and their associated Hecke algebras, W-graphs serve as fundamental combinatorial tools. A W-graph consists of a set of vertices with specific labels and edge weights that encode the action of the algebra on a vector space. While the Kazhdan-Lusztig (KL) construction has long been the standard for generating these graphs, its reliance on the computation of complex polynomials across the entire group makes it computationally prohibitive for large-scale applications.

This paper introduces the concept of a W-graph ideal, a framework that generalizes existing methods and provides a more efficient, targeted approach to constructing representations, specifically Specht modules in Type A.

The W-Graph Ideal Framework

The authors define a W-graph ideal within the context of the left weak order of a Coxeter group. An ideal is defined such that if an element is in the ideal, all its "suffixes" (in a specific algebraic sense) must also be contained within the ideal.

Algebraic Action and Classification

The construction relies on defining how Hecke algebra generators act on a basis indexed by the ideal. This action is categorized into four distinct types of moves:

  1. Strong Ascents: Where the length increases and the element remains in the ideal.
  2. Strong Descents: Where the length decreases and the element remains in the ideal.
  3. Weak Ascents: Where the length increases but the resulting element is outside the ideal.
  4. Weak Descents: Where the length decreases but the resulting element is outside the ideal.

The Recursive Construction Algorithm

The core contribution is a recursive algorithm (Theorem 7.3 and Corollary 7.4) that constructs a unique basis satisfying the W-graph requirements. Unlike the standard KL approach, which often requires traversing the dense Bruhat order of the entire group, this algorithm operates on the left weak order. This significantly narrows the search space and allows for the "targeted" construction of specific modules without decomposing the entire regular representation.

Theorem 7.6 proves that the resulting triple $(C, \mu, \tau)$ is indeed a valid W-graph. Furthermore, the authors establish polynomial degree bounds for the $q_{y,w}$ polynomials used in the recursion, ensuring that the algorithm eventually terminates.

Applications to Specht Modules in Type A

The most significant application of this theory is in Type A Coxeter groups (isomorphic to symmetric groups). The authors demonstrate a perfect correspondence between the combinatorial properties of Standard Tableaux and W-graph ideals.

By mapping the set of standard tableaux for a given partition to a W-graph ideal, the algorithm can directly construct W-graphs for Specht modules—the fundamental building blocks of symmetric group representations. The paper provides a concrete example of this by constructing the 21-dimensional Specht module for the partition (3, 3, 1).

Computational Verification and Generalization

The theoretical framework has been validated through implementation in the MAGMA computational algebra system. This implementation allowed the authors to verify results for complex partitions, such as (5, 5, 3, 3).

A key insight of this work is its role as a unifying theory. The authors show that both the original Kazhdan-Lusztig construction and Deodhar’s parabolic construction are specific, restricted instances of the broader W-graph ideal framework.

Conclusion and Future Work

W-graph ideals offer a powerful new path for representation theory, combining theoretical elegance with computational efficiency. While the current focus is on Type A and Specht modules, the framework is generalizable to any Coxeter group. Future research may extend these methods to study skew partitions and more general classes of representations, as well as further optimizing the algorithmic implementation for even larger-scale computations.

Summary updated

Abstract

We introduce a concept of a W-graph ideal in a Coxeter group. The main goal of this paper is to describe how to construct a W-graph from a given W-graph ideal. The principal application of this idea is in type A, where it provides an algorithm for the construction of W-graphs for Specht modules.
BibTeX
@article{howlett2012w,
  author = {Robert B. Howlett and Van Minh Nguyen},
  title = {{W-graph ideals}},
  journal = {Journal of Algebra},
  year = {2012},
  doi = {10.1016/j.jalgebra.2012.03.027},
}
Figure