ON COMPARABILITY OF RANDOM PERMUTATIONS

DISSERTATIO $\mathrm{N}$

Presented in Partial Fulfillment of the Requirements for

the Degree Doctor of Philosophy in the Graduate

School of the Ohio State University

By

Adam Hammett, $\mathrm{B}\mathrm{.}\mathrm{S}$.

$\mathrm{*}\mathrm{*}\mathrm{*}\mathrm{*}$ $\mathrm{*}$

The Ohio State University

2007

Dissertation Committee:

$\mathrm{\mapsto }\mathrm{1}\mathrm{3}\mathrm{3}\mathrm{C}\mathrm{1}\mathrm{b}\mathrm{C}\mathrm{l}\mathrm{b}\mathrm{l}\mathrm{\cup }\mathrm{1}\mathrm{1}\mathrm{\cup }\mathrm{\cup }\mathrm{1}\mathrm{1}\mathrm{1}\mathrm{1}\mathrm{1}\mathrm{1}\mathrm{l}\mathrm{b}\mathrm{b}\mathrm{C}\mathrm{C}$. Approved by

Dr. Boris Pittel, Advisor

Dr. Gerald Edgar

1 $\mathrm{ċ}$.

Advisor

Dr. Akos Seress Graduate Program in

Graduate Program in Mathematics

ABSTRACT

Two permutations of $\mathrm{\left[}\mathit{n}\mathrm{\right]}$ $\mathrm{:}\mathrm{=}\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{}\mathrm{2}\mathrm{,}\mathrm{}\mathrm{\text{...}}\mathrm{,}\mathrm{}\mathit{n}\mathrm{\}}$ are comparable in the Bruhat order if one

can be obtained from the other by a sequence of transpositions decreasing the number

of inversions. We show that the total number of pairs of permutations $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ with

$\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ is of order $\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}\mathrm{/}{\mathit{n}}^{\mathrm{2}}$ at most. Equivalently, if $\mathit{\pi }$, a are chosen uniformly at

random and independently of each other, then $\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right)}$ is of order ${\mathit{n}}^{\mathrm{-}\mathrm{2}}$ at most. By

a direct probabilistic argument we prove $\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right)}$ is of order $\mathrm{(}\mathrm{0}\mathrm{.}\mathrm{7}\mathrm{0}\mathrm{8}{\mathrm{)}}^{\mathit{n}}$ at least, so

that there is currently a wide qualitative gap between the upper and lower bounds.

Next, emboldened by a connection with Ferrers diagrams and plane partitions

implicit in Bressoud's book [13], we return to the Bruhat order upper bound and show

that for $\mathit{n}$ permutations ${\mathit{\pi }}_{\mathrm{1}}$, $\mathrm{\text{...}}$, ${\mathit{\pi }}_{\mathit{r}}$ selected independently and uniformly at random,

$\mathit{P}\mathrm{\left(}{\mathit{\pi }}_{\mathrm{1}}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{\text{...}}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{\pi }}_{\mathit{r}}\mathrm{\right)}\mathrm{=}\mathit{O}\mathrm{\left(}{\mathit{n}}^{\mathrm{-}\mathit{r}\mathrm{(}\mathit{r}\mathrm{-}\mathrm{1}\mathrm{)}}\mathrm{\right)}$,

thus providing an extension of our result for pairs of permutations to chains of length

$\mathit{r}\mathrm{>}\mathrm{2}$.

Turning to the related weak order $\mathrm{\text{"}}\mathrm{\prec }\mathrm{-}$"- when only adjacent transpositions are

admissible - we use a non-inversion set criterion to prove that ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}\mathrm{:}\mathrm{=}\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{\prec }}\mathit{\sigma }\mathrm{\right)}$ is

submultiplicative, thus showing existence of $\mathit{\rho }\mathrm{=}\lim \sqrt[\mathit{n}]{{\mathit{P}}_{\mathit{n}}^{\mathrm{*}}}$. We demonstrate that $\mathit{\rho }$

is 0.362 at most. Moreover, we prove the lower bound ${{\displaystyle \prod }}_{\mathit{i}\mathrm{=}\mathrm{1}}^{\mathit{n}}\mathrm{\left(}\mathit{H}\mathrm{\right(}\mathit{i}\mathrm{)}\mathrm{/}\mathit{i}\mathrm{)}$ for ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}$, where

ii

$\mathit{H}\mathrm{\left(}\mathit{i}\mathrm{\right)}\mathrm{:}\mathrm{=}{{\displaystyle \sum }}_{\mathit{j}\mathrm{=}\mathrm{1}}^{\mathit{i}}\mathrm{1}\mathrm{/}\mathit{j}$. In light of numerical experiments, we conjecture that for each

order the upper bounds for permutation-pairs are qualitatively close to the actual

behavior. We believe that extensions to $\mathit{r}$-chains similar to that for the Bruhat order

upper bound can be made for our other bounds in each order, and are presently

working in this direction.

Finally, the weak order poset happens to be a lattice, and we study some properties

of its infimums and supremums. Namely, we prove that the number of r-tuples

$\mathrm{(}{\mathit{\pi }}_{\mathrm{1}}$ , . . . ' ${\mathit{\pi }}_{\mathit{r}}\mathrm{)}$ of $\mathit{n}$-permutations with minimal infimum, 12 $\mathrm{\text{...}}$ $\mathit{n}$, asymptotically equals

$\mathrm{-}\frac{\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathit{r}}}{{\mathit{h}}_{\mathit{r}}^{\mathrm{\prime }}\mathrm{\left(}{\mathit{z}}^{\mathrm{*}}\mathrm{\right)}\mathrm{(}{\mathit{z}}^{\mathrm{*}}{\mathrm{)}}^{\mathit{n}\mathrm{+}\mathrm{1}}}$, $\mathit{r}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{2}$, $\mathit{n}$ $\mathrm{\to }\mathrm{\infty }$. (1)

Here, ${\mathit{z}}^{\mathrm{*}}\mathrm{=}{\mathit{z}}^{\mathrm{*}}\mathrm{\left(}\mathit{r}\mathrm{\right)}\mathrm{\in }\mathrm{(}\mathrm{1}\mathrm{,}\mathrm{}\mathrm{2}\mathrm{)}$ is the unique (positive) root of the equation

${\mathit{h}}_{\mathit{r}}\mathrm{\left(}\mathit{z}\mathrm{\right)}\mathrm{:}\mathrm{=}{{\displaystyle \sum }}_{\mathit{j}\mathrm{\ge }\mathrm{0}}\frac{\mathrm{(}\mathrm{-}\mathrm{1}{\mathrm{)}}^{\mathit{j}}}{\mathrm{(}\mathit{j}\mathrm{!}{\mathrm{)}}^{\mathit{r}}}{\mathit{z}}^{\mathit{j}}\mathrm{=}\mathrm{0}$

within the disk $\mathrm{\left|}\mathit{z}\mathrm{\right|}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{2}$. Moreover, (1) is also the asymptotic number of $\mathit{r}$-tuples with

