More on the combinatorial invariance of Kazhdan-Lusztig polynomials

We prove that the Kazhdan-Lusztig polynomials are combinatorial invariants for intervals up to length 8 in Coxeter groups of type A and up to length 6 in Coxeter groups of type B and D. As a consequence of our methods, we also obtain a complete classification, up to isomorphism, of Bruhat intervals of length 7 in type A and of length 5 in types B and D, which are not lattices.     

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 note on the optimality of the N- and D-policies for the M/G/1 queue

This note considers the N- and D-policies for the M/G/1 queue. We concentrate on the true relationship between the optimal N- and D-policies when the cost function is based on the expected number of customers in the system.     

On the inverse braid and reflection monoids of type <Emphasis Type="Italic">B</Emphasis>

There are well-known relations between braid and symmetric groups as well as Artin-Brieskorn braid groups and Coxeter groups: the latter are the factor-groups of the Artin-Brieskorn braid groups. The inverse braid monoid is related to the inverse symmetric monoid in the same way. We show that similar relations exist between the inverse braid monoid of type B and the inverse reflection monoid of type B. This gives a presentation of the latter monoid.     

Noncommutative algebras related with Schubert calculus on Coxeter groups

For any finite Coxeter system (W,S) we construct a certain noncommutative algebra, the so-called bracket algebra, together with a family of commuting elements, the so-called Dunkl elements. The Dunkl elements conjecturally generate an algebra which is canonically isomorphic to the coinvariant algebra of the Coxeter group W. We prove this conjecture for classical Coxeter groups and I₂(m). We define a “quantization” and a multiparameter deformation of our construction and show that for Lie groups of classical type and G₂, the algebra generated by Dunkl’s elements in the quantized bracket algebra is canonically isomorphic to the small quantum cohomology ring of the corresponding flag variety, as described by B. Kim. For crystallographic Coxeter systems we define the so-called quantum Bruhat representation of the corresponding bracket algebra. We study in more detail the structure of the relations in B_n-, D_n- and G₂-bracket algebras, and as an application, discover a Pieri-type formula in the B_n-bracket algebra. As a corollary, we obtain a Pieri-type formula for multiplication of an arbitrary B_n-Schubert class by some special ones. Our Pieri-type formula is a generalization of Pieri’s formulas obtained by A. Lascoux and M.-P. Schützenberger for flag varieties of type A. We also introduce a super-version of the bracket algebra together with a family of pairwise anticommutative elements, the so-called flat connections with constant coefficients, which describes “a noncommutative differential geometry on a finite Coxeter group” in the sense of S. Majid.     

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.     

ComplexK-theory ofBSL3(Z)

ComplexK-theory ofBSL₃(Z) andBSt₃(Z) are computed. We first study a Brown-Peterson (BP) version of Soulé's arguments. Then we consider complexK-theory by using a Conner-Floyd type theorem.     

On Noncrossing and Nonnesting Partitions of Type D

We present an explicit bijection between noncrossing and nonnesting partitions of Coxeter systems of type D which preserves openers, closers, and transients.     

Pointed and multi-pointed partitions of type A and B

The aim of this paper is to define and study pointed and multi-pointed partition posets of type A and B (in the classification of Coxeter groups). We compute their characteristic polynomials, incidence Hopf algebras and homology groups. As a corollary, we show that some operads are Koszul over .     

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.     

Regular elements of semigroups B X ( D ) defined by generalized elementary B X ( D )-semilattices of unions

In the paper, the class of complete semigroups of binary relations is considered, each of whose elements is defined by a complete B _X (D)-semilattice of unions which belongs to the class of generalized elementary X-semilattices. Regular elements are described for each semigroup of this class. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 49, Algebra and Geometry, 2007.     

A Decomposition of the Descent Algebra of a Finite Coxeter Group

The purpose of this paper is twofold. First we aim to unify previous work by the first two authors, A. Garsia, and C. Reutenauer (see [2], [3], [4], [5] and [10]) on the structure of the descent algebras of the Coxeter groups of type A _n and B _n. But we shall also extend these results to the descent algebra of an arbitrary finite Coxeter group W. The descent algebra, introduced by Solomon in [14], is a subalgebra of the group algebra of W. It is closely related to the subring of the Burnside ring B(W) spanned by the permutation representations W/W _J, where the W _J are the parabolic subgroups of W. Specifically, our purpose is to lift a basis of primitive idempotents of the parabolic Burnside algebra to a basis of idempotents of the descent algebra.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

