Author
Hammett, Adam

Year
2007

Advisor
Pittel, Boris

Abstract
Two permutations of [n]:={1,2,...,n} are comparable in Bruhat order if one can be obtained from the other by a sequence of transpositions decreasing the number of inversions. Let P(n) be the probability that two independent and uniformly random permutations are comparable in Bruhat order. We demonstrate that P(n) is of order n^{-2} at most, and (0.708)^n at least. We also extend this result to r-tuples of permutations. Namely, if P(n,r) denotes the probability that r independent and uniformly random permutations form an r-long chain in Bruhat order, we demonstrate that P(n,r) is of order n^{-r(r-1)} at most, an exact extension of the case P(n,2)=P(n). For the related "weak order" - when only adjacent transpositions are admissible - we show that P^*(n) is of order (0.362)^n at most, and (H(1)/2)*(H(2)/2)*...*(H(n)/n) at least. Here H(i)=1/1+1/2+....+1/i, and P^*(n) is defined analogously to P(n), but for weak order. Finally, the weak order poset is a lattice, and we study Q(n,r), the probability that r independent and uniformly random permutations have trivial infimum, 12...n. We prove that [Q(n,r)]^{1/n}-->1/q(r), as n tends to infinity. Here, q(r) is the unique (positive) root of the equation 1-z+z^2/(2!)^r+...+(-z)^j/(j!)^r=0, lying in the disk |z|<2.

Thesis
Hammett, Adam Joseph.pdf