Time

Feb 22 2006 - 4:30pm

Location

MW154

Speaker

Adam Hammett (The Ohio State University)

Abstract

Two permutations of [n] are comparable in Bruhat order if one can be obtained from the other by a sequence of transpositions decreasing the number of inversions. There exist some effective rules for checking comparability of two given permutations p and q. Among them is the 0-1 matrix criterion: p <= q iff for each i and j the number of p(1),...,p(i) below j is at least the number of q(1),...,q(i) below j. Using this criterion we show that the total number of pairs (p,q), p <= q, is if order (n!)^2/n^2 at most. Equivalently, if p,q are chosen uniformly at random and independently of each other, then Pr(p<=q) is of order 1/n^2 at most. Numerical experiments indicate that the actual number of these pairs is (n!)^2/n^{2+d} for some d in [0.5,1] so that our upper bound is a qualitative match for the true behavior. This is joint work with Boris Pittel.