Maximally Clustered Elements and Schubert Varieties

We introduce and study a class of “maximally clustered” elements for simply laced Coxeter groups. Such elements include as a special case the freely braided elements of Green and the author, which in turn constitute a superset of the iji-avoiding elements of Fan. We show that any reduced expression for a maximally clustered element is short-braid equivalent to a “contracted” expression, which can be characterized in terms of certain subwords called “braid clusters”. We establish some properties of contracted reduced expressions and apply these to the study of Schubert varieties in the simply laced setting. Specifically, we give a smoothness criterion for Schubert varieties indexed by maximally clustered elements. Received December 30, 2005     

Monomials and Temperley–Lieb Algebras

We classify the “fully tight” simply laced Coxeter groups, that is, the ones whoseiji-avoiding Kazhdan–Lusztig basis elements are monomials in the generatorsB_si. We then investigate the basis of the Temperley–Lieb algebra arising from the Kazhdan–Lusztig basis of the associated Hecke algebra, and prove that the basis coincides with the usual (monomial) basis.     

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

Brauer algebras of simply laced type

The diagram algebra introduced by Brauer that describes the centralizer algebra of the n-fold tensor product of the natural representation of an orthogonal Lie group has a presentation by generators and relations that only depends on the path graph A _{n − 1} on n − 1 nodes. Here we describe an algebra depending on an arbitrary graph Q, called the Brauer algebra of type Q, and study its structure in the cases where Q is a Coxeter graph of simply laced spherical type (so its connected components are of type A _{n − 1}, D _n , E₆, E₇, E₈). We find its irreducible representations and its dimension, and show that the algebra is cellular. The algebra is generically semisimple and contains the group algebra of the Coxeter group of type Q as a subalgebra. It is a ring homomorphic image of the Birman-Murakami-Wenzl algebra of type Q; this fact will be used in later work determining the structure of the Birman-Murakami-Wenzl algebras of simply laced spherical type.     

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.     

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.     

Average-case complexity and decision problems in group theory

We investigate the average-case complexity of decision problems for finitely generated groups, in particular, the word and membership problems. Using our recent results on “generic-case complexity”, we show that if a finitely generated group G has word problem solvable in subexponential time and has a subgroup of finite index which possesses a non-elementary word-hyperbolic quotient group, then the average-case complexity of the word problem of G is linear time, uniformly with respect to the collection of all length-invariant measures on G. This results applies to many of the groups usually studied in geometric group theory: for example, all braid groups B_n, all groups of hyperbolic knots, many Coxeter groups and all Artin groups of extra-large type.     

The topology at infinity of Coxeter groups and buildings

The connectivity at infinity of a finitely generated Coxeter group W is completely determined by topological properties of its nerve L (a finite simplicial complex). For example, W is simply connected at infinity if and only if L and the subcomplexes (where ranges over all simplices in L) are simply connected. This characterization extends to locally finite buildings. Received: May 3, 2001     

Coxeter Decompositions of Compact Hyperbolic Pyramids and Triangular Prisms

A polyhedron P admits a Coxeter decomposition if P can be tiled by finitely many Coxeter polyhedra such that any two tiles having a common face are symmetric with respect to this face. In this paper, we classify Coxeter decompositions of compact convex pyramids and triangular prisms in the hyperbolic space $\mathbb{H}^3 $ .     

Embeddings of root systems I: Root systems over commutative rings

This paper gives examples of embeddings of root systems of Coxeter groups, including sporadic embeddings of standard real root systems in other standard real root systems, and, for a general Coxeter group, an embedding of its universal symmetric root system over commutative rings into the standard real root system of a simply laced Coxeter group.     

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.     

Subword complexes and edge subdivisions

For a finite Coxeter group, a subword complex is a simplicial complex associated with a pair (Q, π), where Q is a word in the alphabet of simple reflections and π is a group element. We discuss the transformations of such a complex that are induced by braid moves of the word Q. We show that under certain conditions, such a transformation is a composition of edge subdivisions and inverse edge subdivisions. In this case, we describe how the H- and γ-polynomials change under the transformation. This case includes all braid moves for groups with simply laced Coxeter diagrams.     

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.     

Geometric diffeomorphism finiteness in low dimensions and homotopy group finiteness

The main results of this note consist in the following two geometric finiteness theorems for diffeomorphism types and homotopy groups of closed simply connected manifolds: 1. For any given numbers C and D the class of closed smooth simply connected manifolds of dimension which admit Riemannian metrics with sectional curvature bounded in absolute value by $\vert K \vert\le C$ and diameter bounded from above by D contains at most finitely many diffeomorphism types. In each dimension there exist counterexamples to the preceding statement. 2. For any given numbers C and D and any dimension m there exist for each natural number up to isomorphism always at most finitely many groups which can occur as the k-th homotopy group of a closed smooth simply connected m-manifold which admits a metric with sectional curvature and diameter . Received: 21 August 1999 / Accepted: 20 April 2001 / Published online: 19 October 2001     

Dynkin Diagram Classification of λ-Minuscule Bruhat Lattices and of d-Complete Posets

d-Complete posets are defined to be posets which satisfy certain local structural conditions. These posets play or conjecturally play several roles in algebraic combinatorics related to the notions of shapes, shifted shapes, plane partitions, and hook length posets. They also play several roles in Lie theory and algebraic geometry related to -minuscule elements and Bruhat distributive lattices for simply laced general Weyl or Coxeter groups, and to -minuscule Schubert varieties. This paper presents a classification of d-complete posets which is indexed by Dynkin diagrams.     

Schubert Varieties and Free Braidedness

We give a simple necessary and sufficient condition for a Schubert variety X_w to be smooth when w is a freely braided element of a simply laced Weyl group; such elements were introduced by the authors in a previous work. This generalizes in one direction a result of Fan concerning varieties indexed by short-braid avoiding elements. We also derive generating functions for the freely braided elements that index smooth Schubert varieties. All results are stated and proved only for the simply laced case.     

Centralizers of Involutions in Locally Finite Groups

The present article deals with locally finite groups G having an involution φ such that C _G (φ) is an SF-group. It is shown that G possesses a normal subgroup B which is a central product of finitely many groups isomorphic to PSL(2, K _i ) or SL(2, K _i ) for some infinite locally finite fields K _i of odd characteristic, such that [G, φ]′/B and G/[G, φ] are both SF-groups.     

Minimal length elements in some double cosets of Coxeter groups

We study the minimal length elements in some double cosets of Coxeter groups and use them to study Lusztig's G-stable pieces and the generalization of G-stable pieces introduced by Lu and Yakimov. We also use them to study the minimal length elements in a conjugacy class of a finite Coxeter group and prove a conjecture in [M. Geck, S. Kim, G. Pfeiffer, Minimal length elements in twisted conjugacy classes of finite Coxeter groups, J. Algebra 229 (2) (2000) 570-600].