From Bruhat intervals to intersection lattices and a conjecture of Postnikov

We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w∈Sn is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups.A byproduct of this result and its proof is a set of inequalities relating Betti numbers of complexified inversion arrangements to Betti numbers of closed Schubert cells. Another consequence is a simple combinatorial interpretation of the chromatic polynomial of the inversion graph of a permutation which avoids the above patterns.     

Product decompositions of the symmetric group induced by separable permutations

In this paper we consider the rank generating function of a separable permutation π in the weak Bruhat order on the two intervals [id,π] and [π,w₀], where w₀=n,n−1,…,1. We show a surprising result that the product of these two generating functions is the generating function for the symmetric group with the weak order. We then obtain explicit formulas for the rank generating functions on [id,π] and [π,w₀], leading to the rank-symmetry and unimodality of the two graded posets.     

Poisson structures on affine spaces and flag varieties. I. Matrix affine Poisson space

The standard Poisson structure on the rectangular matrix variety Mm,n(C) is investigated, via the orbits of symplectic leaves under the action of the maximal torus T⊂GLm+n(C). These orbits, finite in number, are shown to be smooth irreducible locally closed subvarieties of Mm,n(C), isomorphic to intersections of dual Schubert cells in the full flag variety of GLm+n(C). Three different presentations of the T-orbits of symplectic leaves in Mm,n(C) are obtained: (a) as pullbacks of Bruhat cells in GLm+n(C) under a particular map; (b) in terms of rank conditions on rectangular submatrices; and (c) as matrix products of sets similar to double Bruhat cells in GLm(C) and GLn(C). In presentation (a), the orbits of leaves are parametrized by a subset of the Weyl group Sm+n, such that inclusions of Zariski closures correspond to the Bruhat order. Presentation (b) allows explicit calculations of orbits. From presentation (c) it follows that, up to Zariski closure, each orbit of leaves is a matrix product of one orbit with a fixed column-echelon form and one with a fixed row-echelon form. Finally, decompositions of generalized double Bruhat cells in Mm,n(C) (with respect to pairs of partial permutation matrices) into unions of T-orbits of symplectic leaves are obtained.     

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.     

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.     

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

     

Deformations of permutation representations of Coxeter groups

The permutation representation afforded by a Coxeter group W acting on the cosets of a standard parabolic subgroup inherits many nice properties from W such as a shellable Bruhat order and a flat deformation over ?[q] to a representation of the corresponding Hecke algebra. In this paper we define a larger class of “quasiparabolic” subgroups (more generally, quasiparabolic W-sets), and show that they also inherit these properties. Our motivating example is the action of the symmetric group on fixed-point-free involutions by conjugation.     

Towards the inverse of a word

Let w be a word, i.e., a permutation with repetitions. We present a construction for the inverse of w in the case where w has at most three distinct letters, and indicate steps towards the construction in the general case.     

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.     

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

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.     

Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams

We consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). For general sets of entries, these numbers of matrices are not polynomials in q (Stembridge in Ann. Comb. 2(4):365, 1998); however, when the set of entries is a Young diagram, the numbers, up to a power of q?1, are polynomials with nonnegative coefficients (Haglund in Adv. Appl. Math. 20(4):450, 1998). In this paper, we give a number of conditions under which these numbers are polynomials in q, or even polynomials with nonnegative integer coefficients. We extend Haglund’s result to complements of skew Young diagrams, and we apply this result to the case where the set of entries is the Rothe diagram of a permutation. In particular, we give a necessary and sufficient condition on the permutation for its Rothe diagram to be the complement of a skew Young diagram up to rearrangement of rows and columns. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order.     

A note on scheduling flowshops with flexible stage ordering

We develop an asymptotically optimal heuristic for the m-stage flowshop problem with flexible stage ordering. Our algorithm supplies a job permutation which has the same worst case absolute bound for all possible m! orderings of the m stages. The development of our algorithm is motivated by the observation that it is sometimes beneficial to reverse the processing order in multi-stage manufacturing processes. Our algorithm facilitates the development of a job sequence a priori before the processing order is determined.     

Reduced Decompositions with One Repetition and Permutation Pattern Avoidance

In 2007, Tenner established a connection between pattern avoidance in permutations and the Bruhat order on permutations by showing that the downset of a permutation in the Bruhat order is a Boolean algebra if and only if the permutation is 3412 and 321 avoiding. Tenner conjectured, but did not prove, that if the permutation is 321 avoiding and contains exactly one 3412 pattern, or if the permutation is 3412 avoiding and contains exactly one 321 pattern, then there exists a reduced decomposition with precisely one repetition. This property actually characterizes permutations with precisely one repetition. The goal of this paper is to prove this equivalence as a first step in our program to count permutations with few repetitions of 321 and 3412 and to understand Bruhat downsets by means of pattern avoidance.     

On intersections of conjugacy classes and bruhat cells

For a connected semisimple algebraic group G over an algebraically closed field k and a fixed pair (B, B ^– ) of opposite Borel subgroups of G, we determine when the intersection of a conjugacy class C in G and a double coset BwB ^– is nonempty, where w is in the Weyl group W of G. The question comes from Poisson geometry, and our answer is in terms of the Bruhat order on W and an involution m _C ∈ 2 W associated to C. We prove that the element m _C is the unique maximal length element in its conjugacy class in W, and we classify all such elements in W. For G = SL(n + 1; k), we describe m _C explicitly for every conjugacy class C, and when w ∈ W ≌ S_n+1 is an involution, we give an explicit answer to when C ∩ (BwB) is nonempty.     

On maximal weights of Hadamard matrices

Let $\text{Ω}{}_{\mathrm{n}}$ denote the set of all Hadamard matrices of order n. For $\text{H ? Ω}{}_{\mathrm{n}}$, define the weight of H to be the number of 1's in H and is denoted by w(H). For a subset $\text{Γ ? Ω}{}_{\mathrm{n}}$, define the maximal weight of Γ as w(Γ) = max{w(H) | H?Γ}. Two Hadamard matrices are equivalent if one of them can be transformed to the other by permutation and negation of rows and columns, and the equivalence class containing H is denoted by [H]. In this paper, we shall derive lower bounds for w([H]), which are best possible for n ? 20. We shall also determine the exact value of $\text{w(Ω}{}_{32}\text{)}$.     

Reed-Muller codes and permutation decoding

We show that the first- and second-order Reed-Muller codes, R(1,m) and R(2,m), can be used for permutation decoding by finding, within the translation group, (m−1)- and (m+1)-PD-sets for R(1,m) for m≥5,6, respectively, and (m−3)-PD-sets for R(2,m) for m≥8. We extend the results of Seneviratne [P. Seneviratne, Partial permutation decoding for the first-order Reed-Muller codes, Discrete Math., 309 (2009), 1967-1970].     

On the permutation groups of cyclic codes

We classify the permutation groups of cyclic codes over a finite field. As a special case, we find the permutation groups of non-primitive BCH codes of prime length. In addition, the Sylow p-subgroup of the permutation group is given for many cyclic codes of length p ^m . Several examples are given to illustrate the results.     

Generating indecomposable permutations

An indecomposable permutation π on [n] is one such that π([m])=[m] for no m<n. We consider indecomposable permutations and give a new, inclusive enumerative recurrence for them. This recurrence allows us to generate all indecomposable permutations of length n in transposition Gray code order, in constant amortized time (CAT). We also present a CAT generation algorithm for indecomposable permutations which is based on the Johnson-Trotter algorithm for generating all permutations of length n. The question of whether or not there exists an adjacent transposition Gray code for indecomposable permutations remains open.