Search ETDs:
On comparability of random permutations
Hammett, Adam Joseph

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.
Boris Pittel (Advisor)
131 p.

Recommended Citations

Hide/Show APA Citation

Hammett, A. (2007). On comparability of random permutations. (Electronic Thesis or Dissertation). Retrieved from https://etd.ohiolink.edu/

Hide/Show MLA Citation

Hammett, Adam. "On comparability of random permutations." Electronic Thesis or Dissertation. Ohio State University, 2007. OhioLINK Electronic Theses and Dissertations Center. 25 Sep 2017.

Hide/Show Chicago Citation

Hammett, Adam "On comparability of random permutations." Electronic Thesis or Dissertation. Ohio State University, 2007. https://etd.ohiolink.edu/

Files

osu1172592365.pdf (519.45 KB) View|Download