On the Fully Commutative Elements of Coxeter Groups

Let W be a Coxeter group. We define an element w ε W to be fully commutative if any reduced expression for w can be obtained from any other by means of braid relations that only involve commuting generators. We give several combinatorial characterizations of this property, classify the Coxeter groups with finitely many fully commutative elements, and classify the parabolic quotients whose members are all fully commutative. As applications of the latter, we classify all parabolic quotients with the property that (1) the Bruhat ordering is a lattice, (2) the Bruhat ordering is a distributive lattice, (3) the weak ordering is a distributive lattice, and (4) the weak ordering and Bruhat ordering coincide. Partially supported by NSF Grants DMS-9057192 and DMS-9401575.     

Left cells containing a fully commutative element

Let W be a finite or an affine Coxeter group and W_c the set of all the fully commutative elements in W. For any left cell L of W containing some fully commutative element, our main result of the paper is to prove that there exists a unique element (say w^L) in L∩W_c such that any z∈L has the form z=xw^L with ?(z)=?(x)+?(w^L) for some x∈W. This implies that L is left connected, verifying a conjecture of Lusztig in our case.     

On 321-Avoiding Permutations in Affine Weyl Groups

We introduce the notion of 321-avoiding permutations in the affine Weyl group W of type A _{n – 1} by considering the group as a George group (in the sense of Eriksson and Eriksson). This enables us to generalize a result of Billey, Jockusch and Stanley to show that the 321-avoiding permutations in W coincide with the set of fully commutative elements; in other words, any two reduced expressions for a 321-avoiding element of W (considered as a Coxeter group) may be obtained from each other by repeated applications of short braid relations.Using Shi's characterization of the Kazhdan–Lusztig cells in the group W, we use our main result to show that the fully commutative elements of W form a union of Kazhdan–Lusztig cells. This phenomenon has been studied by the author and J. Losonczy for finite Coxeter groups, and is interesting partly because it allows certain structure constants for the Kazhdan–Lusztig basis of the associated Hecke algebra to be computed combinatorially.We also show how some of our results can be generalized to a larger group of permutations, the extended affine Weyl group associated to GL _n ()     

The Enumeration of Fully Commutative Elements of Coxeter Groups

A Coxeter group element w is fully commutative if any reduced expression for w can be obtained from any other via the interchange of commuting generators. For example, in the symmetric group of degree n, the number of fully commutative elements is the nth Catalan number. The Coxeter groups with finitely many fully commutative elements can be arranged into seven infinite families A_n, B_n, D_n, E_n,F_n, H_n and I₂(m). For each family, we provide explicit generating functions for the number of fully commutative elements and the number of fully commutative involutions; in each case, the generating function is algebraic.     

A Characterization of the Simply-Laced FC-Finite Coxeter Groups

We call an element of a Coxeter group fully covering (or a fully covering element) if its length is equal to the number of the elements it covers in the Bruhat ordering. It is easy to see that the notion of fully covering is a generalization of the notion of a 321-avoiding permutation and that a fully covering element is a fully commutative element. Also, we call a Coxeter group bi-full if its fully commutative elements coincide with its fully covering elements. We show that the bi-full Coxeter groups are the ones of type A_n, D_n, E_n with no restriction on n. In other words, Coxeter groups of type E₉, E₁₀,.... are also bi-full. According to a result of Fan, a Coxeter group is a simply-laced FC-finite Coxeter group if and only if it is a bi-full Coxeter group.AMS Subject Classification: 06A07, 20F55.     

A quiver presentation for Solomon's descent algebra

The descent algebra Σ(W) is a subalgebra of the group algebra QW of a finite Coxeter group W, which supports a homomorphism with nilpotent kernel and commutative image in the character ring of W. Thus Σ(W) is a basic algebra, and as such it has a presentation as a quiver with relations. Here we construct Σ(W) as a quotient of a subalgebra of the path algebra of the Hasse diagram of the Boolean lattice of all subsets of S, the set of simple reflections in W. From this construction we obtain some general information about the quiver of Σ(W) and an algorithm for the construction of a quiver presentation for the descent algebra Σ(W) of any given finite Coxeter group W.     

Leading coefficients of Kazhdan–Lusztig polynomials and fully commutative elements

Let W be a Coxeter group of type . We show that the leading coefficient, μ(x,w), of the Kazhdan–Lusztig polynomial P _x,w is always equal to 0 or 1 if x is fully commutative (and w is arbitrary).     

Reflection Independence in Even Coxeter Groups