maximal supremum, $\mathit{n}\mathrm{(}\mathit{n}\mathrm{}\mathrm{-}\mathrm{1}\mathrm{)}$ $\mathrm{\text{...}}\mathrm{1}$.

iii

To my wife, Rachael, for her unending suppport.

iv

ACKNOWLEDGMENTS

First and foremost, I wish to thank my advisor, Boris Pittel. Our collaboration was

quite intensive on this research project, and without his countless suggestions and

endless encouragement, none of these results would have materialized. He is truly an

outstanding example of what a mentor should be.

This work was inspired in large part by a thought-provoking talk Mark Skandera

gave at the MIT Combinatorics Conference honoring Richard Stanley's $\mathrm{6}{\mathrm{0}}^{\mathrm{t}\mathrm{h}}$ birthday.

We are grateful to Mark for an enlightening follow-up discussion of comparability

criteria for the Bruhat order. We thank Sergey Fomin for encouragement and for

introducing us to an instrumental notion of the permutation-induced poset, and also

for many insightful suggestions regarding the history of Bruhat order. Without Ed

Overman's invaluable guidance we would not have been able to obtain our numerical

results. Craig Lennon gave us an idea for proving an exponential lower bound in

the case of Bruhat order. We thank $\mathrm{M}\mathrm{i}\mathrm{k}\mathrm{l}\mathrm{6}\mathrm{s}$ $\mathrm{B}\mathrm{6}\mathrm{n}\mathrm{a}$ for his interest in this work and

for drawing our attention to the lower bound for the number of linear extensions in

Richard Stanley's book.

$\mathrm{v}$

VITA

April 28, 1979. . . . . . . . . . . . . . . . . . . . . . . . . Born - Santa Maria, CA

1997-2001 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Undergraduate,

Westmont College - Santa Barbara, CA

2001 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . $\mathrm{B}\mathrm{.}\mathrm{S}$. in Mathematics,

Westmont College

2001-Present . . . . . . . . . . . . . . . . . . . . . . . . . . Graduate Teaching Associate,

The Ohio State University

FIELDS OF STUDY

Major Field: Mathematics

Specialization: Combinatorial Probability

vi

TABLE OF CONTENTS

Abstract ii

Dedication . 1v

Acknowledgments . $\mathrm{v}$

Vita vi

List of Figures $\mathrm{x}$

List of Tables xi

CHAPTER PAGE

1 Introduction 1

1.1 Bruhat Order, Preliminaries 1

1.2 Main Results Related to the Bruhat Order 5

1.3 Weak Order, Preliminaries 7

1.4 Main Results Related to the Weak Order 8

2The Proof of the Bruhat Order Upper Bound 14

2.1 A Necessary Condition for Bruhat Comparability 14

2.2 A Probabilistic Simplification 21

2.3 Asymptotics 23

3The Proof of the Bruhat Order Lower Bound . 26

3.1 A Sufficient Condition for Bruhat Comparability 26

3.2 A Reduction to Uniforms 29

3.3 An Algorithm to Maximize the Bound 34

vii

4

An Extension to Chains in Bruhat Order

39

4.1 The General Setup . 39

4.2 A Tractable Necessary Condition 41

4.3 The Core Counting Problem 42

4.4 A Probabilistic Simplification 56

4.5 Asymptotics 57

5Some Properties of the Weak Ordering 62

5.1 A Criterion for Weak Comparability 62

5.2 Submultiplicativity of ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}$ 65

6 The Proof of the Weak Order Upper Bound 67

6.1 A Necessary Condition for Weak Comparability 67

6.2 A Reduction to Uniforms 69

6.3 An Algorithm to Minimize the Bound 71

7The Proof of the Weak Order Lower Bound 75

7.1 A Formula for $\mathit{P}\mathrm{\left(}{\mathit{E}}_{\mathit{i}}\mathrm{\right(}\mathit{\pi }\mathrm{\left)}\underset{\mathrm{‾}}{\mathrm{\supset }}{\mathit{E}}_{\mathit{i}}\mathrm{\right(}\mathit{\sigma }\mathrm{\left)}\mathrm{\right)}$ . . 75

7.2 Positive Correlation of the Events $\mathrm{\left\{}{\mathit{E}}_{\mathit{i}}\mathrm{\right(}\mathit{\pi }\mathrm{\left)}\underset{\mathrm{‾}}{\mathrm{\supset }}{\mathit{E}}_{\mathit{i}}\mathrm{\right(}\mathit{\sigma }\mathrm{\left)}\mathrm{\right\}}$ 77

7.3 Linear Extensions of Arbitrary Finite Posets 81

8Numerics . 83

8.1 Bruhat Order Numerics 83

8.2 Weak Order Numerics 85

9On Infs and Sups in the Weak Order Lattice 89

9.1 A Connection with Complete, Directed, Acyclic Graphs 89

9.2 Computing Infs and Sups in the Weak Order Lattice 93

9.3 Some Equivalent Criteria for $\inf \mathrm{\{}{\mathit{\pi }}_{\mathrm{1}}$ , . . . ' ${\mathit{\pi }}_{\mathit{r}}\mathrm{\}}\mathrm{=}\mathrm{1}\mathrm{2}$ $\mathrm{\text{...}}$ $\mathit{n}$ 96

9.4 Submultiplicativity Again 99

9.5 Sharp Asymptotics of ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}$ . 1Ot

9.5.1 Step 1: An Exact Formula for ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}$ lai

9.5.2 Step 2: A Generating Function for ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}\mathrm{.}$. 105

9.5.3 Step 3: Asymptotics 108

Vlll

10

Open Problems

114

10.1 The Problems 114

Bibliography 115

IX

LIST OF FIGURES

FIGURE PAGE

1.1 The Bruhat order on ${\mathit{S}}_{\mathrm{3}}$ and ${\mathit{S}}_{\mathrm{4}}$. 2

1.2 Superimposing $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and $\mathit{M}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ to form $\mathit{M}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$. 5

1.3 The permutation-induced poset ${\mathrm{7}}^{\mathrm{\supset }}\mathrm{\left(}\mathrm{2}\mathrm{1}\mathrm{4}\mathrm{3}\mathrm{\right)}$. $\mathrm{1}\mathrm{0}$

$\mathrm{2}\mathrm{.}\mathrm{1}$ Finding a necessary condition for $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$. 16

2.2 Selection of first $\mathit{m}\mathrm{=}{\mathit{m}}_{\mathrm{1}}$ ( $\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}\mathit{m}$ resp.) rows (columns resp.) in

corners to support $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$. 21

3.1 ${\mathit{G}}_{\mathrm{5}}$ and an emboldened subgrid C. 27

3.2 Deletion of 2 largest elements of $\mathit{\pi }$, $\mathit{\sigma }$, and its affect on C. . 28

4.1 Finding a necessary condition for ${\mathit{\pi }}_{\mathrm{1}}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{\text{...}}$ $\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{\pi }}_{\mathit{r}}$. 43