The absolute order on the hyperoctahedral group

The absolute order on the hyperoctahedral group B _n is investigated. Using a poset fiber theorem, it is proved that the order ideal of this poset generated by the Coxeter elements is homotopy Cohen–Macaulay. This method results in a new proof of Cohen–Macaulayness of the absolute order on the symmetric group. Moreover, it is shown that every closed interval in the absolute order on B _n is shellable and an example of a non-Cohen–Macaulay interval in the absolute order on D ₄ is given. Finally, the closed intervals in the absolute order on B _n and D _n which are lattices are characterized and some of their important enumerative invariants are computed.     

On spaces which are linearly D

We introduce a generalization of D-spaces, which we call linearly D-spaces. The following results are obtained for a T₁-space X.

– X is linearly Lindelöf if, and only if, X is a linearly D-space of countable extent.

– X is linearly D provided that X is submetaLindelöf.

– X is linearly D provided that X is the union of finitely many linearly D-subspaces.

– X is compact provided that X is countably compact and X is the union of countably many linearly D-subspaces.

A Clifford Algebraic Framework for Coxeter Group Theoretic Computations

Real physical systems with reflective and rotational symmetries such as viruses, fullerenes and quasicrystals have recently been modeled successfully in terms of three-dimensional (affine) Coxeter groups. Motivated by this progress, we explore here the benefits of performing the relevant computations in a Geometric Algebra framework, which is particularly suited to describing reflections. Starting from the Coxeter generators of the reflections, we describe how the relevant chiral (rotational), full (Coxeter) and binary polyhedral groups can be easily generated and treated in a unified way in a versor formalism. In particular, this yields a simple construction of the binary polyhedral groups as discrete spinor groups. These in turn are known to generate Lie and Coxeter groups in dimension four, notably the exceptional groups D ₄, F ₄ and H ₄. A Clifford algebra approach thus reveals an unexpected connection between Coxeter groups of ranks 3 and 4. We discuss how to extend these considerations and computations to the Conformal Geometric Algebra setup, in particular for the non-crystallographic groups, and construct root systems and quasicrystalline point arrays. We finally show how a Clifford versor framework sheds light on the geometry of the Coxeter element and the Coxeter plane for the examples of the twodimensional non-crystallographic Coxeter groups I ₂(n) and the threedimensional groups A ₃, B ₃, as well as the icosahedral group H ₃. IPPP/12/49, DCPT/12/98     

The representation dimension of Hecke algebras and symmetric groups

We establish a lower bound for the representation dimension of all the classical Hecke algebras of types A, B and D. For all the type A algebras, and “most” of the algebras of types B and D, we also establish upper bounds. Moreover, we establish bounds for the representation dimension of group algebras of some symmetric groups.     

K(π 1)'s for Artin Groups of Finite Type

We construct K( 1)'s for Artin groups of type C _n and D _n , using the lattice of elements preceding a Coxeter element in the partial order defined by reflection length.     

L 1→ L q Poincaré Inequalities for 0 < q < 1 Imply Representation Formulas

Given two doubling measures μ and ν in a metric space (S, ρ) of homogeneous type, let B ₀⊂S be a given ball. It has been a well-known result by now (see [1–4]) that the validity of an L ¹→L ¹ Poincaré inequality of the following form: for all metric balls B⊂B ₀⊂S, implies a variant of representation formula of fractional integral type: for ρ-a.e. x∈B ₀, One of the main results of this paper shows that an L ¹ to L ^q Poincaré inequality for some 0 < q < 1, i.e., for all metric balls B⊂B ₀, will suffice to imply the above representation formula. As an immediate corollary, we can show that the weak-type condition, also implies the same formula. Analogous theorems related to high-order Poincaré inequalities and Sobolev spaces in metric spaces are also proved. Received December 27, 2000, Accepted May 28, 2001