If (W,S) is a Coxeter system, then an element of W is a reflection if it is conjugate to some element of S. To each Coxeter system there is an associated Coxeter diagram. A Coxeter system is called reflection preserving if every automorphism of W preserves reflections in this Coxeter system. As a direct application of our main theorem, we classify all reflection preserving even Coxeter systems. More generally, if (W,S) is an even Coxeter system, we give a combinatorial condition on the diagram for (W,S) that determines whether or not two even systems for W have the same set of reflections. If (W,S) is even and (W,S) is not even, then these systems do not have the same set of reflections. A Coxeter group is said to be reflection independent if any two Coxeter systems (W,S) and (W,S) have the same set of reflections. We classify all reflection independent even Coxeter groups.Mathematics Subject Classifications (2000). 20F05, 20F55, 20F65, 51F15.     

Inversion arrangements and Bruhat intervals

Let W be a finite Coxeter group. For a given w∈W, the following assertion may or may not be satisfied:

(?)

The principal Bruhat order ideal of w contains as many elements as there are regions in the inversion hyperplane arrangement of w.

We present a type independent combinatorial criterion which characterises the elements w∈W that satisfy (?). A couple of immediate consequences are derived:

(1)

The criterion only involves the order ideal of w as an abstract poset. In this sense, (?) is a poset-theoretic property.

(2)

For W of type A, another characterisation of (?), in terms of pattern avoidance, was previously given in collaboration with Linusson, Shareshian and Sjöstrand. We obtain a short and simple proof of that result.

(3)

If W is a Weyl group and the Schubert variety indexed by w∈W is rationally smooth, then w satisfies (?).

     

A Hecke Algebra Quotient and Some Combinatorial Applications

