Printer Friendly

Type A molecules are Kazhdan-Lusztig.

1 Introduction

Let (W, S) be a Coxeter system. A W-graph is a graph with additional structure that encodes a representation of the corresponding Iwahori-Hecke algebra. Kazhdan and Lusztig (1979) introduced such graphs for the regular representation, and showed that the strongly connected components (called "cells") also yield representations. Stembridge identified several common features of the Kazhdan- Lusztig graphs, namely, they are bipartite, (nearly) edge-symmetric, and their edge weights are non- negative integers (collectively he called these properties "admissibility"). He proceeded to describe, via four combinatorial rules, when an admissible graph is a W-graph (Stembridge (2008a)). One hopes that the characterization will allow one to construct the Kazhdan-Lusztig cells without having to compute Kazhdan- Lusztig polynomials (a notoriously difficult task). A piece of evidence suggesting that the definition of a general admissible W-cell approximates a Kazhdan-Lusztig cell is a more recent result of Stembridge that there are only finitely many admissible W-cells for each W (Stembridge (2012)).

There are no known examples of admissible [A.sub.n]-cells besides the Kazhdan- Lusztig cells (Stembridge experimentally checked it up to n = 9). A possible strategy of proof is as follows:

1. An [A.sub.n]-cell is a strongly connected directed graph. Consider the subgraphs which are connected via two-sided edges (of course these are strongly connected on their own, but a cell may contain several of them). The subgraphs satisfy combinatorial rules slightly weaker than those satisfied by a cell; a graph satisfying these rules is called a molecule. The first step is to show that any [A.sub.n]-molecule is Kazhdan-Lusztig, i.e. it appears in the Kazhdan-Lusztig graph.

2. It is known that a Kazhdan-Lusztig [A.sub.n]-cell is connected via two-sided edges, and these edges are well understood (they are called dual Knuth moves). The second step is to prove that no cell may have multiple molecules. The fact that no two Kazhdan-Lusztig [A.sub.n] molecules may be connected inside a cell has been experimentally checked for n [less than or equal to] 12 (Stembridge (2011)).

3. The last part is to prove that there can be only one [A.sub.n]-graph with a given underlying molecule. For Kazhdan-Lusztig molecules this has been checked for n [less than or equal to] 13 (Stembridge (2011)).

In this paper we complete the first part of the above program, namely, we prove that any [A.sub.n]-molecule is Kazhdan-Lusztig. Together with the above computations, this result implies that all [A.sub.n]-cells up to n = 12 are Kazhdan-Lusztig. The main ingredient of the proof is the axiomatization of graphs on tableaux generated by dual Knuth moves (Assaf (2008)). Five of the axioms follow easily from the molecules axioms, but the last one presents a challenge.

The paper is structured as follows. Section 2 introduces W-molecules. Section 3 discusses Assaf's dual equivalence graphs and relates them to molecules. The last section contains an outline of the proof of the main theorem that the simple part of a type A molecule is a dual equivalence graph.

2 Molecules

This section summarizes the required W-molecules terminology as described by Stembridge (2008a,b).

Let (W, S) be a simply-laced Coxeter system. A significant part of this section extends to multiply-laced types; see the above two papers. The papers are mostly concerned with W-graphs, i.e. graphs that encode certain representations of the corresponding Iwahori-Hecke algebra. It turns out that the simple (i.e. directed both ways) edges of these graphs are much easier to understand than other edges. For example, there is a very explicit description of them for the case of cells arising in the Kazhdan-Luztig W-graph (we will give it in Section 3.1). Thus we consider subgraphs connected by simple edges. These subgraphs are not W-graphs (i.e. they do not encode representations), but they satisfy certain combinatorial rules which are slightly weaker than Stembridge's W-graph rules. We begin this paper by formalizing the definitions and presenting the rules.

2.1 Definitions

An (admissible) S-labeled graph isatuple G = (V, m, [tau]), where V is a set (vertices), m: V x V [right arrow] [Z.sup.[greater than or equal to] 0], and [tau]: V [right arrow] [2.sup.S] such that

