# OhioLINKElectronic Theses & Dissertations Center

Search ETDs:
On comparability of random permutations

2007, Doctor of Philosophy, Ohio State University, Mathematics.
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+z2/(2!)r+…+(-z)j/(j!)r=0, lying in the disk |z|<2.
131 p.