MIT Combinatorics Seminar

Statistics on Permutation Groups, Canonical Words and Pattern Avoidance

Yuval Roichman  (BIU and UCSD)

Wednesday, March 16, 2005   4:15 pm    Room 2-338


The number of left to right minima of a permutation is generalized to Coxeter (and closely related) groups, via an interpretation as the number of ``long factors" in canonical expressions of elements in the group.

This statistic is used to determine a covering map, which `lifts' identities on the symmetric group $S_n$ to the alternating group $A_{n+1}$. The covering map is then extended to `lift' known identities on $S_n$ to new identities on $S_{n+q-1}$ for every positive integer $q$, thus yielding $q$-analogues of the known $S_n$ identities.

Equi-distribution identities on certain families of pattern avoiding permutations follow. The cardinalities of subsets of permutations avoiding these patterns are given by extended Stirling and Bell numbers. The dual systems (determined by matrix inversion) have combinatorial realizations via statistics on colored permutations.

Joint with Amitai Regev.