4.2 A non-intersecting nest of 7 lattice paths. 46

4.3 An intersecting nest of 7 lattice paths. 47

4.4 "Swapping" the tails in Figure 4.3. 49

8.1 Experimental determination of the exponent $\mathrm{-}\mathit{a}$ in the asymptotic

equation ${\mathit{P}}_{\mathit{n}}\mathrm{\sim }\mathit{c}{\mathit{n}}^{\mathrm{-}\mathit{a}}$. 85

8.2 Experimental determination of the ratio $\mathit{\rho }$ in the asymptotic equation

${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}\mathrm{\sim }\mathit{c}{\mathit{\rho }}^{\mathit{n}}$. 86

$\mathrm{x}$

LIST OF TABLES

TABLE PAGE

3.1 Exact computation of ${\mathit{N}}_{\mathit{k}}$ for smallish $\mathit{k}$. 37

6.1 Exact computation of ${\mathit{N}}_{\mathit{k}}^{\mathrm{*}}$ for smallish $\mathit{k}$. 74

8.1 Computer simulation data for ${\mathit{P}}_{\mathit{n}}$. 84

8.2 Exact computation of ${\mathit{P}}_{\mathit{n}}$ for smallish $\mathit{n}$. 84

8.3 Computer simulation data for ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}$. 87

8.4 Exact computation of ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}$ for smallish $\mathit{n}$. 87

8.5 Our theoretical lower bound for ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}$ applied for smallish $\mathit{n}$. 88

Xi

(JIAPTER 1

INTRODUCTION

In this chapter, we present the fundamental ideas necessary to understand the ma-

terial in subsequent chapters. We also state the main results to be proved in this

dissertation. It is assumed that the reader has some familiarity with probability the-

ory and combinatorics. A good graduate-level introduction to these subjects can be

found, for instance, in Billingsley [4] and Stanley's volumes on enumerative combina-

torics, [46] and [47].

1.1 Bruhat Order, Preliminaries

Let $\mathit{n}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{1}$ be an integer. Two permutations of $\mathrm{\left[}\mathit{n}\mathrm{\right]}$ $\mathrm{:}\mathrm{=}\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{}\mathrm{\text{...}}\mathrm{,}\mathrm{}\mathit{n}\mathrm{\}}$ are comparable in the

Bruhat order if one can be obtained from the other by a sequence of transpositions of

pairs of elements forming an inversion. Here is a precise definition of the Bruhat order

on the set of permutations ${\mathit{S}}_{\mathit{n}}$ (see [46, p. 172, ex. 75. $\mathrm{a}\mathrm{.}\mathrm{]}$, Humphreys [30, p. 119]).

If $\mathit{\omega }$ $\mathrm{=}\mathit{\omega }\mathrm{\left(}\mathrm{1}\mathrm{\right)}$ $\mathrm{\text{...}}$ $\mathit{\omega }\mathrm{\left(}\mathit{n}\mathrm{\right)}$ $\mathrm{\in }{\mathit{S}}_{\mathit{n}}$, then a reduction of $\mathit{\omega }$ is a permutation obtained from $\mathit{\omega }$

by interchanging some $\mathit{\omega }$ $\mathrm{\left(}\mathit{i}\mathrm{\right)}$ with some $\mathit{\omega }$ $\mathrm{\left(}\mathit{j}\mathrm{\right)}$ provided $\mathit{i}\mathrm{<}\mathit{j}$ and $\mathit{\omega }$ $\mathrm{\left(}\mathit{i}\mathrm{\right)}\mathrm{>}\mathit{\omega }$ $\mathrm{\left(}\mathit{j}\mathrm{\right)}$. We say

that $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ in the Bruhat order if there is a chain $\mathit{\sigma }\mathrm{=}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\to }{\mathit{\omega }}_{\mathrm{2}}\mathrm{\to }\mathrm{\text{...}}\mathrm{\to }{\mathit{\omega }}_{\mathit{s}}\mathrm{=}\mathit{\pi }$, where

each ${\mathit{\omega }}_{\mathit{t}}$ is a reduction of ${\mathit{\omega }}_{\mathit{t}\mathrm{-}\mathrm{1}}$. The number of inversions in ${\mathit{\omega }}_{\mathit{t}}$ strictly decreases with $\mathit{t}$.

1

4321

321

312

132

123

1234

Figure 1.1: The Bruhat order on ${\mathit{S}}_{\mathrm{3}}$ and ${\mathit{S}}_{\mathrm{4}}$.

Indeed, one can show that if ${\mathit{\omega }}_{\mathrm{2}}$ is a reduction of ${\mathit{\omega }}_{\mathrm{1}}$ via the interchange ${\mathit{\omega }}_{\mathrm{1}}\mathrm{\left(}\mathit{i}\mathrm{\right)}\mathrm{\leftrightarrow }{\mathit{\omega }}_{\mathrm{1}}\mathrm{\left(}\mathit{j}\mathrm{\right)}$,

$\mathit{i}\mathrm{<}\mathit{j}$, then

$\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{\left(}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\right)}\mathrm{=}\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{\left(}{\mathit{\omega }}_{\mathrm{2}}\mathrm{\right)}\mathrm{+}\mathrm{2}\mathit{N}\mathrm{\left(}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\right)}\mathrm{+}\mathrm{1}$,

$\mathit{N}\mathrm{\left(}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\right)}\mathrm{:}\mathrm{=}\mathrm{\left|}\mathrm{\right\{}\mathit{k}\mathrm{}\mathrm{:}\mathrm{}\mathit{i}\mathrm{<}\mathit{k}\mathrm{<}\mathit{j}\mathrm{,}\mathrm{}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\left(}\mathit{i}\mathrm{\right)}\mathrm{>}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\left(}\mathit{k}\mathrm{\right)}\mathrm{>}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\left(}\mathit{j}\mathrm{\right)}\mathrm{\left\}}\mathrm{\right|}$;

here $\mathrm{i}\mathrm{n}\mathrm{v}\mathrm{\left(}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\right)}$, say, is the number of inversions in ${\mathit{\omega }}_{\mathrm{1}}$ (see Björner and Brenti [6]). Figure

1.1 illustrates this poset on ${\mathit{S}}_{\mathrm{3}}$ and ${\mathit{S}}_{\mathrm{4}}$. The Bruhat order notion can be extended

to other Coxeter groups (see Björner [5], Deodhar [20], and [6, p. 63] for historical

background), but we will be dealing with the symmetric group ${\mathit{S}}_{\mathit{n}}$ only.

The definition of the Bruhat order is very transparent, and yet deciding for given $\mathit{\pi }$, a

2

whether $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ from the definition is computationally difficult, even for smallish $\mathit{n}$.

Fortunately, there exist efficient algorithms for checking Bruhat comparability, which

can all be traced back to an algorithmic comparability criterion due to Ehresmann

(1934) [22] (see also Knuth [34], Björner and Brenti [6]). The Ehresmann "tableau