1. as a directed graph (with edges given by pairs of vertices with non-zero m value), G is bipartite,

2. if [tau](u) [subset] [tau](v) then m(u, v) = 0,

3. if [tau](u) and [tau](v) are incomparable, then m(u, v) = m(v, u).

The function [tau] is referred to as the [tau]-invariant.

By a simple edge we mean a pair of vertices ([v.sub.1], [v.sub.2]) such that neither m([v.sub.1], [v.sub.2]) nor m([v.sub.2], [v.sub.1]) are 0 (in the graphs that we consider both weights will be 1). By an arc [v.sub.1] [right arrow] [v.sub.2] we mean a pair of vertices ([v.sub.1], [v.sub.2]) such that m([v.sub.1], [v.sub.2]) [not equal to] 0, but m([v.sub.2], [v.sub.1]) = 0. Notice if u [right arrow] v is an arc, then [tau](u) [contains] [tau](v). If (u, v) is a simple edge then [tau](u) and [tau](v) are incomparable, and m(u, v) = m(v, u).

A simple edge (u, v) activates a bond i - j in the Coxeter graph if precisely one of [tau](u) and [tau](v) contains i, and precisely the other one contains j.

For distinct i, j [member of] S, a path u [right arrow] [v.sub.1] [right arrow] [v.sub.2] [right arrow] ... [right arrow] [v.sub.r-1] [right arrow] v in G is alternating of type (i, j) if

* i,j [member of] [tau](u) and i,j [not member of] [tau](v),

* i [member of] [tau]([v.sub.k]), j [not member of] [tau]([v.sub.k]) for odd k,

* i [not member of] [tau]([v.sub.k]), j [member of] [tau]([v.sub.k]) for even k.

Let [N.sup.r.sub.ij](G; u, v) denote the weighted count of such paths:


Definition 2.1 An S-labeled graph is called a molecular graph if it satisfies

(SR) If (u, v) is a simple edge then m(u, v) = m(v, u) = 1.

(CR) If u [member of] v is an edge, i.e. m(u, v) [not equal to] 0, then every i [member of] [tau](u)\[tau](v) is bonded to every j [member of] [tau](v)\[tau](u).

(BR) Suppose i - j is a bond in the Coxeter graph of (W, S). Any vertex u with i [member of] [tau](u) and j [not member of] [tau](u) is adjacent to precisely one edge which activates i - j.

(LPR2) For any i, j [member of] S for any u, v [member of] V with i, j [member of] [tau](u), i, j [not member of] [tau](v) and [tau](v)\[tau](u) [not equal to] [empty set], we have

[N.sup.2.sub.ij](G; u, v) = [N.sup.2.sub.ji](G; u, v).

(LPR3) Let k, i, j, l [member of] S be a copy of [A.sub.4] in the Coxeter graph: k - i - j - l. For any u, v [member of] V with i, j [member of] [tau](u), i, j [not member of] [tau](v), k, l [not member of] [tau](u), k, l [member of] [tau](v), we have

[N.sup.3.sub.ij](G; u, v) = [N.sup.3.sub.ji](G; u, v).

The rules are called, respectively, simplicity rule, compatibility rule, bonding rule, and local polygon rules.

Definition 2.2 A molecular graph is called a molecule if there is a path of simple edges between any pair ofvertices.

Example 2.3 It is easy to classify all the [S.sub.4] molecules. Because of admissibility, a vertex whose [tau]-invariant is [empty set] cannot be connected to any other vertex by a simple edge. Similarly for a vertex whose [tau]-invariant is {1,2,3}.

Suppose we have a vertex [v.sub.1] whose [tau]-invariant is {1}. By BR, it is connected by a simple edge to a vertex [v.sub.2] whose [tau]-invariant contains 2, but not 1. By CR, 3 [not member of] [tau]([v.sub.2]), and hence [tau]([v.sub.2]) = {2}. By BR, [v.sub.2] is connected by a simple edge to a vertex [v.sub.3] whose [tau]-invariant contains 3, but not 2. We already know [v.sub.3] [not equal to] [v.sub.1]. By BR, [tau]([v.sub.3]) = {3}. There are no other simple edges possible, and this is a complete molecule. The same analysis works for [v.sub.1] having [tau]-invariants of {3}, {1,2}, {2,3}.

