The University of Michigan Combinatorics Seminar
Winter 2005
April 1, 4:10-5:00, 3866 East Hall

How frequently are two permutations comparable in Bruhat order?

Boris Pittel

Ohio State University


Two permutations of [n] are comparable in Bruhat order if one can be obtained from another by a series 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 exceeds 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 c(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 c/n^2 at most. By a direct probabilistic argument we prove that Pr(p<=q) is (0.61)^n at least. 0.61 can be increased a bit, but there remains a wide gap between the upper and lower bounds. The numerical experiment leads us to conjecture that Pr(p<=q) is of order n^{-a} exactly, for a close to 2.5. For the weak Bruhat order--when only the adjacent transpositions are admissible--we use the inversion set criterion to prove that P(n):=Pr(p<=q) is submultiplicative, thus showing existence of c*=lim(P(n))^{1/n}. We demonstrate that c* is 0.43 at most. The experiment indicates that c* is close, if not equal to 1/3, but we are still working on a positive lower bound for this limit.

This is joint work with Adam Hammett.