criterion" states that $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ if and only if ${\mathit{\pi }}_{\mathit{i}\mathrm{,}\mathit{j}}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{\sigma }}_{\mathit{i}\mathrm{,}\mathit{j}}$ for all $\mathrm{1}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{i}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{j}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{n}$ $\mathrm{-}\mathrm{1}$, where

${\mathit{\pi }}_{\mathit{i}\mathrm{,}\mathit{j}}$ and ${\mathit{\sigma }}_{\mathit{i}\mathrm{,}\mathit{j}}$ are the i-th entry in the increasing rearrangement of $\mathit{\pi }\mathrm{\left(}\mathrm{1}\mathrm{\right)}$ , . . . , $\mathit{\pi }\mathrm{\left(}\mathit{j}\mathrm{\right)}$

and of a(1) , . . . ' $\mathit{\sigma }\mathrm{\left(}\mathit{j}\mathrm{\right)}$. These arrangements form two staircase tableaux, hence the

term tableau criterion" For example, 41523 $\mathrm{>}$ 21534 is verified by element-wise

comparisons of the two tableaux

12451235

14 5 1 2 5

1412

4 2

Also, it is well-known that Ehresmann's criterion is equivalent to the $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix

criterion. It involves comparing the number of Fs contained in certain submatrices

of the $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-permutation matrices representing $\mathit{\pi }$ and a (see $\mathrm{B}\mathrm{6}\mathrm{n}\mathrm{a}\mathrm{\left[}\mathrm{1}\mathrm{0}\mathrm{\right]}$, [6]). Later,

Björner and Brenti [7] were able to improve on the result of [22], giving a tableau

criterion that requires fewer operations. Very recently, Drake, Gerrish and Skandera

[21] have found two new comparability criteria, involving totally nonnegative poly-

nomials and the Schur functions respectively. We are aware of other criteria (see [5],

Fulton [25, pp. 173-177], Lascoux and Schiitzenberger [36], [20] $\mathrm{)}$, but we found the

$\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix and Ehresmann criteria most amenable to probabilistic study.

3

The $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix criterion for Bruhat order on ${\mathit{S}}_{\mathit{n}}$ says that for $\mathit{\pi }$, $\mathit{\sigma }\mathrm{\in }{\mathit{S}}_{\mathit{n}}$, $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ if

and only if for all $\mathit{i}$, $\mathit{j}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{n}$, the number of $\mathit{\pi }\mathrm{\left(}\mathrm{1}\mathrm{\right)}$ , . . . , $\mathit{\pi }\mathrm{\left(}\mathit{i}\mathrm{\right)}$ that are at most $\mathit{j}$ exceeds

(or equals) the number of a(1), . . . ' a(i) that are at most $\mathit{j}$ (see [11] for this version).

It is referred to as the $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix criterion because of the following recasting of this

condition: let $\mathit{M}$ $\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$, $\mathit{M}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ be the permutation matrices corresponding to $\mathit{\pi }$, $\mathit{\sigma }$, so

that for instance the $\mathrm{(}\mathit{i}\mathrm{,}\mathrm{}\mathit{j}\mathrm{)}$-entry of $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ is 1 if $\mathit{\pi }\mathrm{\left(}\mathit{j}\mathrm{\right)}\mathrm{=}\mathit{i}$ and 0 otherwise. Here, we

are labeling columns 1, 2, . . . ' $\mathit{n}$ when reading from left to right, and rows are labeled

1, 2, . . . ' $\mathit{n}$ when reading from bottom to top so that this interpretation is like placing

ones at points $\mathrm{(}\mathit{i}\mathrm{,}\mathrm{}\mathit{\pi }\mathrm{(}\mathit{i}\mathrm{\left)}\mathrm{\right)}$ of the $\mathit{n}$ $\mathrm{\times }\mathit{n}$ integer lattice and zeroes elsewhere. Denoting

submatrices of $\mathit{M}$ ($\mathrm{ċ}$) corresponding to rows I and columns $\mathit{J}$ by $\mathit{M}$ $\mathrm{(}\mathrm{ċ}{\mathrm{)}}_{\mathit{I}\mathrm{,}\mathit{J}}$, this criterion

says that $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ if and only if for all $\mathit{i}$, $\mathit{j}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{n}$, the number of ones in $\mathit{M}$ $\mathrm{(}\mathit{\pi }{\mathrm{)}}_{\mathrm{\left[}\mathit{i}\mathrm{\right]}\mathrm{,}\mathrm{\left[}\mathit{j}\mathrm{\right]}}$ is at

least the number of ones in $\mathit{M}$ $\mathrm{(}\mathit{\sigma }{\mathrm{)}}_{\mathrm{\left[}\mathit{i}\mathrm{\right]}\mathrm{,}\mathrm{\left[}\mathit{j}\mathrm{\right]}}$ (see [21] for this version).

An effective way of visualizing this criterion is to imagine the matrices $\mathit{M}$ $\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and

$\mathit{M}$ $\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ as being superimposed on one another into a single matrix, $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$, with the

ones for $\mathit{M}$ $\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ represented by $\mathrm{\times }\mathrm{\text{'}}\mathrm{s}\mathrm{\left(}\mathrm{\text{"}}\mathrm{c}\mathrm{r}\mathrm{o}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{s}\mathrm{\text{"}}\mathrm{\right)}$, the ones for $\mathit{M}$ $\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ by $\mathrm{\circ }$ 's $\mathrm{\left(}\mathrm{\text{"}}\mathrm{b}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{s}\mathrm{\text{"}}\mathrm{\right)}$

and the zeroes for both by empty entries. Note that some entries of a $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ may

be occupied by both a cross and a ball. Then the $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix criterion says that

$\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ if and only if every southwest submatrix of $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ contains at least as many

crosses as balls. Here, in the notation above, a southwest submatrix is a submatrix

$\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }{\mathrm{)}}_{\mathrm{\left[}\mathit{i}\mathrm{\right]}\mathrm{,}\mathrm{\left[}\mathit{j}\mathrm{\right]}}$ of $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ for some $\mathit{i}$, $\mathit{j}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{n}$. It is clear that we could also check

$\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ by checking that crosses are at least as numerous as balls in every northeast

submatrix of $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$. Likewise, $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ if and only if balls are at least as numerous

as crosses in every northwest submatrix of $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$, or similarly balls are at least

4

$\mathit{M}\mathrm{\left(}\mathit{0}\mathrm{\right)}$

Figure 1.2: Superimposing $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and $\mathit{M}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ to form $\mathit{M}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$.

as numerous as crosses in every southeast submatrix of $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$. Parts of all four

of these equivalent conditions will be used in our proofs. As a quick example, with

$\mathit{\pi }\mathrm{=}$ 21534 and $\mathit{\sigma }\mathrm{=}\mathrm{4}\mathrm{1}\mathrm{5}\mathrm{2}\mathrm{3}$, $\mathit{\pi }\mathrm{<}\mathit{\sigma }$ is checked by examining southwest submatrices of