Let (W, S) be a Coxeter group associated to a Coxeter graph which has no multiple bonds. Let H be the corresponding Hecke Algebra. We define a certain quotient \-H of H and show that it has a basis parametrized by a certain subset W _cof the Coxeter group W. Specifically, W _cconsists of those elements of W all of whose reduced expressions avoid substrings of the form sts where s and t are noncommuting generators in S. We determine which Coxeter groups have finite W _cand compute the cardinality of W _cwhen W is a Weyl group. Finally, we give a combinatorial application (which is related to the number of reduced expressions for w W _cof an exponential formula of Lusztig which utilizes a specialization of a subalgebra of \-H.     

Maps between buildings that preserve a given Weyl distance

Let Δ and Δ′ be two buildings of the same type (W, S), viewed as sets of chambers endowed with“distance” functions δ and δ′, respectively, admitting values in the common Weyl group W, which is a Coxeter group with standard generating set S. For a given element ω ε W, we study surjective maps ? : Δ → Δ′ with the property that δ(C, D) = ω if and only if Δ′ (?(C), ?(D)) = ω. The result is that the restrictions of ? to all residues of certain spherical types—determined by ω—are isomorphisms. We show with counterexamples that this result is optimal. We also demonstrate that, in many cases, this is enough to conclude that ? is an isomorphism. In particular, ? is an isomorphism if Δ and Δ′ are 2-spherical and every reduced expression of ω involves all elements of S.     

The Enumeration of Coxeter Elements

Let (W,S, ) be a Coxeter system: a Coxeter group W with S its distinguished generator set and its Coxeter graph. In the present paper, we always assume that the cardinality l=|S| ofS is finite. A Coxeter element of W is by definition a product of all generators s S in any fixed order. We use the notation C(W) to denote the set of all the Coxeter elements in W. These elements play an important role in the theory of Coxeter groups, e.g., the determination of polynomial invariants, the Poincaré polynomial, the Coxeter number and the group order of W (see [1–5] for example). They are also important in representation theory (see [6]). In the present paper, we show that the set C(W) is in one-to-one correspondence with the setC() of all acyclic orientations of . Then we use some graph-theoretic tricks to compute the cardinality c(W) of the setC(W) for any Coxeter group W. We deduce a recurrence formula for this number. Furthermore, we obtain some direct formulae of c(W) for a large family of Coxeter groups, which include all the finite, affine and hyperbolic Coxeter groups.The content of the paper is organized as below. In Section 1, we discuss some properties of Coxeter elements for simplifying the computation of the value c(W). In particular, we establish a bijection between the sets C(W) andC() . Then among the other results, we give a recurrence formula of c(W) in Section 2. Subsequently we deduce some closed formulae of c(W) for certain families of Coxeter groups in Section 3.     

On orbits of order ideals of minuscule posets

An action on order ideals of posets considered by Fon-Der-Flaass is analyzed in the case of posets arising from minuscule representations of complex simple Lie algebras. For these minuscule posets, it is shown that the Fon-Der-Flaass action exhibits the cyclic sieving phenomenon, as defined by Reiner, Stanton, and White. A uniform proof is given by investigation of a bijection due to Stembridge between order ideals of minuscule posets and fully commutative Weyl group elements. This bijection is proven to be equivariant with respect to a conjugate of the Fon-Der-Flaass action and an arbitrary Coxeter element. If P is a minuscule poset, it is shown that the Fon-Der-Flaass action on order ideals of the Cartesian product P×[2] also exhibits the cyclic sieving phenomenon, only the proof is by appeal to the classification of minuscule posets and is not uniform.     

On cyclic edge-connectivity of transitive graphs

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph G, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut of G. In this paper, we first prove that for any cyclically separable graph G, , where ω(X) is the number of edges with one end in X and the other end in V(G)?X. A cyclically separable graph G with cλ(G)=ζ(G) is said to be cyclically optimal. The main results in this paper are: any connected k-regular vertex-transitive graph with k≥4 and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal.     

On dominance and minuscule Weyl group elements

Fix a Dynkin graph and let λ be a coweight. When does there exist an element w of the corresponding Weyl group such that w is λ-minuscule and w(λ) is dominant? We answer this question for general Coxeter groups. We express and prove these results using a variant of Mozes’ game of numbers.     

On Reflection Subgroups of Finite Coxeter Groups

Let W be a finite Coxeter group. We classify the reflection subgroups of W up to conjugacy and give necessary and sufficient conditions for the map that assigns to a reflection subgroup R of W the conjugacy class of its Coxeter elements to be injective, up to conjugacy.     

Kazhdan-Lusztig cells in some weighted Coxeter groups

Let(W,S) be a Coxeter group with S = I■J such that J consists of all universal elements of S and that I generates a finite parabolic subgroup W_I of W with w_0 the longest element of W_I. We describe all the left cells and two-sided cells of the weighted Coxeter group(W,S,L) that have non-empty intersection with W_J,where the weight function L of(W, S) is in one of the following cases:(i) max{L(s) | s ∈J} min{L(t)|t∈I};(ii) min{L(s)|s ∈J} ≥L(w_0);(iii) there exists some t ∈ I satisfying L(t) L(s) for any s ∈I-{t} and L takes a constant value L_J on J with L_J in some subintervals of [1, L(w_0)-1]. The results in the case(iii) are obtained under a certain assumption on(W, W_I).     

Hecke algebras with independent parameters

We study the Hecke algebra \({\mathcal {H}}({\mathbf {q}})\) over an arbitrary field \({\mathbb {F}}\) of a Coxeter system (W, S) with independent parameters \({\mathbf {q}}=(q_s\in {\mathbb {F}}:s\in S)\) for all generators. This algebra always has a spanning set indexed by the Coxeter group W, which is indeed a basis if and only if every pair of generators joined by an odd edge in the Coxeter diagram receives the same parameter. In general, the dimension of \({\mathcal {H}}({\mathbf {q}})\) could be as small as 1. We construct a basis for \({\mathcal {H}}({\mathbf {q}})\) when (W, S) is simply laced. We also characterize when \({\mathcal {H}}({\mathbf {q}})\) is commutative, which happens only if the Coxeter diagram of (W, S) is simply laced and bipartite. In particular, for type A, we obtain a tower of semisimple commutative algebras whose dimensions are the Fibonacci numbers. We show that the representation theory of these algebras has some features in analogy/connection with the representation theory of the symmetric groups and the 0-Hecke algebras.     

Parking structures: Fuss analogs

For any irreducible real reflection group W with Coxeter number h, Armstrong, Reiner, and the author introduced a pair of \(W \times {\mathbb {Z}}_{h}\) -modules which deserve to be called W-parking spaces which generalize the type A notion of parking functions and conjectured a relationship between them. In this paper we give a Fuss analog of their constructions. For a Fuss parameter k≥1, we define a pair of \(W \times {\mathbb {Z}}_{kh}\) -modules which deserve to be called k-W-parking spaces and conjecture a relationship between them. We prove the weakest version of our conjectures for each of the infinite families ABCDI of finite reflection groups, together with proofs of stronger versions in special cases. Whenever our weakest conjecture holds for W, we have the following corollaries.

• There is a simple formula for the character of either k-W-parking space.
• We recover a cyclic sieving result due to Krattenthaler and Müller which gives the cycle structure of a generalized rotation action on k-W-noncrossing partitions.
• When W is crystallographic, the restriction of either k-W-parking space to W is isomorphic to the action of W on the finite torus Q/(kh+1)Q, where Q is the root lattice.