Order Dimension,Strong Bruhat Order and Lattice Properties for Posets

We determine the order dimension of the strong Bruhat order on finite Coxeter groups of types A, B and H. The order dimension is determined using a generalization of a theorem of Dilworth: dim (P)=width(Irr(P)), whenever P satisfies a simple order-theoretic condition called here the dissective property (or clivage). The result for dissective posets follows from an upper bound and lower bound on the dimension of any finite poset. The dissective property is related, via MacNeille completion, to the distributive property of lattices. We show a similar connection between quotients of the strong Bruhat order with respect to parabolic subgroups and lattice quotients.     

On the cyclically fully commutative elements of Coxeter groups

Let W be an arbitrary Coxeter group. If two elements have expressions that are cyclic shifts of each other (as words), then they are conjugate (as group elements) in?W. We say that w is cyclically fully commutative (CFC) if every cyclic shift of any reduced expression for w is fully commutative (i.e., avoids long braid relations). These generalize Coxeter elements in that their reduced expressions can be described combinatorially by acyclic directed graphs, and cyclically shifting corresponds to source-to-sink conversions. In this paper, we explore the combinatorics of the CFC elements and enumerate them in all Coxeter groups. Additionally, we characterize precisely which CFC elements have the property that powers of them remain fully commutative, via the presence of a simple combinatorial feature called a band. This allows us to give necessary and sufficient conditions for a CFC element w to be logarithmic, that is, ?(w ^k )=k??(w) for all k??1, for a large class of Coxeter groups that includes all affine Weyl groups and simply laced Coxeter groups. Finally, we give a simple non-CFC element that fails to be logarithmic under these conditions.     

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 Short Derivation of the Möbius Function for the Bruhat Order

We give a short, self-contained derivation of the Möbius function for the Bruhat orderings of Coxeter groups and their parabolic quotients.     

The sorting order on a Coxeter group

Let (W,S) be an arbitrary Coxeter system. For each word ω in the generators we define a partial order—called the ω-sorting order—on the set of group elements Wω⊆W that occur as subwords of ω. We show that the ω-sorting order is a supersolvable join-distributive lattice and that it is strictly between the weak and Bruhat orders on the group. Moreover, the ω-sorting order is a “maximal lattice” in the sense that the addition of any collection of Bruhat covers results in a nonlattice.Along the way we define a class of structures called supersolvable antimatroids and we show that these are equivalent to the class of supersolvable join-distributive lattices.     

On Growth Types of Quotients of Coxeter Groups by Parabolic Subgroups

The principal objects studied in this note are infinite, non-affine Coxeter groups W. A well-known result of de la Harpe asserts that such groups have exponential growth. We study the growth type of quotients of W by parabolic subgroups and by a certain class of reflection subgroups. Our main result is that these quotients have exponential growth as well.     

Combinatorial proof of the inversion formula on the Kazhdan–Lusztig R-polynomials

In this paper, we present a combinatorial proof of the inversion formula on the Kazhdan–Lusztig \(R\) -polynomials. This problem was raised by Brenti. As a consequence, we obtain a combinatorial interpretation of the equidistribution property due to Verma stating that any nontrivial interval of a Coxeter group in the Bruhat order has as many elements of even length as elements of odd length. The same argument leads to a combinatorial proof of an extension of Verma’s equidistribution to the parabolic quotients of a Coxeter group obtained by Deodhar. As another application, we derive a refinement of the inversion formula for the symmetric group by restricting the summation to permutations ending with a given element.     

A Weighted Enumeration of Maximal Chains in the Bruhat Order

Given a finite Weyl group W with root system , assign the weight to each covering pair in the Bruhat order related by the reflection corresponding to . Extending this multiplicatively to chains, we prove that the sum of the weights of all maximal chains in the Bruhat order has an explicit product formula, and prove a similar result for a weighted sum over maximal chains in the Bruhat ordering of any parabolic quotient of W. Several variations and open problems are discussed.     

Fixed points of involutive automorphisms of the Bruhat order

Applying a classical theorem of Smith, we show that the poset property of being Gorenstein^* over Z₂ is inherited by the subposet of fixed points under an involutive poset automorphism. As an application, we prove that every interval in the Bruhat order on (twisted) involutions in an arbitrary Coxeter group has this property, and we find the rank function. This implies results conjectured by F. Incitti. We also show that the Bruhat order on the fixed points of an involutive automorphism induced by a Coxeter graph automorphism is isomorphic to the Bruhat order on the fixed subgroup viewed as a Coxeter group in its own right.     

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.     

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).     