$\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ in Figure 1.2. Also, the superimposing of $\mathit{M}$ $\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ with $\mathit{M}$ $\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ to form $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$

is illustrated in this figure.

1.2 Main Results Related to the Bruhat Order

In this dissertation, we use the $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix and the Ehresmann criteria to obtain

upper and lower bounds for the number of pairs $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ with $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$.

5

Theorem 1.2.1. Let $\mathit{n}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{1}$ be an integer, and let $\mathit{\pi }$, $\mathit{\sigma }\mathrm{\in }{\mathit{S}}_{\mathit{n}}$ be selected independently

and uniformly at random. Then there exist universal constants ${\mathit{c}}_{\mathrm{1}}$, ${\mathit{c}}_{\mathrm{2}}\mathrm{>}\mathrm{0}$ such that

${\mathit{c}}_{\mathrm{1}}\mathrm{(}\mathrm{0}\mathrm{.}\mathrm{7}\mathrm{0}\mathrm{8}{\mathrm{)}}^{\mathit{n}}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{P}\mathrm{(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{)}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{c}}_{\mathrm{2}}\mathrm{/}{\mathit{n}}^{\mathrm{2}}$

Equivalently, the number of pairs $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ with $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$ is sandwiched between the

counts ${\mathit{c}}_{\mathrm{1}}\mathrm{(}\mathrm{0}\mathrm{.}\mathrm{7}\mathrm{0}\mathrm{8}{\mathrm{)}}^{\mathit{n}}\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}$ and ${\mathit{c}}_{\mathrm{2}}{\mathit{n}}^{\mathrm{-}\mathrm{2}}\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}$. The lower bound follows from a sufficient

condition derived from the $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix criterion, and a computer-aided tabulation

of an attendant function of a smallish integer argument. Empirical estimates based on

generating pairs of random permutations suggest that $\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right)}$ is of order ${\mathit{n}}^{\mathrm{-}\mathrm{(}\mathrm{2}\mathrm{+}\mathit{\delta }\mathrm{)}}$,

for $\mathit{\delta }$ close to 0.5 from above. So apparently it is the upper bound which comes close

to the true proportion $\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right)}$. It is certain that the constant 0.708 can be further

improved, but we do not know if our method could be extended to deliver a lower

bound $\mathrm{(}\mathrm{1}\mathrm{}\mathrm{-}\mathit{o}\mathrm{(}\mathrm{1}\mathrm{)}{\mathrm{)}}^{\mathit{n}}$. A lower bound ${\mathit{n}}^{\mathrm{-}\mathit{a}}$, a qualitative match of the upper bound, seems

out of sight presently.

A deeper insight reveals a more general result, related to chains of length $\mathit{r}$ in Bruhat

order, once we realize some connections with MacMahon's formula [13] for counting

plane partitions contained in an $\mathit{r}\mathrm{\times }\mathit{s}\mathrm{\times }\mathit{t}$ box. Without going into much unnecessary

detail here, one can visualize a plane partition as stacks of unit cubes pushed into a

corner. The k-th Ehresmann condition contains a clear connection between Bruhat

order on permutations and counting combinatorial objects related to plane partitions,

namely non-intersecting lattice paths, a notion we will make precise later on. A closer

look at our methods for permutation-pairs in the spirit of Gessel and Viennot's work

6

[26] implies an extension of Theorem 1.2.1, upper bound, from pairs of permutations

to r-tuples:

Theorem 1.2.2. Let ${\mathit{\pi }}_{\mathrm{1}}$, ..., ${\mathit{\pi }}_{\mathit{r}}\mathrm{\in }{\mathit{S}}_{\mathit{n}}$ be selected independently and uniformly at

random. Then there exists a uniform constant c $\mathrm{>}\mathrm{0}$ such that

$\mathit{P}\mathrm{\left(}{\mathit{\pi }}_{\mathrm{1}}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{\text{...}}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{\pi }}_{\mathit{r}}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{c}\mathrm{/}{\mathit{n}}^{\mathit{r}\mathrm{(}\mathit{r}\mathrm{-}\mathrm{1}\mathrm{)}}$.

Note that this result implies that there are at most $\mathit{c}{\mathit{n}}^{\mathrm{-}\mathit{r}\mathrm{(}\mathit{r}\mathrm{-}\mathrm{1}\mathrm{)}}$ $\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathit{r}}$ length $\mathit{r}$ chains in

the Bruhat order poset.

1.3 Weak Order, Preliminaries

Then we turn to the modified order on ${\mathit{S}}_{\mathit{n}}$, the rveak order $\mathrm{\text{"}}\mathrm{\prec }\mathrm{-}$" Here $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{\prec }}\mathit{\sigma }$ if there

is a chain $\mathit{\sigma }\mathrm{=}{\mathit{\omega }}_{\mathrm{1}}\mathrm{\to }{\mathit{\omega }}_{\mathrm{2}}\mathrm{\to }\mathrm{\text{...}}\mathrm{\to }{\mathit{\omega }}_{\mathit{s}}\mathrm{=}\mathit{\pi }$, where each ${\mathit{\omega }}_{\mathit{t}}$ is a simple reduction of ${\mathit{\omega }}_{\mathit{t}\mathrm{-}\mathrm{1}}$,

i.e. obtained from ${\mathit{\omega }}_{\mathit{t}\mathrm{-}\mathrm{1}}$ by transposing two adjacent elements ${\mathit{\omega }}_{\mathit{t}\mathrm{-}\mathrm{1}}\mathrm{\left(}\mathit{i}\mathrm{\right)}$, ${\mathit{\omega }}_{\mathit{t}\mathrm{-}\mathrm{1}}\mathrm{(}\mathit{i}\mathrm{+}\mathrm{1}\mathrm{)}$ with

${\mathit{\omega }}_{\mathit{t}\mathrm{-}\mathrm{1}}\mathrm{\left(}\mathit{i}\mathrm{\right)}\mathrm{>}{\mathit{\omega }}_{\mathit{t}\mathrm{-}\mathrm{1}}\mathrm{(}\mathit{i}\mathrm{+}\mathrm{1}\mathrm{)}$. Since at each step the number of inversions decreases by 1,

all chains connecting a and $\mathit{\pi }$ have the same length. Alternatively, there is a simple

non-inversion (resp. inversion) set criterion, contained in Berge [3], we can use to

check $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{\prec }}\mathit{\sigma }$. Indeed, given $\mathit{\omega }\mathrm{\in }{\mathit{S}}_{\mathit{n}}$ introduce the set of non-inversions of $\mathit{\omega }$:

$\mathit{E}\mathrm{\left(}\mathit{\omega }\mathrm{\right)}\mathrm{=}\mathrm{\left\{}\mathrm{\right(}\mathit{i}\mathrm{,}\mathrm{}\mathit{j}\mathrm{)}\mathrm{}\mathrm{:}\mathrm{}\mathit{i}\mathrm{<}\mathit{j}\mathrm{,}\mathrm{}{\mathit{\omega }}^{\mathrm{-}\mathrm{1}}\mathrm{(}\mathit{i}\mathrm{)}\mathrm{<}{\mathit{\omega }}^{\mathrm{-}\mathrm{1}}\mathrm{(}\mathit{j}\mathrm{\left)}\mathrm{\right\}}$.

Similarly, for $\mathit{\omega }\mathrm{\in }{\mathit{S}}_{\mathit{n}}$ we introduce the set of inversions of $\mathit{\omega }$:

7

${\mathit{E}}^{\mathrm{*}}\mathrm{\left(}\mathit{\omega }\mathrm{\right)}\mathrm{=}\mathrm{\left\{}\mathrm{\right(}\mathit{i}\mathrm{,}\mathrm{}\mathit{j}\mathrm{)}\mathrm{}\mathrm{:}\mathrm{}\mathit{i}\mathrm{>}\mathit{j}\mathrm{,}\mathrm{}{\mathit{\omega }}^{\mathrm{-}\mathrm{1}}\mathrm{(}\mathit{i}\mathrm{)}\mathrm{<}{\mathit{\omega }}^{\mathrm{-}\mathrm{1}}\mathrm{(}\mathit{j}\mathrm{\left)}\mathrm{\right\}}$.

Then, for given $\mathit{\pi }$, $\mathit{\sigma }\mathrm{\in }{\mathit{S}}_{\mathit{n}}$, we have $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{\prec }}\mathit{\sigma }$ if and only if $\mathit{E}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{\supset }}\mathit{E}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ (equivalently

${\mathit{E}}^{\mathrm{*}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{\subset }}{\mathit{E}}^{\mathrm{*}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}\mathrm{)}$. Note that $\mathit{\omega }\mathrm{\in }{\mathit{S}}_{\mathit{n}}$ is uniquely determined by its $\mathit{E}\mathrm{\left(}\mathit{\omega }\mathrm{\right)}$ (resp. its

${\mathit{E}}^{\mathrm{*}}\mathrm{\left(}\mathit{\omega }\mathrm{\right)}\mathrm{)}$.

It turns out that the poset $\mathrm{(}{\mathit{S}}_{\mathit{n}}\mathrm{,}\underset{\mathrm{‾}}{\mathrm{\prec }}\mathrm{)}$ is a lattice (see [3]). Indeed, given ${\mathit{\pi }}_{\mathrm{1}}$, $\mathrm{\text{...}}$, ${\mathit{\pi }}_{\mathit{r}}\mathrm{\in }{\mathit{S}}_{\mathit{n}}$,

there is an efficient way to compute $\mathit{E}\mathrm{\left(}\inf \mathrm{\right\{}{\mathit{\pi }}_{\mathrm{1}}\mathrm{,}\mathrm{}\mathrm{\text{...}}\mathrm{,}\mathrm{}{\mathit{\pi }}_{\mathit{r}}\mathrm{\left\}}\mathrm{\right)}$ (resp. ${\mathit{E}}^{\mathrm{*}}\mathrm{\left(}\sup \mathrm{\right\{}{\mathit{\pi }}_{\mathrm{1}}$ , . . . , ${\mathit{\pi }}_{\mathit{r}}\mathrm{\}}$))

from the set ${{\displaystyle \cup }}_{\mathit{i}\mathrm{=}\mathrm{1}}^{\mathit{r}}\mathit{E}\mathrm{\left(}{\mathit{\pi }}_{\mathit{i}}\mathrm{\right)}$ (resp. ${{\displaystyle \cup }}_{\mathit{i}\mathrm{=}\mathrm{1}}^{\mathit{r}}\mathit{E}$ " ( ${\mathit{\pi }}_{\mathit{i}}$ )). We will see precisely how to do this later.

1.4 Main Results Related to the Weak Order

We prove the following probabilistic result for weak order comparability:

Theorem 1.4.1. Let $\mathit{\pi }$, $\mathit{\sigma }\mathrm{\in }{\mathit{S}}_{\mathit{n}}$ be selected independently and uniformly at random,

and let ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}\mathrm{:}\mathrm{=}\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{\prec }}\mathit{\sigma }\mathrm{\right)}$. Then ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}$ is submultiplicative, $\mathit{i}\mathrm{.}\mathit{e}$. ${\mathit{P}}_{{\mathit{n}}_{\mathrm{1}}\mathrm{+}{\mathit{n}}_{\mathrm{2}}}^{\mathrm{*}}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{P}}_{{\mathit{n}}_{\mathrm{1}}}^{\mathrm{*}}{\mathit{P}}_{{\mathit{n}}_{\mathrm{2}}}^{\mathrm{*}}$. Con-

sequently there exists $\mathit{\rho }\mathrm{=}\lim \sqrt[\mathit{n}]{{\mathit{P}}_{\mathit{n}}^{\mathrm{*}}}$. Furthermore, there exists an absolute constant

$\mathit{c}\mathrm{>}\mathrm{0}$ such that

${\displaystyle \prod }_{\mathit{i}\mathrm{=}\mathrm{1}}^{\mathit{n}}\mathrm{\left(}\mathit{H}\mathrm{\right(}\mathit{i}\mathrm{)}\mathrm{/}\mathit{i}\mathrm{)}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{P}}_{\mathit{n}}^{\mathrm{*}}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{c}\mathrm{(}\mathrm{0}\mathrm{.}\mathrm{3}\mathrm{6}\mathrm{2}{\mathrm{)}}^{\mathit{n}}$

where $\mathit{H}\mathrm{\left(}\mathit{i}\mathrm{\right)}\mathrm{:}\mathrm{=}{{\displaystyle \sum }}_{\mathit{j}\mathrm{=}\mathrm{1}}^{\mathit{i}}\mathrm{1}\mathrm{/}\mathit{j}$. Consequently, $\mathit{\rho }\underset{\mathrm{‾}}{\mathrm{<}}$ 0.362.

The proof of the upper bound is parallel to that of Theorem 1.2.1, lower bound,

while the lower bound follows from the non-inversion (resp. inversion) set criterion

8

described last section. Empirical estimates indicate that $\mathit{\rho }$ is close to 0.3. So here too,

as in Theorem 1.2.1, the upper bound seems to be qualitatively close to the actual

probability ${\mathit{P}}_{\mathit{n}}^{\mathrm{*}}$. And our lower bound, though superior to the trivial bound $\mathrm{1}\mathrm{/}\mathit{n}\mathrm{!}$, is

decreasing superexponentially fast with $\mathit{n}$, which makes us believe that there ought

to be a way to vastly improve it.

Paradoxically, it is the lower bound that required a deeper combinatorial insight.

Clearly the number of $\mathit{\pi }\mathrm{\text{'}}\mathrm{s}$ below (or equal to) a equals $\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}$, the total number of

linear extensions of ${\mathrm{7}}^{\mathrm{\supset }}\mathrm{=}\mathit{P}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$, the poset induced by $\mathit{\sigma }$. (The important notion of

${\mathrm{7}}^{\mathrm{\supset }}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ was brought to our attention by Sergey Fomin [24].) We prove that for any

poset ${\mathrm{7}}^{\mathrm{\supset }}$ of cardinality $\mathit{n}$,

$\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{>}}\mathit{n}\mathrm{!}\mathrm{/}{{\displaystyle \prod }}_{\mathit{i}\mathrm{\in }\mathit{P}}\mathit{d}\mathrm{\left(}\mathit{i}\mathrm{\right)}$, (1.1)

where $\mathit{d}\mathrm{\left(}\mathit{i}\mathrm{\right)}\mathrm{:}\mathrm{=}\mathrm{|}$ { $\mathit{j}\mathrm{\in }\mathit{P}$ : $\mathit{j}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{i}$ in ${\mathrm{7}}^{\mathrm{\supset }}$} $\mathrm{|}$. (This bound is an exact value of $\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}$ if the

Hasse diagram is a (directed) rooted tree, Knuth [34, sect. 5.1.4, ex. 20], or a forest

of such trees, Björner and Wachs [8].) The bound (1.1) for $\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right(}\mathit{\sigma }\mathrm{\left)}\mathrm{\right)}$ together with the

independence of sequential ranks in the uniform permutation were the key ingredients

in the proof of Theorem 1.4.1, lower bound.

$\mathrm{M}\mathrm{i}\mathrm{k}\mathrm{l}\mathrm{6}\mathrm{s}$ $\mathrm{B}\mathrm{6}\mathrm{n}\mathrm{a}\mathrm{\left[}\mathrm{1}\mathrm{2}\mathrm{\right]}$ has informed us that this general lower bound for $\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}$ had been

stated by Richard Stanley as a level 2 exercise in [46, p. 312, ex. 1] without a

solution. We have decided to keep the proof in the dissertation, since we could

not find a published proof anywhere either. The classic hook formula provides an

example of a poset ${\mathrm{7}}^{\mathrm{\supset }}$ for which (1.1) is markedly below $\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}$. It remains to be seen

whether (1.1) can be strengthened in general, or at least for ${\mathrm{7}}^{\mathrm{\supset }}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$. As an illustration,

9

1 2

Figure 1.3: The permutation-induced poset ${\mathrm{7}}^{\mathrm{\supset }}\mathrm{\left(}\mathrm{2}\mathrm{1}\mathrm{4}\mathrm{3}\mathrm{\right)}$.

${\mathrm{7}}^{\mathrm{\supset }}\mathrm{=}\mathit{P}\mathrm{\left(}\mathrm{2}\mathrm{1}\mathrm{4}\mathrm{3}\mathrm{\right)}$ has the Hasse diagram appearing in Figure 1.3. Then $\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}$ $\mathrm{=}\mathrm{4}$, but

(1.1) delivers only

$\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{2}\mathrm{4}\mathrm{/}\mathrm{9}$ $\mathrm{\to }$ $\mathit{e}\mathrm{\left(}\mathit{P}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{3}$.

Regarding the lattice properties of $\mathrm{(}{\mathit{S}}_{\mathit{n}}\mathrm{,}\underset{\mathrm{‾}}{\mathrm{\prec }}\mathrm{)}$, note that the identity permutation 12 $\mathrm{\text{...}}$ $\mathit{n}$

is the unique minimum, and $\mathit{n}\mathrm{(}\mathit{n}\mathrm{-}\mathrm{1}\mathrm{)}$ $\mathrm{\text{...}}$1 is the unique maximum. Let ${\mathit{\pi }}_{\mathrm{1}}$, $\mathrm{\text{...}}$, ${\mathit{\pi }}_{\mathit{r}}\mathrm{\in }{\mathit{S}}_{\mathit{n}}$

be selected independently and uniformly at random. It is natural to ask: "How

likely is it that the infimum (resp. supremum) of $\mathrm{\{}{\mathit{\pi }}_{\mathrm{1}}$ , . . . ' ${\mathit{\pi }}_{\mathit{r}}\mathrm{\}}$ is the unique mini-

mal (resp. maximal) element in the weak order lattice?" Equivalently, what is the

asymptotic number of $\mathit{r}$-tuples $\mathrm{(}{\mathit{\pi }}_{\mathrm{1}}$ , . . . ' ${\mathit{\pi }}_{\mathit{r}}\mathrm{)}$ such that $\inf \mathrm{\{}{\mathit{\pi }}_{\mathrm{1}}$, . . . , ${\mathit{\pi }}_{\mathit{r}}\mathrm{\}}\mathrm{=}\mathrm{1}\mathrm{2}$ $\mathrm{\text{...}}$ $\mathit{n}$ (resp.

$\sup \mathrm{\{}{\mathit{\pi }}_{\mathrm{1}}\mathrm{,}\mathrm{}\mathrm{\text{...}}\mathrm{,}\mathrm{}{\mathit{\pi }}_{\mathit{r}}\mathrm{\}}\mathrm{=}\mathit{n}\mathrm{(}\mathit{n}\mathrm{}\mathrm{-}\mathrm{1}\mathrm{)}$ $\mathrm{\text{...}}$1), $\mathit{n}$ $\mathrm{\to }\mathrm{\infty }$? It turns out that the answer is the same

whether we consider infs or sups, which allows us to focus only on infimums. We

prove the following:

Theorem 1.4.2. Let ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}\mathrm{=}\mathit{P}$ $\mathrm{\left(}\inf \mathrm{\right\{}{\mathit{\pi }}_{\mathrm{1}}\mathrm{,}\mathrm{}$...,$\mathrm{}{\mathit{\pi }}_{\mathit{r}}\mathrm{\}}\mathrm{=}\mathrm{1}\mathrm{2}\mathrm{}$...n). Then

1. As a function of n, ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}$ is submultiplicative. Hence, there exists

to

$\mathit{p}\mathrm{\left(}\mathit{r}\mathrm{\right)}\mathrm{=}\lim \sqrt[\mathit{n}]{{\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}}\mathrm{=}$ inf $\sqrt[\mathit{n}]{{\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}}$, $\mathit{r}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{1}$.

2. For each $\mathit{r}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{1}$, put ${\mathit{h}}_{\mathit{r}}\mathrm{\left(}\mathit{z}\mathrm{\right)}\mathrm{=}{{\displaystyle \sum }}_{\mathit{j}\mathrm{\ge }\mathrm{0}}\frac{\mathrm{(}\mathrm{-}\mathrm{1}{\mathrm{)}}^{\mathit{j}}}{\mathrm{(}\mathit{j}\mathrm{!}{\mathrm{)}}^{\mathit{r}}}{\mathit{z}}^{\mathit{j}}$ and ${\mathit{H}}_{\mathit{r}}\mathrm{\left(}\mathit{z}\mathrm{\right)}\mathrm{=}\mathrm{\left(}{\mathit{h}}_{\mathit{r}}\mathrm{\right(}\mathit{z}\mathrm{)}{\mathrm{)}}^{\mathrm{-}\mathrm{1}}$ Then, letting

${\mathit{P}}_{\mathrm{0}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}\mathrm{=}\mathrm{1}$, we have

${\mathit{H}}_{\mathit{r}}\mathrm{\left(}\mathit{z}\mathrm{\right)}\mathrm{=}{{\displaystyle \sum }}_{\mathit{n}\mathrm{\ge }\mathrm{0}}{\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}{\mathit{z}}^{\mathit{n}}$,

from which we obtain (Darboux theorem [2])

${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}\mathrm{\sim }\mathrm{-}\frac{\mathrm{1}}{{\mathit{z}}^{\mathrm{*}}{\mathit{h}}_{\mathit{r}}^{\mathrm{\prime }}\mathrm{\left(}{\mathit{z}}^{\mathrm{*}}\mathrm{\right)}}\frac{\mathrm{1}}{\mathrm{(}{\mathit{z}}^{\mathrm{*}}{\mathrm{)}}^{\mathit{n}}}$, $\mathit{n}$ $\mathrm{\to }\mathrm{\infty }$.

Here, ${\mathit{z}}^{\mathrm{*}}\mathrm{=}{\mathit{z}}^{\mathrm{*}}\mathrm{\left(}\mathit{r}\mathrm{\right)}\mathrm{\in }\mathrm{(}\mathrm{1}\mathrm{,}\mathrm{}\mathrm{2}\mathrm{)}$ is the unique simple root of ${\mathit{h}}_{\mathit{r}}\mathrm{\left(}\mathit{z}\mathrm{\right)}\mathrm{=}\mathrm{0}$ in the disc

$\mathrm{\left|}\mathit{z}\mathrm{\right|}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{2}$. Consequently, $\mathit{p}\mathrm{\left(}\mathit{r}\mathrm{\right)}\mathrm{=}\mathrm{1}\mathrm{/}{\mathit{z}}^{\mathrm{*}}$

Unlike our results about comparability in the Bruhat and weak orderings, here we

have a sharp asymptotic formula. The key to the proof of this theorem is establishing

the exact formula

${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}\mathrm{=}{\displaystyle \sum }_{\mathit{k}\mathrm{=}\mathrm{0}}^{\mathit{n}\mathrm{-}\mathrm{1}}\mathrm{(}\mathrm{-}\mathrm{1}{\mathrm{)}}^{\mathit{k}}$ ${\mathit{b}}_{\mathrm{1}}\mathrm{+}\mathrm{\text{...}}\mathrm{+}{\mathit{b}}_{\mathit{n}\mathrm{-}\mathit{k}}\mathrm{=}\mathit{n}{{\displaystyle \sum }}_{{\mathit{b}}_{\mathrm{1}}\mathrm{,}\mathrm{\text{...}}\mathrm{,}{\mathit{b}}_{\mathit{n}\mathrm{-}\mathit{k}}\mathrm{\ge }\mathrm{1}}\mathrm{,}\mathrm{(}{\mathit{b}}_{\mathrm{1}}\mathrm{!}{\mathrm{)}}^{\mathit{r}}\mathrm{\text{...}}\mathrm{(}{\mathit{b}}_{\mathit{n}\mathrm{-}\mathit{k}}\mathrm{!}{\mathrm{)}}^{\mathit{r}}\mathrm{1}$,

which follows from the principle of inclusion-exclusion. This formula for ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}$ is, in

some sense, an $\mathit{r}$-analog of that for the Eulerian numbers ( $\mathrm{B}\mathrm{6}\mathrm{n}\mathrm{a}\mathrm{\left[}\mathrm{1}\mathrm{1}\mathrm{\right]}$, Knuth [34]).

Indeed, it turns out that ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}$ is the probability that the uniform, independent permu-

tations ${\mathit{\pi }}_{\mathrm{1}}^{\mathrm{-}\mathrm{1}}$, $\mathrm{\text{...}}$, ${\mathit{\pi }}_{\mathit{r}}^{\mathrm{-}\mathrm{1}}$ have no common descents. Introduce the random variable ${\mathit{S}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}$,

11

the number of these common descents, so that ${\mathit{P}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}\mathrm{=}\mathit{P}\mathrm{(}{\mathit{S}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}\mathrm{=}\mathrm{0}\mathrm{)}$. Another natural

question here is:

Problem. What is the limiting distribution of ${\mathit{S}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}$l.?

We believe that the answer here is "Gaussian", as it is in the case of the number

of descents in a single uniformly random permutation (Sachkov [44]). Our feeling

is that the proof will involve use of the bivariate generating function ${\mathit{F}}_{\mathit{r}}\mathrm{(}\mathit{x}\mathrm{,}\mathrm{}\mathit{y}\mathrm{)}\mathrm{=}$

${{\displaystyle \sum }}_{\mathit{n}\mathrm{\ge }\mathrm{1}}{\mathit{x}}^{\mathit{n}}\mathit{E}\mathrm{\left[}\mathrm{\right(}\mathrm{1}\mathrm{+}\mathit{y}{\mathrm{)}}^{{\mathit{S}}_{\mathit{n}}^{\mathrm{\left(}\mathit{r}\mathrm{\right)}}}\mathrm{]}$, which we prove has the simple form

${\mathit{F}}_{\mathit{r}}\mathrm{(}\mathit{x}\mathrm{,}\mathrm{}\mathit{y}\mathrm{)}\mathrm{=}\frac{\mathit{x}{\mathit{f}}_{\mathit{r}}\mathrm{\left(}\mathit{x}\mathit{y}\mathrm{\right)}}{\mathrm{1}\mathrm{-}\mathit{x}{\mathit{f}}_{\mathit{r}}\mathrm{\left(}\mathit{x}\mathit{y}\mathrm{\right)}}$, ${\mathit{f}}_{\mathit{r}}\mathrm{\left(}\mathit{z}\mathrm{\right)}\mathrm{.}\mathrm{=}{{\displaystyle \sum }}_{\mathit{j}\mathrm{\ge }\mathrm{0}}\frac{{\mathit{z}}^{\mathit{j}}}{\mathrm{(}\mathit{j}\mathrm{+}\mathrm{1}\mathrm{)}{\mathrm{!}}^{\mathit{r}}}$ .

Interestingly, this generating function is a special case of a more general result proved

by Richard Stanley [45], although he was probably unaware of the connections his

work had with the weak ordering.

In conclusion we mention several papers that are in the same spirit of this dissertation.

First, [39] and [40] (both by Boris Pittel), where the "probability-of-comparability"

problems were solved for the poset of integer partitions of $\mathit{n}$ under dominance order,

and for the poset of set partitions of $\mathrm{\left[}\mathit{n}\mathrm{\right]}$ ordered by refinement. Also, [41] (again

by B. Pittel), where the $\mathrm{\text{"}}\mathrm{i}\mathrm{n}\mathrm{f}$