Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


osu1172592365.pdf (519.45 KB)

ETD Abstract Container

Abstract Header

On comparability of random permutations

Hammett, Adam Joseph
http://rave.ohiolink.edu/etdc/view?acc_num=osu1172592365

Abstract Details

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.
Mathematics
Combinatorics; Probability; Bruhat Order; Weak Order; Partially Ordered Sets

Recommended Citations

Citations

  • Hammett, A. J. (2007). On comparability of random permutations [Doctoral dissertation, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1172592365

    APA Style (7th edition)

  • Hammett, Adam. On comparability of random permutations. 2007. Ohio State University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1172592365.

    MLA Style (8th edition)

  • Hammett, Adam. "On comparability of random permutations." Doctoral dissertation, Ohio State University, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=osu1172592365

    Chicago Manual of Style (17th edition)

osu1172592365
553
© 2007, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.