Suppose we have a vertex v1 whose [tau]-invariant is {2}. By BR, it is connected by a simple edge to a vertex [v.sub.2] whose [tau]-invariant contains 1, but not 2. The case of [tau]([v.sub.2]) = {1} was described above, so the only choice is [tau]([v.sub.2]) = {1,3}. This yields a complete molecule. The same argument works for [v.sub.1] having [tau]-invariant of {1, 3}.

This completes the classification:

Example 2.4 It takes some more work to classify the S5 molecules (see the paper of Stembridge (2008a))

The simple part of a molecule is the graph formed by erasing all the arcs. We usually view it as an undirected graph. A morphism of molecules [phi]: M [right arrow] N is a map between the vertex sets which

1. is a graph morphism of the simple parts,

2. preserves [tau]-invariants.

Notice that a morphism does not need to respect arcs, aside from ones whose weights are determined by the local polygon rules from the simple edges.

2.2 Restriction

Let J [subset or equal to] S and let [W.sub.J] be the corresponding parabolic subgroup.

Let M = (V, m, [tau]) be a W-molecular graph. The [W.sub.J]-restriction of M is N = (V, m', [tau]'), with

1. for all v [member of] V, [tau]'(v) = [tau](v) [intersection] J,

2. for all u, v [member of] V,


The [W.sub.J]-restriction of M is a [W.sub.J]-molecular graph. A [W.sub.J]- submolecule of M is a [W.sub.J]-molecule (i.e. component connected by simple edges) of the [W.sub.J]-restriction of M. There is a natural inclusion map of a [W.sub.J]-submolecule into the original molecular graph. Sometimes, abusing notation, we refer to the image of this map as a [W.sub.J]-submolecule. The sense in which we use the word should be clear from the context.

3 Dual equivalence graphs

This section summarizes the relevant definitions and results of Assaf (2008); they are restated and slightly specialized to make the similarity with W-molecules more apparent.

Fix n [member of] [Z.sup.>0]. Let (W, S) be a Coxeter system of type [A.sub.n]. Identify S in anatural way with {1, ..., n}. Define [a.sub.i] to be the edge of the Coxeter graph (throughout the paper we will refer to these edges as bonds) which links i and i + 1. Then B:= {[a.sub.1], ..., [a.sub.n-1]} is the set of all edges of the Coxeter graph. For examples with small n we will use the notation a, b, c, ... instead.

Definition 3.1 A signed colored graph of type n + 1 is a tuple (V, E, [tau], [beta]), where (V, E) is a finite undirected simple graph, [tau]: V [right arrow] [2.sup.S], and [beta]: E [right arrow] [2.sup.B].

Denote by [E.sub.i] the set of edges with label i (i.e. such that the corresponding value of [beta] contains i); we call these i-colored edges. This is a slight reindexing from Assaf's original definition; in the original [E.sub.i] was the set of edges whose label contains i - 1.

3.1 "Standard" dual equivalence graphs

We start by constructing a family, indexed by partitions, of signed colored graphs.

Let [lambda] be a partition of n + 1. Let SYT([lambda]) be the set of standard Young tableaux of shape [lambda]. The left descent set of a tableau T is

[tau](T) := {1 [less than or equal to] i [less than or equal to] n: i is located in a higher row than i + 1 in T}.

The left descent sets are shown in red in Example 3.2.

The set of vertices of our graph is V := SYT([lambda]).

By a diagonal of a tableau we mean a NW - SE diagonal. A dual Knuth move is the exchange of i and i + 1 in a standard tableau, provided that either i - 1 or i + 2 lies (necessarily strictly) between the diagonals containing i and i + 1. This corresponds to dual Knuth moves on the symmetric group via the "content reading word" (reading each diagonal from top to bottom, and concatenating in order of increasing height of the diagonals). The set of edges of our graph is the set of pairs of tableaux related by a dual Knuth move:

E := {(T, U) : T and U are related by a dual Knuth move}.

A dual Knuth move between tableaux T and U activates the bond [a.sub.i] if i lies in precisely one of [tau](T) and [tau](U), and i + 1 lies precisely in the other. Denote this condition by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For (T, U) [member of] E, let


The graph [G.sub.[lambda]] := (V, E, [tau], [beta]) is a signed colored graph of type n + 1.

Example 3.2 Two standard dual equivalence graphs (corresponding to the shapes 311 and 32).

The values of t are shown in red.

3.2 Axiomatics

A vertex w of a signed colored graph is said to admit an i-neighbor if precisely one of i and i + 1 lies in [tau](w).

Definition 3.3 A dual equivalence graph of type n + 1 is a signed colored graph (V, E, [tau], [beta]) such that for any 1 [less than or equal to] i < n:

1. For w [member of] V, w admits an i-neighbor if and only if there exists x [member of] V which is connected to w by an edge of color i. In this case x must be unique

2. Suppose (w, x) is an edge of color i. Then i [member of] [tau](w) iff i [not member of] [tau](x), i + 1 [member of] [tau](w) iff i + 1 [not member of] [tau](x), and if h < i - 1 or h > i + 2 then h [member of] [tau](w) iff h [member of] [tau](x).

In other words, going along an i colored edge switches i and i + 1 in the [tau] value, and does not affect anything except i - 1, i, i + 1, and i + 2.

3. Suppose (w, x) is an edge of color i. If i - 1 [member of] [tau](w)[DELTA][tau](x) then (i - 1 [member of] [tau](w) iff i + 1 [member of] [tau](w)), where [DELTA] is the symmetric difference. If i + 2 [member of] [tau](w)[DELTA][tau](x) then (i + 2 [member of] [tau](w) iff i [member of] [tau](w)).

4. If i < n - 2, consider the subgraph on all the vertices and edges labeled [a.sub.i] or [a.sub.i+1]. Each of its connected components has the form:

If i < n - 3, consider the subgraph on all the vertices and edges labeled [a.sub.i], [a.sub.i+1], or [a.sub.i+2]. Each of its connected components has the form:

5. Suppose (w,x) [member of] [E.sub.i], (x,y) [member of] [E.sub.j], and [absolute value of (i - j)] [greater than or equal to] 3. Then there exists v [member of] V such that (w, v) [member of] [E.sub.j], (v,y) [member of] [E.sub.i].

6. Consider a connected component of the subgraph on all the vertices and edges of colors [less than or equal to] i. If we erase all the i-colored edges it breaks down into several components. Any two these were connected by an i-colored edge.

A weak dual equivalence graph is a signed colored graph satisfying 1-5 of the above.

Proposition 3.4 The graph [G.sub.[lambda]] (the standard dual equivalence graph) is actually a dual equivalence graph. Moreover, [{[G.sub.[lambda]]}.sub.[lambda]] is a complete collection of isomorphism class representatives of dual equivalence graphs.

Proof: The references are to the paper of Assaf (2008). The first statement is Proposition 3.5. The second is a combination of Theorem 3.9 and Proposition 3.11. []

3.3 Restriction

Suppose G is a signed colored graph of type n + 1. For 0 [less than or equal to] k < n + 1, a(k + 1)-restriction of G consists of the same vertex set V, the edges colored [less than or equal to] k - 1, the [tau] function post-composed with intersection with {1, ..., k}, and the [beta] function post-composed with restriction to {[a.sub.1], ..., [a.sub.k-1]} (see Example 3.5). The (k + 1)-restriction of G is a signed colored graph of type k + 1. The property of being a dual equivalence graph (or a weak dual equivalence graph) is preserved by restriction. By a (k + 1)-component of G we mean either the connected component of the restriction, or the induced subgraph of G on vertices corresponding to such connected component. It should be clear from the context which of these we are talking about.