Monotonicity of strata in the stratification of the cone of totally positive matrices

According to a theorem of Bjorner [5], there exists a stratified space whose strata are labeled by the elements of [u, v] for every interval [u, v] in the Bruhat order of a Coxeter group W, and each closed stratum (respectively the boundary of each stratum) has the homology of a ball (respectively of a sphere). In [6], Fomin and Shapiro suggest a natural geometric realization of these stratified spaces for a Weyl group W of a semi-simple Lie group G, and then prove its validity in the case of the symmetric group. The stratified spaces arise as links in the Bruhat decomposition of the totally non-negative part of the unipotent radical of G. In this article, we verify the topological regularity property of the strata formed as a result of Bruhat partial ordering on the elements of theWeyl group (of rank 4) of a semi-simple simply connected algebraic group G which is SL(4,?) in our case here. The Weyl group here is the Coxeter group S ₄.     

Sets of reflections defining twisted Bruhat orders

Twisted Bruhat orders are certain partial orders on a Coxeter system (W,S) associated to initial sections of reflection orders, which are certain subsets of the set of reflections T of a Coxeter system. We determine which subsets of T give rise to a partial order on W in the same way.     

Permutahedra and generalized associahedra

Given a finite Coxeter system (W,S) and a Coxeter element c, or equivalently an orientation of the Coxeter graph of W, we construct a simple polytope whose outer normal fan is N. Reading's Cambrian fan Fc, settling a conjecture of Reading that this is possible. We call this polytope the c-generalized associahedron. Our approach generalizes Loday's realization of the associahedron (a type A c-generalized associahedron whose outer normal fan is not the cluster fan but a coarsening of the Coxeter fan arising from the Tamari lattice) to any finite Coxeter group. A crucial role in the construction is played by the c-singleton cones, the cones in the c-Cambrian fan which consist of a single maximal cone from the Coxeter fan.Moreover, if W is a Weyl group and the vertices of the permutahedron are chosen in a lattice associated to W, then we show that our realizations have integer coordinates in this lattice.     

Pattern avoidance and Boolean elements in the Bruhat order on involutions

We show that the principal order ideal of an element w in the Bruhat order on involutions in a symmetric group is a Boolean lattice if and only if w avoids the patterns 4321, 45312 and 456123. Similar criteria for signed permutations are also stated. Involutions with this property are enumerated with respect to natural statistics. In this context, a bijective correspondence with certain Motzkin paths is demonstrated. This article is largely based on results from the second author’s M.Sc. thesis [15].     

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 ()     

A Distributive Lattice Structure Connecting Dyck Paths,Noncrossing Partitions and 312-avoiding Permutations

In [Ferrari, L. and Pinzani, R.: Lattices of lattice paths. J. Stat. Plan. Inference 135 (2005), 77–92] a natural order on Dyck paths of any fixed length inducing a distributive lattice structure is defined. We transfer this order to noncrossing partitions along a well-known bijection [Simion, R.: Noncrossing partitions. Discrete Math. 217 (2000), 367–409], thus showing that noncrossing partitions can be endowed with a distributive lattice structure having some combinatorial relevance. Finally we prove that our lattices are isomorphic to the posets of 312-avoiding permutations with the order induced by the strong Bruhat order of the symmetric group.     

Cambrian lattices

For an arbitrary finite Coxeter group W, we define the family of Cambrian lattices for W as quotients of the weak order on W with respect to certain lattice congruences. We associate to each Cambrian lattice a complete fan, which we conjecture is the normal fan of a polytope combinatorially isomorphic to the generalized associahedron for W. In types A and B we obtain, by means of a fiber-polytope construction, combinatorial realizations of the Cambrian lattices in terms of triangulations and in terms of permutations. Using this combinatorial information, we prove in types A and B that the Cambrian fans are combinatorially isomorphic to the normal fans of the generalized associahedra and that one of the Cambrian fans is linearly isomorphic to Fomin and Zelevinsky's construction of the normal fan as a “cluster fan.” Our construction does not require a crystallographic Coxeter group and therefore suggests a definition, at least on the level of cellular spheres, of a generalized associahedron for any finite Coxeter group. The Tamari lattice is one of the Cambrian lattices of type A, and two “Tamari” lattices in type B are identified and characterized in terms of signed pattern avoidance. We also show that open intervals in Cambrian lattices are either contractible or homotopy equivalent to spheres.