Partial symmetry, reflection monoids and Coxeter groups

This is the first of a series of papers in which we initiate and develop the theory of reflection monoids, motivated by the theory of reflection groups. The main results identify a number of important inverse semigroups as reflection monoids, introduce new examples, and determine their orders.     

On quotients of Coxeter groups under the weak order

We consider quotients of finitely generated Coxeter groups under the weak order. Björner and Wachs proved that every such quotient is a meet semi-lattice, and in the finite case is a lattice [Björner and Wachs, Trans. Amer. Math. Soc. 308 (1988) 1–37]. Our result is that the quotient of an affine Weyl group by the corresponding finite Weyl group is a lattice, and that up to isomorphism, these are the only quotients of infinite Coxeter groups that are lattices. In this paper, we restrict our attention to the non-affine case; the affine case appears in [Waugh, Order 16 (1999) 77–87]. We reduce to the hyperbolic case by an argument using induced subgraphs of Coxeter graphs. Within each quotient, we produce a set of elements with no common upper bound, generated by a Maple program. The number of cases is reduced because the sets satisfy the following conjecture: if a set of elements does not have an upper bound in a particular Coxeter group, then it does not have an upper bound in any Coxeter group whose graph can be obtained from the graph of the original group by increasing edge weights.     

Chains in the Bruhat order

We study a family of polynomials whose values express degrees of Schubert varieties in the generalized complex flag manifold G/B. The polynomials are given by weighted sums over saturated chains in the Bruhat order. We derive several explicit formulas for these polynomials, and investigate their relations with Schubert polynomials, harmonic polynomials, Demazure characters, and generalized Littlewood-Richardson coefficients. In the second half of the paper, we study the classical flag manifold and discuss related combinatorial objects: flagged Schur polynomials, 312-avoiding permutations, generalized Gelfand-Tsetlin polytopes, the inverse Schubert-Kostka matrix, parking functions, and binary trees. A.P. was supported in part by National Science Foundation grant DMS-0201494 and by Alfred P. Sloan Foundation research fellowship. R.S. was supported in part by National Science Foundation grant DMS-9988459.     

Pattern avoidance and the Bruhat order

The structure of order ideals in the Bruhat order for the symmetric group is elucidated via permutation patterns. The permutations with boolean principal order ideals are characterized. These form an order ideal which is a simplicial poset, and its rank generating function is computed. Moreover, the permutations whose principal order ideals have a form related to boolean posets are also completely described. It is determined when the set of permutations avoiding a particular set of patterns is an order ideal, and the rank generating functions of these ideals are computed. Finally, the Bruhat order in types B and D is studied, and the elements with boolean principal order ideals are characterized and enumerated by length.     

Semi-edges, reflections and Coxeter groups

We combine the theory of Coxeter groups, the covering theory of graphs introduced by Malnic, Nedela and Skoviera and the theory of reflections of graphs in order to obtain the following characterization of a Coxeter group:

Let be a -covering of a monopole admitting semi-edges only. The graph is the Cayley graph of a Coxeter group if and only if is regular and any deck transformation in that interchanges two neighboring vertices of acts as a reflection on .

     

Chordal Coxeter groups

A solution of the isomorphism problem is presented for the class of Coxeter groups W that have a finite set of Coxeter generators S such that the underlying graph of the presentation diagram of the system (W,S) has the property that every cycle of length at least four has a chord. As an application, we construct counterexamples to two conjectures concerning the isomorphism problem for Coxeter groups.      

Bruhat order, smooth Schubert varieties, and hyperplane arrangements

The aim of this article is to link Schubert varieties in the flag manifold with hyperplane arrangements. For a permutation, we construct a certain graphical hyperplane arrangement. We show that the generating function for regions of this arrangement coincides with the Poincaré polynomial of the corresponding Schubert variety if and only if the Schubert variety is smooth. We give an explicit combinatorial formula for the Poincaré polynomial. Our main technical tools are chordal graphs and perfect elimination orderings.     

Explicit left orders on free groups extending the lexicographic order on free monoids

For every finitely generated free group, we construct an explicit left order extending the lexicographic order on the free monoid generated by the positive letters. The order is defined by a left, free action on the orbit of 0 of a free group of piecewise linear homeomorphisms of the line. The membership in the positive cone is decidable in linear time in the length of the input word. The positive cone forms a context-free language closed under word reversal.     

Rigidity of Coxeter groups

Let be a Coxeter group acting properly discontinuously and cocompactly on manifolds and such that the fixed point sets of finite subgroups are contractible. Let be a -homotopy equivalence which restricts to a -homeomorphism on the boundary. Under an assumption on the three dimensional fixed point sets, we show that then is -homotopic to a -homeomorphism.     

Sorting orders,subword complexes,Bruhat order and total positivity

In this note we construct a poset map from a Boolean algebra to the Bruhat order which unveils an interesting connection between subword complexes, sorting orders, and certain totally nonnegative spaces. This relationship gives a simple new proof that the proper part of Bruhat order is homotopy equivalent to the proper part of a Boolean algebra — that is, to a sphere. We also obtain a geometric interpretation for sorting orders. We conclude with two new results: that the intersection of all sorting orders is the weak order, and the union of sorting orders is the Bruhat order.     

Reflection groups of geodesic spaces and Coxeter groups

H.S.M. Coxeter showed that a group Γ is a finite reflection group of an Euclidean space if and only if Γ is a finite Coxeter group. In this paper, we define reflections of geodesic spaces in general, and we prove that Γ is a cocompact discrete reflection group of some geodesic space if and only if Γ is a Coxeter group.