The n-components of [G.sub.[lambda]] are obtained by fixing the position of n + 1 in the tableau. Such a component is isomorphic to [G.sub.[mu]], where [mu] if formed from [lambda] by erasing the outer corner which contained n + 1. Here is what it looks like on the above examples:

Example 3.5

The condition of being a weak dual equivalence graph is already quite powerful. The following lemma is relevant to us. It essentially says that a weak dual equivalence graph with a nice restriction property is necessarily a cover of a dual equivalence graph.

Lemma 3.6 Suppose G is a weak dual equivalence graph of type n + 1. Suppose moreover that each n-component is a dual equivalence graph. Then there is a surjective morphism [phi]: G [right arrow] [G.sub.[lambda]] for some partition [lambda] of n + 1, which restricts to an isomorphism on the n- components.

Let C [congruent to] [G.sub.[mu]] be an n-component. Then for any partition [upsilon] [not equal to] [mu] of n with [upsilon] [subset] [lambda], there exists a unique n-component D [congruent to] [G.sub.[mu]] with which is connected to C by an (n - 1)-colored edge. Also, two n-components which are both isomorphic to [G.sub.[mu]] are not connected by an (n - 1)- colored edge.

Proof: The references are again to the paper of Assaf (2008). The existence of the morphism is shown in Theorem 3.14. Its surjectivity follows by Remark 3.8. The fact that it restricts to an isomorphism on the n-components follows from the proof of Theorem 3.14. The covering properties from the second paragraph are shown in Corollary 3.15, though the last one is not explicitly mentioned. []

3.4 Molecules and dual equivalence graphs

Proposition 3.7 The simple part of an [A.sub.n] molecule, with [beta](u,v) = {bonds activated by the edge (u,v)} is a weak dual equivalence graph.

Proof: Axioms (1), (2), (3) follow directly from SR, BR, and CR. The [S.sub.4] and [S.sub.5] molecules have been computed by Stembridge (2008a) (see Examples 2.3 and 2.4). This shows that (4) is satisfied. The axiom (5) is a weaker version of the local polygon rule. []

Consider the graph [G.sub.[lambda]] from section 3.1. It is clear that (viewed as a weighted directed graph with all edges pointing both ways and having weight 1) it is an admissible S-labeled graph for the [A.sub.n] root system. It is well known that it forms the simple part of an [A.sub.n]-molecule (the left Kazhdan-Lusztig cell) which we call [bar.[G.sub.[lambda]]].

Definition 3.8 An [A.sub.n] molecule is a Kazhdan-Lusztig molecule if it is isomorphic to [bar.[G.sub.[lambda]]], i.e. if its simple part is a dual equivalence graph.

4 Main theorem

In this section we show that any [A.sub.n] molecule is Kazhdan-Lusztig. The proof will proceed by induction on n, so the preliminary results will start with an [A.sub.n] molecule whose [A.sub.n-1] submolecules are Kazhdan-Lusztig.

The first of these results states that if two such [A.sub.n-1] molecules are connected by a simple edge, then the connecting [A.sub.n-2] submolecules are isomorphic and there is a "cabling" of edges (possibly arcs) of weight 1 between these [A.sub.n-2] molecules:

Lemma 4.1 Let M be an [A.sub.n] molecule whose [A.sub.n-1] submolecules are Kazhdan-Lusztig. Suppose A and B are two such submolecules which are joined by a simple edge (in M), namely there exist x [member of] A, y [member of] B such that the edge x - y is simple. Let A' (resp. B') be the [A.sub.n-2] submolecule of M containing x (resp. y). Then there is an isomorphism [psi] between A' and B' such that [psi](x) = y. Moreover, if n [member of] [tau](x) then m(z [right arrow] [psi](z)) = 1 for all z [member of] A'.

The second preliminary result shows that if, out of three [A.sub.n-1] submolecules, two pairs (satisfying some conditions) are connected by simple edges, then the third pair is also connected by a simple edge:

The conditions will later be removed to show that any pair of [A.sub.n-1] submolecules of an [A.sub.n] molecule is connected by a simple edge.

Lemma 4.2 Let M be an [A.sub.n]-molecule whose [A.sub.n-1] submolecules are Kazhdan-Lusztig. By Proposition 3.6, there is a surjective morphism [phi]: M [right arrow] [bar.[G.sub.[lambda]]] for some partition [lambda] of n + 1. Let A, B, C be [A.sub.n-1] submolecules of M such that A and B are both connected to C by simple edges. Then A [congruent to] [bar.[G.sub.[mu]]], B [congruent to] [bar.[G.sub.[upsilon]]], C [congruent to] [bar.[G.sub.[eta]]], for some partitions formed by deleting outer corners of [lambda]. The three partitions have to be different by Proposition 3.6. Suppose moreover that the deleted corner for n was the highest of the three, namely:

Then A and B are connected by a simple edge.

We can now finish the proof of the theorem.

Theorem 4.3 Any An molecule is Kazhdan-Lusztig.

Proof: We know that the simple part of an [A.sub.n] molecule is a weak dual equivalence graph. It remains to show that it satisfies the axiom (6), namely that any two [A.sub.n-1] submolecules are connected by a simple edge.

Proceed by induction on n, the case n = 1 being trivial. Let M be an [A.sub.n] molecule. By inductive assumption, all [A.sub.n-1] molecules are Kazhdan-Lusztig. So, according to 3.6 there is a covering M [right arrow] [bar.[G.sub.[lambda]]], for some partition [lambda] of n + 1.

Choose two of these [A.sub.n-1] submolecules, A and Z. Choose a path of simple edges between them which goes through the fewest number of molecules. If it does not go through other molecules, then we are done. Suppose that is not so. Let A, B, C be the first three molecules on the path (it may happen that Z = C). The partitions [mu], [upsilon], [eta] corresponding to A, B, and C are formed by removing an outer corner of [lambda]; they are all distinct by Proposition 3.6.

Again using Proposition 3.6, consider the following string of [A.sub.n-1] submolecules connected by simple edges: A - B - C - A' - B', with A [congruent to] A', B [congruent to] B', and some of these possibly equalities. Out of [mu], [upsilon], and [eta] choose the partition which is formed by removing the highest box of [lambda]. In the above string, choose a copy of the corresponding [A.sub.n-1] submolecule with submolecules attached on both sides (for example, if [lambda]\[mu] was highest of the three, then we should choose A'). Then the triple consisting of this submolecule and the two adjacent ones satisfies the condition of the Lemma 4.2 (in the example, it would be the triple C - A' - B'). Applying it we get that A' = A, and B' = B. But then A is connected to C, contradicting our assumption that the path went through a minimal number of molecules.

So any two [A.sub.n-1] molecules are connected by an edge, finishing the proof. []


S. H. Assaf. Dual Equivalence Graphs I: A combinatorial proof of LLT and Macdonald positivity. arXiv:1005.3759, 2008.

D. Kazhdan and G. Lusztig. Representations of Coxeter groups and Hecke algebras. Invent. Math., 53(2): 165-184, 1979.

J. R. Stembridge. Admissible W-graphs. Representation Theory, 12:346-368, 2008a.

J. R. Stembridge. More W-graphs and cells: molecular components and cell synthesis. 8/ stembridge0 8.pdf, 2008b.

J. R. Stembridge. Personal communication, 2011.

J. R. Stembridge. A finiteness theorem for W-graphs. Advances in Mathematics, 229:2405-2414, 2012.

Michael Chmutov

Department of Mathematics, University of Michigan, 2074 East Hall, 530 Church

St., Ann Arbor, MI 48109
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Chmutov, Michael
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2013
Previous Article:Transition matrices for symmetric and quasisymmetric Hall-Littlewood polynomials (extended abstract).
Next Article:Cyclic sieving of increasing tableaux and small Schroder paths.

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters