An IDEAL Group, CLC, Project

]> An IDEAL Group, CLC, Project

ON COMPARABILITY OF RANDOM PERMUTATIONS

DISSERTATIO $N$

Presented in Partial Fulfillment of the Requirements for

the Degree Doctor of Philosophy in the Graduate

School of the Ohio State University

Adam Hammett, $B . S$ .

$* * * *$ $*$

The Ohio State University

2007

Dissertation Committee:

$\mapsto 133 C 1 b C l b l \cup 11 \cup \cup 111111 l b b C C$ . Approved by

Dr. Boris Pittel, Advisor

Dr. Gerald Edgar

1 $ċ$ .

Advisor

Dr. Akos Seress Graduate Program in

Graduate Program in Mathematics

ABSTRACT

Two permutations of $[n]$ $: = {1, 2, ..., n}$ 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 $(π, σ)$ with

$π \underline{<} σ$ is of order $(n!)^{2} / n^{2}$ at most. Equivalently, if $π$ , a are chosen uniformly at

random and independently of each other, then $P (π \underline{<} σ)$ is of order $n^{- 2}$ at most. By

a direct probabilistic argument we prove $P (π \underline{<} σ)$ is of order $(0.708)^{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 $n$ permutations $π_{1}$ , $...$ , $π_{r}$ selected independently and uniformly at random,

$P (π_{1} \underline{<} ... \underline{<} π_{r}) = O (n^{- r (r - 1)})$ ,

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

$r > 2$ .

Turning to the related weak order $" ≺ -$ "- when only adjacent transpositions are

admissible - we use a non-inversion set criterion to prove that $P_{n}^{*} : = P (π \underline{≺} σ)$ is

submultiplicative, thus showing existence of $ρ = \lim \sqrt[n]{P_{n}^{*}}$ . We demonstrate that $ρ$

is 0.362 at most. Moreover, we prove the lower bound $\prod_{i = 1}^{n} (H (i) / i)$ for $P_{n}^{*}$ , where

$H (i) : = \sum_{j = 1}^{i} 1 / 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 $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

$(π_{1}$ , . . . ' $π_{r})$ of $n$ -permutations with minimal infimum, 12 $...$ $n$ , asymptotically equals

$- \frac{(n!)^{r}}{h_{r}^{'} (z^{*}) (z^{*})^{n + 1}}$ , $r \underline{>} 2$ , $n$ $\to \infty$ . (1)

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

$h_{r} (z) : = \sum_{j \geq 0} \frac{(- 1)^{j}}{(j!)^{r}} z^{j} = 0$

within the disk $| z | \underline{<} 2$ . Moreover, (1) is also the asymptotic number of $r$ -tuples with

maximal supremum, $n (n - 1)$ $... 1$ .

iii

To my wife, Rachael, for her unending suppport.

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 $6 0^{t 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 $M i k l 6 s$ $B 6 n 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.

$v$

VITA

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

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

Westmont College - Santa Barbara, CA

2001 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . $B . S$ . in Mathematics,

Westmont College

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

The Ohio State University

FIELDS OF STUDY

Major Field: Mathematics

Specialization: Combinatorial Probability

TABLE OF CONTENTS

Abstract ii

Dedication . 1v

Acknowledgments . $v$

Vita vi

List of Figures $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

An Extension to Chains in Bruhat Order

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 $P_{n}^{*}$ 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 $P (E_{i} (π) \underline{\supset} E_{i} (σ))$ . . 75

7.2 Positive Correlation of the Events ${E_{i} (π) \underline{\supset} E_{i} (σ)}$ 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 {π_{1}$ , . . . ' $π_{r}} = 12$ $...$ $n$ 96

9.4 Submultiplicativity Again 99

9.5 Sharp Asymptotics of $P_{n}^{(r)}$ . 1Ot

9.5.1 Step 1: An Exact Formula for $P_{n}^{(r)}$ lai

9.5.2 Step 2: A Generating Function for $P_{n}^{(r)} .$ . 105

9.5.3 Step 3: Asymptotics 108

Vlll

Open Problems

114

10.1 The Problems 114

Bibliography 115

LIST OF FIGURES

FIGURE PAGE

1.1 The Bruhat order on $S_{3}$ and $S_{4}$ . 2

1.2 Superimposing $M (π)$ and $M (σ)$ to form $M (π, σ)$ . 5

1.3 The permutation-induced poset $7^{\supset} (2143)$ . $10$

$2.1$ Finding a necessary condition for $π \underline{<} σ$ . 16

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

corners to support $M (π)$ . 21

3.1 $G_{5}$ and an emboldened subgrid C. 27

3.2 Deletion of 2 largest elements of $π$ , $σ$ , and its affect on C. . 28

4.1 Finding a necessary condition for $π_{1} \underline{<} ...$ $\underline{<} π_{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 $- a$ in the asymptotic

equation $P_{n} \sim c n^{- a}$ . 85

8.2 Experimental determination of the ratio $ρ$ in the asymptotic equation

$P_{n}^{*} \sim c ρ^{n}$ . 86

$x$

LIST OF TABLES

TABLE PAGE

3.1 Exact computation of $N_{k}$ for smallish $k$ . 37

6.1 Exact computation of $N_{k}^{*}$ for smallish $k$ . 74

8.1 Computer simulation data for $P_{n}$ . 84

8.2 Exact computation of $P_{n}$ for smallish $n$ . 84

8.3 Computer simulation data for $P_{n}^{*}$ . 87

8.4 Exact computation of $P_{n}^{*}$ for smallish $n$ . 87

8.5 Our theoretical lower bound for $P_{n}^{*}$ applied for smallish $n$ . 88

(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 $n \underline{>} 1$ be an integer. Two permutations of $[n]$ $: = {1, ..., n}$ 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 $S_{n}$ (see [46, p. 172, ex. 75. $a .]$ , Humphreys [30, p. 119]).

If $ω$ $= ω (1)$ $...$ $ω (n)$ $\in S_{n}$ , then a reduction of $ω$ is a permutation obtained from $ω$

by interchanging some $ω$ $(i)$ with some $ω$ $(j)$ provided $i < j$ and $ω$ $(i) > ω$ $(j)$ . We say

that $π \underline{<} σ$ in the Bruhat order if there is a chain $σ = ω_{1} \to ω_{2} \to ... \to ω_{s} = π$ , where

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

4321

321

312

132

123

1234

Figure 1.1: The Bruhat order on $S_{3}$ and $S_{4}$ .

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

$i < j$ , then

$i n v (ω_{1}) = i n v (ω_{2}) + 2 N (ω_{1}) + 1$ ,

$N (ω_{1}) : = | {k : i < k < j, ω_{1} (i) > ω_{1} (k) > ω_{1} (j)} |$ ;

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

1.1 illustrates this poset on $S_{3}$ and $S_{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 $S_{n}$ only.

The definition of the Bruhat order is very transparent, and yet deciding for given $π$ , a

whether $π \underline{<} σ$ from the definition is computationally difficult, even for smallish $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 $π \underline{<} σ$ if and only if $π_{i, j} \underline{<} σ_{i, j}$ for all $1 \underline{<} i \underline{<} j \underline{<} n$ $- 1$ , where

$π_{i, j}$ and $σ_{i, j}$ are the i-th entry in the increasing rearrangement of $π (1)$ , . . . , $π (j)$

and of a(1) , . . . ' $σ (j)$ . These arrangements form two staircase tableaux, hence the

term tableau criterion" For example, 41523 $>$ 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 $(0, 1)$ -matrix

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

of the $(0, 1)$ -permutation matrices representing $π$ and a (see $B 6 n a [10]$ , [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] $)$ , but we found the

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

The $(0, 1)$ -matrix criterion for Bruhat order on $S_{n}$ says that for $π$ , $σ \in S_{n}$ , $π \underline{<} σ$ if

and only if for all $i$ , $j \underline{<} n$ , the number of $π (1)$ , . . . , $π (i)$ that are at most $j$ exceeds

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

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

condition: let $M$ $(π)$ , $M (σ)$ be the permutation matrices corresponding to $π$ , $σ$ , so

that for instance the $(i, j)$ -entry of $M (π)$ is 1 if $π (j) = i$ and 0 otherwise. Here, we

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

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

ones at points $(i, π (i))$ of the $n$ $\times n$ integer lattice and zeroes elsewhere. Denoting

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

says that $π \underline{<} σ$ if and only if for all $i$ , $j \underline{<} n$ , the number of ones in $M$ $(π)_{[i], [j]}$ is at

least the number of ones in $M$ $(σ)_{[i], [j]}$ (see [21] for this version).

An effective way of visualizing this criterion is to imagine the matrices $M$ $(π)$ and

$M$ $(σ)$ as being superimposed on one another into a single matrix, $M$ $(π, σ)$ , with the

ones for $M$ $(π)$ represented by $\times' s (" c r o s s e s ")$ , the ones for $M$ $(σ)$ by $\circ$ 's $(" b a l l s ")$

and the zeroes for both by empty entries. Note that some entries of a $(π, σ)$ may

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

$π \underline{<} σ$ if and only if every southwest submatrix of $M$ $(π, σ)$ contains at least as many

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

$M$ $(π, σ)_{[i], [j]}$ of $M$ $(π, σ)$ for some $i$ , $j \underline{<} n$ . It is clear that we could also check

$π \underline{<} σ$ by checking that crosses are at least as numerous as balls in every northeast

submatrix of $M$ $(π, σ)$ . Likewise, $π \underline{<} σ$ if and only if balls are at least as numerous

as crosses in every northwest submatrix of $M$ $(π, σ)$ , or similarly balls are at least

$M (0)$

Figure 1.2: Superimposing $M (π)$ and $M (σ)$ to form $M (π, σ)$ .

as numerous as crosses in every southeast submatrix of $M$ $(π, σ)$ . Parts of all four

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

$π =$ 21534 and $σ = 41523$ , $π < σ$ is checked by examining southwest submatrices of

$M$ $(π, σ)$ in Figure 1.2. Also, the superimposing of $M$ $(π)$ with $M$ $(σ)$ to form $M$ $(π, σ)$

is illustrated in this figure.

1.2 Main Results Related to the Bruhat Order

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

upper and lower bounds for the number of pairs $(π, σ)$ with $π \underline{<} σ$ .

Theorem 1.2.1. Let $n \underline{>} 1$ be an integer, and let $π$ , $σ \in S_{n}$ be selected independently

and uniformly at random. Then there exist universal constants $c_{1}$ , $c_{2} > 0$ such that

$c_{1} (0.708)^{n} \underline{<} P (π \underline{<} σ) \underline{<} c_{2} / n^{2}$

Equivalently, the number of pairs $(π, σ)$ with $π \underline{<} σ$ is sandwiched between the

counts $c_{1} (0.708)^{n} (n!)^{2}$ and $c_{2} n^{- 2} (n!)^{2}$ . The lower bound follows from a sufficient

condition derived from the $(0, 1)$ -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 $P (π \underline{<} σ)$ is of order $n^{- (2 + δ)}$ ,

for $δ$ close to 0.5 from above. So apparently it is the upper bound which comes close

to the true proportion $P (π \underline{<} σ)$ . 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 $(1 - o (1))^{n}$ . A lower bound $n^{- 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 $r$ in Bruhat

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

plane partitions contained in an $r \times s \times 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

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

to r-tuples:

Theorem 1.2.2. Let $π_{1}$ , ..., $π_{r} \in S_{n}$ be selected independently and uniformly at

random. Then there exists a uniform constant c $> 0$ such that

$P (π_{1} \underline{<} ... \underline{<} π_{r}) \underline{<} c / n^{r (r - 1)}$ .

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

the Bruhat order poset.

1.3 Weak Order, Preliminaries

Then we turn to the modified order on $S_{n}$ , the rveak order $" ≺ -$ " Here $π \underline{≺} σ$ if there

is a chain $σ = ω_{1} \to ω_{2} \to ... \to ω_{s} = π$ , where each $ω_{t}$ is a simple reduction of $ω_{t - 1}$ ,

i.e. obtained from $ω_{t - 1}$ by transposing two adjacent elements $ω_{t - 1} (i)$ , $ω_{t - 1} (i + 1)$ with

$ω_{t - 1} (i) > ω_{t - 1} (i + 1)$ . Since at each step the number of inversions decreases by 1,

all chains connecting a and $π$ have the same length. Alternatively, there is a simple

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

check $π \underline{≺} σ$ . Indeed, given $ω \in S_{n}$ introduce the set of non-inversions of $ω$ :

$E (ω) = {(i, j) : i < j, ω^{- 1} (i) < ω^{- 1} (j)}$ .

Similarly, for $ω \in S_{n}$ we introduce the set of inversions of $ω$ :

$E^{*} (ω) = {(i, j) : i > j, ω^{- 1} (i) < ω^{- 1} (j)}$ .

Then, for given $π$ , $σ \in S_{n}$ , we have $π \underline{≺} σ$ if and only if $E (π) \underline{\supset} E (σ)$ (equivalently

$E^{*} (π) \underline{\subset} E^{*} (σ))$ . Note that $ω \in S_{n}$ is uniquely determined by its $E (ω)$ (resp. its

$E^{*} (ω))$ .

It turns out that the poset $(S_{n}, \underline{≺})$ is a lattice (see [3]). Indeed, given $π_{1}$ , $...$ , $π_{r} \in S_{n}$ ,

there is an efficient way to compute $E (\inf {π_{1}, ..., π_{r}})$ (resp. $E^{*} (\sup {π_{1}$ , . . . , $π_{r}}$ ))

from the set $\cup_{i = 1}^{r} E (π_{i})$ (resp. $\cup_{i = 1}^{r} E$ " ( $π_{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 $π$ , $σ \in S_{n}$ be selected independently and uniformly at random,

and let $P_{n}^{*} : = P (π \underline{≺} σ)$ . Then $P_{n}^{*}$ is submultiplicative, $i . e$ . $P_{n_{1} + n_{2}}^{*} \underline{<} P_{n_{1}}^{*} P_{n_{2}}^{*}$ . Con-

sequently there exists $ρ = \lim \sqrt[n]{P_{n}^{*}}$ . Furthermore, there exists an absolute constant

$c > 0$ such that

$\prod_{i = 1}^{n} (H (i) / i) \underline{<} P_{n}^{*} \underline{<} c (0.362)^{n}$

where $H (i) : = \sum_{j = 1}^{i} 1 / j$ . Consequently, $ρ \underline{<}$ 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

described last section. Empirical estimates indicate that $ρ$ 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 $P_{n}^{*}$ . And our lower bound, though superior to the trivial bound $1 / n!$ , is

decreasing superexponentially fast with $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 $π' s$ below (or equal to) a equals $e (P)$ , the total number of

linear extensions of $7^{\supset} = P (σ)$ , the poset induced by $σ$ . (The important notion of

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

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

$e (P) \underline{>} n! / \prod_{i \in P} d (i)$ , (1.1)

where $d (i) : = |$ { $j \in P$ : $j \underline{<} i$ in $7^{\supset}$ } $|$ . (This bound is an exact value of $e (P)$ 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 $e (P (σ))$ 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.

$M i k l 6 s$ $B 6 n a [12]$ has informed us that this general lower bound for $e (P)$ 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 $7^{\supset}$ for which (1.1) is markedly below $e (P)$ . It remains to be seen

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

1 2

Figure 1.3: The permutation-induced poset $7^{\supset} (2143)$ .

$7^{\supset} = P (2143)$ has the Hasse diagram appearing in Figure 1.3. Then $e (P)$ $= 4$ , but

(1.1) delivers only

$e (P) \underline{>} 24 / 9$ $\to$ $e (P) \underline{>} 3$ .

Regarding the lattice properties of $(S_{n}, \underline{≺})$ , note that the identity permutation 12 $...$ $n$

is the unique minimum, and $n (n - 1)$ $...$ 1 is the unique maximum. Let $π_{1}$ , $...$ , $π_{r} \in S_{n}$

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

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

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

asymptotic number of $r$ -tuples $(π_{1}$ , . . . ' $π_{r})$ such that $\inf {π_{1}$ , . . . , $π_{r}} = 12$ $...$ $n$ (resp.

$\sup {π_{1}, ..., π_{r}} = n (n - 1)$ $...$ 1), $n$ $\to \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 $P_{n}^{(r)} = P$ $(\inf {π_{1},$ ..., $π_{r}} = 12$ ...n). Then

1. As a function of n, $P_{n}^{(r)}$ is submultiplicative. Hence, there exists

$p (r) = \lim \sqrt[n]{P_{n}^{(r)}} =$ inf $\sqrt[n]{P_{n}^{(r)}}$ , $r \underline{>} 1$ .

2. For each $r \underline{>} 1$ , put $h_{r} (z) = \sum_{j \geq 0} \frac{(- 1)^{j}}{(j!)^{r}} z^{j}$ and $H_{r} (z) = (h_{r} (z))^{- 1}$ Then, letting

$P_{0}^{(r)} = 1$ , we have

$H_{r} (z) = \sum_{n \geq 0} P_{n}^{(r)} z^{n}$ ,

from which we obtain (Darboux theorem [2])

$P_{n}^{(r)} \sim - \frac{1}{z^{*} h_{r}^{'} (z^{*})} \frac{1}{(z^{*})^{n}}$ , $n$ $\to \infty$ .

Here, $z^{*} = z^{*} (r) \in (1, 2)$ is the unique simple root of $h_{r} (z) = 0$ in the disc

$| z | \underline{<} 2$ . Consequently, $p (r) = 1 / z^{*}$

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

$P_{n}^{(r)} = \sum_{k = 0}^{n - 1} (- 1)^{k}$ $b_{1} + ... + b_{n - k} = n \sum_{b_{1}, ..., b_{n - k} \geq 1}, (b_{1}!)^{r} ... (b_{n - k}!)^{r} 1$ ,

which follows from the principle of inclusion-exclusion. This formula for $P_{n}^{(r)}$ is, in

some sense, an $r$ -analog of that for the Eulerian numbers ( $B 6 n a [11]$ , Knuth [34]).

Indeed, it turns out that $P_{n}^{(r)}$ is the probability that the uniform, independent permu-

tations $π_{1}^{- 1}$ , $...$ , $π_{r}^{- 1}$ have no common descents. Introduce the random variable $S_{n}^{(r)}$ ,

the number of these common descents, so that $P_{n}^{(r)} = P (S_{n}^{(r)} = 0)$ . Another natural

question here is:

Problem. What is the limiting distribution of $S_{n}^{(r)}$ 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 $F_{r} (x, y) =$

$\sum_{n \geq 1} x^{n} E [(1 + y)^{S_{n}^{(r)}}]$ , which we prove has the simple form

$F_{r} (x, y) = \frac{x f_{r} (x y)}{1 - x f_{r} (x y)}$ , $f_{r} (z) . = \sum_{j \geq 0} \frac{z^{j}}{(j + 1)!^{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 $n$ under dominance order,

and for the poset of set partitions of $[n]$ ordered by refinement. Also, [41] (again

by B. Pittel), where the $" i n f i m u m / s u p r e m u m$ " problem was solved for the lattice

of set partitions of $[n]$ ordered by refinement. In [16], E. R. Canfield presents an

enlightening extension of the $\inf / \sup$ work done in [41]. Very recently, in [1], R. M.

Adin and Y. Roichman explore the valency properties of a typical permutation in the

Bruhat order Hasse diagram.

This work is in large part the result of an intensive collaborative effort with my

doctoral advisor, Boris Pittel. Portions of this dissertation have been accepted for

publication (2006) in the journal Transactions of the American Mathematical Society

(see [28] for availability).

(JIAPTER 2

THE PROOF OF THE BRUHAT ORDER UPPER BOUND

In this chapter, we focus on the proof of Theorem 1.2.1, upper bound. The proof

divides naturally into three steps, hence the divisions of the sections that follow.

We need to show that

$P (π \underline{<} σ) = O (n^{- 2})$ .

The argument is based on the $(0, 1)$ -matrix criterion. We assume that $n$ is even. Only

minor modifications are necessary for $n$ odd.

2.1 A Necessary Condition for Bruhat Comparability

The $(0, 1)$ -matrix criterion requires that a set of $n^{2}$ conditions are met. The challenge

is to select a subset of those conditions which meets two conflicting demands. It has

to be sufficiently simple so that we can compute (estimate) the probability that the

random pair $(π, σ)$ satisfies all the chosen conditions. On the other hand, collectively

these conditions need to be quite stringent for this probability to be $o (1)$ . In our first

advance we were able (via Ehresmann's criterion) to get a bound $O (n^{- 1 / 2})$ by using

about 2 $n^{1 / 2}$ conditions. We are about to describe a set of $2 n$ conditions that does the

job.

Let us split the matrices $M$ $(π, σ)$ , $M$ $(π)$ and $M$ $(σ)$ into 4 submatrices of equal size

$n / 2 \times n / 2 -$ the southwest, northeast, northwest and southeast corners, denoting them

$M_{s w} (ċ)$ , $M_{n e} (ċ)$ , $M_{n w} (ċ)$ and $M_{s e} (ċ)$ respectively. In the southwest corner $M_{s w} (π, σ)$ ,

we restrict our attention to southwest submatrices of the form $i \times n / 2$ , $i = 1$ , $...$ , $n / 2$ .

If $π \underline{<} σ$ , then as we read off rows of $M_{s w} (π, σ)$ from bottom to top keeping track

of the total number of balls and crosses encountered thus far, at any intermediate

point we must have at least as many crosses as balls. Let us denote the set of pairs

$(π, σ)$ such that this occurs by $E_{s w}$ . We draw analogous conclusions for the northeast

corner, reading rows from top to bottom, and we denote by $E_{n e}$ the set of pairs $(π, σ)$

satisfying this condition.

Similarly, we can read columns from left to right in the northwest corner, and here we

must always have at least as many balls as crosses. Denote the set of these pairs $(π, σ)$

by $E_{n w}$ . The same condition holds for the southeast corner when we read columns

from right to left. Denote the set of these pairs $(π, σ)$ by $E_{s e}$ . Letting $E$ denote the

set of pairs $(π, σ)$ satisfying all four of the conditions above, we get

${π \underline{<} σ} \underline{\subset} E = E_{s w} \cap E_{n e} \cap E_{n w} \cap E_{s e}$ .

Pairs of permutations in $E$ satisfy $2 n$ of the $n^{2}$ conditions required by the $(0, 1)$ -matrix

criterion. And unlike the set ${π \underline{<} σ}$ , we are able to compute $| E |$ , and to show that

$P (E) = (n!)^{- 2} | E | = O (n^{- 2})$ . Figure 2.1 is a graphical visualization of the reading-off

process that generates the restrictions defining the set $E$ .

If a row (column) of a submatrix $M (π)_{I, J}$ ( $M (σ)_{I, J}$ resp.) contains a marked entry, we

say that it supports the submatrix. Clearly the number of supporting rows (columns)

$M (π, 0)$

$↓$

$|$

Figure 2.1: Finding a necessary condition for $π \underline{<} σ$ .

equals the number of marked entries in $M (π)_{I, J}$ ( $M (σ)_{I, J}$ resp.). Now, given $π$ , $σ$ ,

let $M_{1} = M_{1} (π)$ , $M_{2} = M_{2} (σ)$ denote the total number of rows that support $M_{s w} (π)$

and $M_{s w} (σ)$ respectively. Then $M_{n w} (π)$ , $M_{n w} (σ)$ are supported by $M_{3} = n / 2 - M_{1}$

columns and by $M_{4} = n / 2 - M_{2}$ columns respectively. The same holds for the

southeastern corners of $M (π)$ and $M (σ)$ . Obviously the northeastern submatrices of

$M (π)$ and $M (σ)$ are supported by $M_{1}$ rows and $M_{2}$ rows respectively. Then we have

$P (E) = \sum_{m_{1}, m_{2}} P (E \cap A (m_{1}, m_{2}))$ ,

(2.1)

$A$ $(m_{1}, m_{2}) : = {(π, σ) : M_{1} = m_{1}, M_{2} = m_{2}}$ .

Clearly $E \cap A$ $(m_{1}, m_{2}) = \emptyset$ if $m_{1} < m_{2}$ . We claim that, for $m_{1} \underline{>} m_{2}$ ,

$P (E \cap A (m_{1}, m_{2})) = [\frac{(m_{1} - m_{2} + 1) (n / 2 + 1)}{(n / 2 - m_{2} + 1) (m_{1} + 1)}]^{4} ċ \frac{\prod_{i = 1}^{4} (\begin{matrix} n / 2 \\ m_{i} \end{matrix})}{(_{n / 2}^{n})^{2}}$ . (T)

Here and below $m_{3} : = n / 2 - m_{1}$ and $m_{4} : = n / 2 - m_{2}$ stand for generic values of $M_{3}$

and $M_{4}$ in the event $A$ $(m_{1}, m_{2})$ .

To prove (T), let us count the number of pairs $(π, σ)$ in $E \cap A (m_{1}, m_{2})$ . First consider

the southwest corner, $M_{s w} (π, σ)$ . Introduce $L_{1} = L_{1} (π, σ)$ , the number of rows

supporting both $M_{s w} (π)$ and $M_{s w} (σ)$ . So $L_{1}$ is the number of rows in the southwest

corner $M_{s w}$ $(π, σ)$ containing both a cross and a ball. Suppose that we are on the

event ${L_{1} = P_{1}}$ . We choose $p_{1}$ rows to support both $M_{s w} (π)$ and $M_{s w} (σ)$ from the

$n / 2$ first rows. Then, we choose $(m_{1} - P_{1} + m_{2} - P_{1})$ more rows from the remaining

$(n / 2 - P_{1})$ rows. Each of these secondary rows is to support either $M_{s w} (π)$ or $M_{s w} (σ)$ ,

but not both. This step can be done in

ways. Next, we partition the set of $(m_{1} - P_{1} + m_{2} - P_{1})$ secondary rows into two row

subsets of cardinality $(m_{1} - l_{1})$ (rows to contain crosses) and $(m_{2} - l_{1})$ (rows to contain

balls) that will support $M_{s w} (π)$ and $M_{s w} (σ)$ , accompanying the $p_{1}$ primary rows

supporting both submatrices. We can visualize each of the resulting row selections as

a subsequence of $($ 1, . . . , $n / 2)$ which is a disjoint union of two subsequences, one with

$p_{1}$ elements labeled by a ball and a cross, and another with $(m_{1} - P_{1} + m_{2} - P_{1})$ elements,

$(m_{1} - l_{1})$ labeled by crosses and the remaining $(m_{2} - l_{1})$ elements labeled by balls.

The condition $E_{s w}$ is equivalent to the restriction: moving along the subsequence from

left to right, at each point the number of crosses is not to fall below the number of

balls. Obviously, no double-marked element can cause violation of this condition.

Thus, our task is reduced to determination of the number of $(m_{1} - P_{1} + m_{2} - P_{1})$ -long

sequences of $m_{1} - l_{1}$ crosses and $m_{2} - l_{1}$ balls such that at no point the number of

crosses is strictly less than the number of balls. By the classic ballot theorem (see

Takacs [49, pp. 2-7] $)$ , the total number of such sequences equals

$\frac{(m_{1} - l_{1} + 1) - (m_{2} - l_{1})}{(m_{1} - l_{1} + 1) + (m_{2} - l_{1})}$

$= \frac{m_{1} - m_{2} + 1}{m_{1} - l_{1} + 1}$ .

The second binomial coefficient is the total number of $(m_{1} - p_{1} + m_{2} - P_{1})$ -long

sequences of $(m_{1} - l_{1})$ crosses and $(m_{2} - l_{1})$ balls. So the second fraction is the

probability that the sequence chosen uniformly at random among all such sequences

meets the ballot theorem condition. The total number of ways to designate the rows

supporting $M_{s w} (π)$ and $M_{s w} (σ)$ , subject to the condition $E_{s w}$ , is the product of two

counts, namely

$(_{l_{1}}^{n / 2}) (_{m_{1} - l_{1} + m_{2} - l_{1}} n / 2 - l_{1}) (^{m_{1} - l_{1} + m_{2} - l_{1}} m_{1} - l_{1}) \frac{m_{1} - m_{2} + 1}{m_{1} - l_{1} + 1}$

$= \frac{m_{1} - m_{2} + 1}{n / 2 - m_{2} + 1} (_{m_{2}}^{n / 2}) (_{p_{1}}^{m_{2}}) (_{m_{1} - l_{1} + 1}^{n / 2 - m_{2} + 1})$

Suummmmirng this last expression over all $p_{1} \underline{<} m_{2}$ , we obtain

$\frac{m_{1} - m_{2} + 1}{n / 2 - m_{2} + 1}$ $\sum_{\leq m_{2}}$

$= \frac{m_{1} - m_{2} + 1}{n / 2 - m_{2} + 1}$ (2.2)

$= \frac{(m_{1} - m_{2} + 1) (n / 2 + 1)}{(n / 2 - m_{2} + 1) (m_{1} + 1)}$ .

Here, in the first equality, we have used the binomial theorem. The product of the

two binomial coefficients in the final count (2.2) is the total number of row selections

from the first $n / 2$ rows, $m_{1}$ to contain crosses and $m_{2}$ to contain balls. So the

fraction preceding these two binomial factors is the probability that a particular row

selection chosen uniformly at random from all such row selections satisfies our ballot

condition "crosses never fall below balls" Equivalently, by the very derivation, the

expression (2.2) is the total number of paths $(X (t), Y (t))_{0 \leq t \leq n / 2}$ on the square lattice

connecting $(0, 0)$ and $(m_{1}, m_{2})$ such that $X (t + 1)$ $- X (t)$ , $Y (t + 1)$ $- Y (t) \in {0, 1}$ , and

$X (t) \underline{>} Y (t)$ for every $t$ . (To be sure, if $X (t + 1)$ $- X (t) = 1$ and $Y (t + 1)$ $- Y (t) = 1$ ,

the corresponding move is a combination of horizontal and vertical unit moves.)

Likewise, we consider the northeast corner, $M_{n e} (π, σ)$ . We introduce $L_{2} = L_{2} (π, σ)$ ,

the number of rows in $M_{n e} (π, σ)$ containing both a cross and a ball. By initially

restricting to the event ${L_{2} = P_{2}}$ , then later summing over all $p_{2} \underline{<} m_{2}$ , we obtain

another factor (2.2). Analogously, a third and fourth factor (2.2) comes from con-

sidering columns in the northwest and southeast corners, $M_{n w} (π, σ)$ and $M_{s e} (π, σ)$ .

Importantly, the row selections for the southwest and the northeast submatrices do

not interfere with the column selections for the northwest and the southeast corners.

So by multiplying these four factors (2.2) we obtain the total number of row and

column selections on the event $A (m_{1}, m_{2})$ subject to all four restrictions defining $E!$

Once such a row-column selection has been made, we have determined which rows

and columns support the four submatrices of $M (π)$ and $M (σ)$ . Consider, for instance,

the southwest corner of $M (π)$ . We have selected $m_{1}$ rows (from the first $n / 2$ rows)

supporting $M_{s w} (π)$ , and we have selected $m_{3}$ columns (from the first $n / 2$ columns)

supporting $M_{n w} (π)$ . Then it is the remaining $n / 2 - m_{3} = m_{1}$ columns that support

$M_{s w} (π)$ . The number of ways to match these $m_{1}$ rows and $m_{1}$ columns, thus to

determine $M_{s w} (π)$ completely, is $m_{1}!$ . The northeast corner contributes another $m_{1}!$ ,

while each of the two other corners contributes $m_{3}!$ , whence the overall matching

factor is $(m_{1}! m_{3}!)^{2}$ . The matching factor for a is $(m_{2}! m_{4}!)^{2}$ . Multiplying the number

of admissible row-column selections by the resulting $\prod_{i = 1}^{4} (m_{i}!)^{2}$ and dividing by $(n!)^{2}$ ,

we obtain

$P (E \cap A (m_{1}, m_{2})) = [\frac{(m_{1} - m_{2} + 1) (n / 2 + 1)}{(n / 2 - m_{2} + 1) (m_{1} + 1)}$ $]^{4}$ . $\frac{\prod_{i = 1}^{4} (m_{i}!)^{2}}{(n!)^{2}}$ ,

which is equivalent to (T). Figure 2.2 is a graphical explanation of this matching

factor. In it, we show the matrix $M (π)$ in a case when in the southwest and the

$n / 2 " - m$

$]) m$

$m ($

$∖_{- v} ⋁$

$n / 2 - m$

Figure 2.2: Selection of first $m = m_{1}$ ( $n / 2 - m$ resp.) rows (columns resp.) in corners

to support $M (π)$ .

northeast squares $π$ is supported by the bottom $m (= m_{1})$ and the top $m$ rows re-

spectively; likewise, in the northwest and the southeast squares $π$ is supported by the

$n / 2 - m$ leftmost and the $n / 2 - m$ rightmost columns respectively.

2.2 A Probabilistic Simplification

Let us show that (2.1) and (T) imply

P $(E) \underline{<} E [\frac{(M_{1} - M_{2} + 1)^{4} (n / 2 + 1)^{4}}{(n / 2 - M_{2} + 1)^{4} (M_{1} + 1)^{4}}$

$(‡)$

First, $M_{1}$ and $M_{2}$ are independent with

$P (M_{i} = m_{i}) = \frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix})}{(_{n / 2}^{n})}$ , $i = 1, 2$ .

Indeed, $M_{i}$ obviously equals the cardinality of the intersection with $[n / 2]$ of a uni-

formly random subset of size $n / 2$ from $[n]$ , which directly implies these formulas.

Thus, each $M_{i}$ has the hypergeometric distribution with parameters $n / 2$ , $n / 2$ , $n / 2$ ; in

other words, $M_{i}$ has the same distribution as the number of red balls in a uniformly

random sample of $n / 2$ balls from an urn containing $n / 2$ red balls and $n / 2$ white balls.

By the independence of $M_{1}$ and $M_{2}$ , we obtain

$P (M_{1} = m_{1}, M_{2} = m_{2}) = \frac{(\begin{matrix} n / 2 \\ m_{1} \end{matrix}) (\begin{matrix} n / 2 \\ m_{2} \end{matrix})}{(_{n / 2}^{n})^{2}}$ $2$ .

It remains to observe that (2.1) and (T) imply

$P (E) = \sum_{m_{1} \geq m_{2}} \frac{(m_{1} - m_{2} + 1)^{4} (n / 2 + 1)^{4}}{(n / 2 - m_{2} + 1)^{4} (m_{1} + 1)^{4}} ċ P (M_{1} = m_{1}, M_{2} = m_{2})$

$\underline{<} \sum_{m_{1}, m_{2}} \frac{(m_{1} - m_{2} + 1)^{4} (n / 2 + 1)^{4}}{(n / 2 - m_{2} + 1)^{4} (m_{1} + 1)^{4}} ċ P (M_{1} = m_{1}, M_{2} = m_{2})$

$= E [\frac{(M_{1} - M_{2} + 1)^{4} (n / 2 + 1)^{4}}{(n / 2 - M_{2} + 1)^{4} (M_{1} + 1)^{4}}]$ ,

and (‡) is proved.

2.3 Asymptotics

The advantage of (‡) is that it allows us to use probabilistic tools exploiting the

independence of the random variables $M_{1}$ and $M_{2}$ . Typically the $M_{i}' s$ are close to

$n / 4$ , while $| M_{1} - M_{2} |$ is of order $n^{1 / 2}$ at most. So, in view of (‡) we expect that

$P (E) = O (n^{- 2})$ .

We now make this argument rigorous. First of all, by the "sample-from-urn" inter-

pretation of $M_{i}$ ,

$E [M_{i}] = \frac{n}{2} \frac{(\begin{matrix} n - 1 \\ n / 2 - 1 \end{matrix})}{(_{n / 2}^{n})}$ $= n / 4$ . (2.3)

Then (see Janson et al. [31, p. 29]) the probability generating function of $M_{i}$ is

dominated by that of Bin(n, 1/4), and consequently for each $t \underline{>} 0$ we have

$P (| M_{i} - n / 4 | \underline{>} t) = O (\exp (- 4 t^{2} / n))$ .

Hence, setting $t = n^{2 / 3}$ we see that

$P (n / 4 - n^{2 / 3} < M_{i} < n / 4 + n^{2 / 3}) \underline{>} 1$ $- e^{- c n^{1 / 3}}$ ,

for some absolute constant $c > 0$ . Introduce the event

$A_{n} = \cap^{2} i = 1 {n / 4 - n^{2 / 3} < M_{i} < n / 4 + n^{2 / 3}}$ .

Combining the estimates for $M_{i}$ , we see that for some absolute constant $c_{1} > 0$ ,

$P (A_{n}) \underline{>} 1$ $- e^{- c_{1} n^{1 / 3}}$

Now the random variable in (‡), call it $X_{n}$ , is bounded by 1, and on the event $A_{n}$ ,

within a factor of $1 + O (n^{- 1 / 3})$ ,

$X_{n} = (\frac{4}{n})^{8} (M_{1} - M_{2} + 1)^{4} (n / 2 + 1)^{4}$

Therefore

$P (E) \underline{<} (\frac{5}{n})^{8} (n / 2 + 1)^{4} E [(M_{1} - M_{2} + 1)^{4}] + O (e^{- c_{1} n^{1 / 3}})$ .

It remains to prove that this expected value is $O (n^{2})$ . Introduce ${\bar{M}}_{i} = M_{i} - E [M_{i}]$ ,

$i = 1, 2$ . Then

$(M_{1} - M_{2} + 1)^{4} = ({\bar{M}}_{1} - {\bar{M}}_{2} + 1)^{4} \underline{<} 27 ({\bar{M}}_{1}^{4} + {\bar{M}}_{2}^{4} + 1)$ ,

$(a + b + c)^{2} \underline{<} 3 (a^{2} + b^{2} + c^{2})$ .

We now demonstrate that $E [{\bar{M}}_{i}^{4}] = O (n^{2})$ . To this end, notice first that $E [{\bar{M}}_{i}^{2}]$ is of

order $n$ exactly. Indeed, extending the computation in (2.3),

$E [M_{i} (M_{i} - 1)] = \frac{n}{2} (\frac{n}{2} - 1)$ $\frac{(\begin{matrix} n - 2 \\ n / 2 - 2 \end{matrix})}{(_{n / 2}^{n})}$

$= \frac{n (n - 2)^{2}}{16 (n - 1)}$ .

Therefore

E $[{\bar{M}}_{i}^{2}] = V a r [M_{i}]$

$= E [M_{i} (M_{i} - 1)] + E [M_{i}] - E^{2} [M_{i}]$

$= \frac{n (n - 2)^{2}}{16 (n - 1)} + \frac{n}{4} - \frac{n^{2}}{16}$ (2.4)

$= \frac{n}{16} + O (1)$ .

Furthermore, as a special instance of the hypergeometrically distributed random vari-

able, $M_{i}$ has the same distribution as the sum of $n / 2$ independent Bernoulli variables

$Y_{j} \in {0, 1}$ (see Vatutin and Mikhailov [38], alternatively [31, p. 30]). Therefore,

(2.4) and the Lindeberg-Feller Central Limit Theorem imply

$\frac{{\bar{M}}_{i}}{\sqrt{n / 16}} \to N (0, 1)$ , (2.5)

where $N (0, 1)$ is the standard normal random variable. In fact, since

$\frac{Y_{j} - E [Y_{j}]}{\sqrt{n / 16}} \to 0$ , $n$ $\to \infty$ ,

we can say more. Indeed, we have (2.5) together with convergence of all the moments

(see Billingsley [4, p. 391]). Therefore, in particular

$\frac{E [{\bar{M}}_{i}^{4}]}{(\sqrt{n / 16})^{4}} \to E [N (0, 1)^{4}]$ , $n$ $\to \infty$ ,

i.e. $E [{\bar{M}}_{i}^{4}] = O (n^{2})$ . This completes the proof of Theorem 1.2.1 (upper bound).

$□$

(JIAPTER 3

THE PROOF OF THE BRUHAT ORDER LOWER

BOUND

In this chapter, we prove Theorem 1.2.1, lower bound. We will actually prove some-

thing better than what was stated there, showing that for each $ε$ $> 0$

$P (π \underline{<} σ) = Ω ((α - ε)^{n})$ ,

where

$(y$ $= 1 \sqrt[1]{} \frac{25497938851324213335}{22!} = 0.70879$ . . . .

First, some preliminaries.

3.1 A Sufficient Condition for Bruhat Comparability

Introduce $π^{*}$ ( $σ^{*}$ resp.), the permutation $π$ ( $σ$ resp.) with the element $n$ deleted.

More generally, for $k \underline{<} n$ , $π^{k *}$ ( $σ^{k *}$ resp.) is the permutation of $[n - k]$ obtained from

$π$ ( $σ$ resp.) by deletion of the $k$ largest elements, $n$ , $n$ $- 1$ , $...$ , $n$ $- k + 1$ . The key to

the proof is the following:

Figure 3.1: $G_{5}$ and an emboldened subgrid $C$ .

Lemma 3.1.1. Let k $\in [n]$ . If every northeastern submatrix of $M (π, σ)$ with at most

k rows contains at least as many crosses as balls, and $π^{k *} \underline{<} σ^{k *}$ , then $π \underline{<} σ$ .

Before proceeding with the proof, we introduce one more bit of notation. Let $G_{n}$ be

the empty $n$ $\times n$ grid depicted in the $M (ċ)' s$ of Figure 1.2. Figure 3.1 is a depiction

of $G_{5}$ and an emboldened northeastern-corner 3 $\times 4$ subgrid of it, denoted by $C$ . If

$C$ is any subgrid of $G_{n}$ , then $M (ċ | C)$ denotes the submatrix of $M (ċ)$ that "sits" on

$C$ . To repeat, the $(0, 1)$ -matrix criterion says that $π \underline{<} σ$ if and only if for each

northeastern-corner subgrid $C$ of $G_{n}$ , we have at least as many crosses as balls in

$M (π, σ | C)$ .

Proof. By the assumption, it suffices to show that the balls do not outnumber crosses

in $M$ ( $π$ , a $| C$ ) for every such subgrid $C$ with strictly more than $k$ rows. Consider any

such $C$ . Let $C^{(k)}$ denote the subgrid formed by the top $k$ rows of $C$ . Given a submatrix

$A$ of $M (π)$ (of $M (σ)$ resp.), let $| A |$ denote the number of columns in $A$ with a cross

(a ball resp.). We need to show

$\| -$		-	-	-
$\oplus$	$- \|$	-	-	-
$\|$	$\|$		$o$
$\|$	$\|$			$o$
$\|$	$\|$	$o$

-	-	$*$	-	$- \|$
-	-	$⊥$	-	$* t$
		$\|$	$\times$	$\|$
	$\times$	$\|$		$\|$
$\times$		$\|$		$\|$

Figure 3.2: Deletion of 2 largest elements of $π$ , $σ$ , and its affect on $C$ .

$| M (π | C) | \underline{>} | M (σ | C) |$ .

By the assumption, we have $| M (π | C^{(k)}) | \underline{>} | M (σ | C^{(k)}) |$ . Write $| M (π | C^{(k)}) | =$

$| M (σ | C^{(k)}) | + λ$ , A $\underline{>} 0$ . We now delete the top $k$ rows from $M (π)$ , $M (σ)$ together

with the $k$ columns that contain the top $k$ crosses in the case of $M (π)$ and the $k$

columns that contain the top $k$ balls in the case of $M (σ)$ . This produces the matrices

$M (π^{k *})$ and $M (σ^{k *})$ . In either case, we obtain the grid $G_{n - k}$ together with a new

northeastern subgrid: $C (π^{k *})$ in the case of $M (π)$ and $C (σ^{k *})$ in the case of $M (σ)$ .

Figure 3.2 is a graphical visualization of this deletion process in the special case

$π = 12534$ , $σ = 45132$ , $k = 2$ and $C$ the 3 $\times 4$ northeastern subgrid of $G_{5}$ . We have

emboldened $C$ in $M (π)$ , $M (σ)$ , and the resulting $C (π^{2 *})$ , $C (σ^{2 *})$ in $M (π^{2 *})$ , $M (σ^{2 *})$

respectively.

Since we delete more columns in the case of $π$ than $σ$ , note that $C (π^{k *}) \underline{\subset} C (σ^{k *})$ as

northeastern subgrids of $G_{n - k}$ . In fact, these grids have the same number of rows,

but $C (π^{k *})$ has A fewer columns. Hence, as $π^{k *} \underline{<} σ^{k *}$ , we have

$| M (π^{k *} | C (π^{k *})) | \underline{>} | M (σ^{k *} | C (π^{k *})) | \underline{>} | M (σ^{k *} | C (σ^{k *})) | - λ$ .

$| M (π | C) | = | M (π | C^{(k)}) | + | M (π^{k *} | C (π^{k *})) |$

$= | M$ (a $| C^{(k)}$ ) $| +$ A $+ | M (π^{k *} | C (π^{k *})) |$

$\underline{>} | M (σ | C^{(k)}) | + | M (σ^{k *} | C (σ^{k *})) |$

$= | M (σ | C) |$ ,

which proves the lemma.

$□$

3.2 A Reduction to Uniforms

For each $k \underline{<} n$ , let $E_{n}$ , $k$ denote the event "every northeast submatrix of the top $k$

rows has at least as many crosses as balls" Then by Lemma 3.1.1,

${π \underline{<} σ} \underline{\supset} E_{n, k} \cap {π^{k *} \underline{<} σ^{k *}}$ .

Now the events $E_{n, k}$ and ${π^{k *} \underline{<} σ^{k *}}$ are independent! So we get

$P (π \underline{<} σ) \underline{>} P (E_{n, k}) P (π^{k *} \underline{<} σ^{k *})$ . (3.1)

For the permutation $π$ ( $σ$ resp.) introduce $l_{i} (π) = π^{- 1} (i)$ ( $l_{i} (σ) = σ^{- 1} (i)$ resp.),

the index of a column that contains a cross (a ball resp.) at the intersection with

row $i$ . In terms of the $l_{i} (ċ)' s$ , $E_{n, k}$ is the event: for each integer $j \underline{<} k$ and $m \underline{<} n$ ,

the number of $l_{n} (π)$ , $p_{n - 1} (π)$ , $...$ , $l_{n - j + 1} (π)$ that are $m$ at least is more than or equal

to the number of $l_{n} (σ)$ , $p_{n - 1} (σ)$ , $...$ , $l_{n - j + 1} (σ)$ that are $m$ at least. We could have

replaced an integer $m \underline{<} n$ with a real number which means that

$E_{n, k} = {(π, σ) : (l (π), l (σ)) \in C_{k}}$ ,

for some cone-shaped (Borel) set $C_{k} \subset R^{2 k}$ ; here $l (π) = {l_{n - i + 1} (π)}_{1 \leq i \leq k}$ , $l (σ) =$

${l_{n - i + 1} (σ)}_{1 \leq i \leq k}$ .

Our task is to estimate sharply $P (E_{n, k})$ for a fixed $k$ , and $n$ $\to \infty$ . Observe first that

$l (π)$ and $l (σ)$ are independent, and each uniformly distributed. For instance

$P (l_{n} (π) = j_{1}, ..., l_{n - k + 1} (π) = j_{k}) = \frac{1}{(n)_{k}}$ , $1 \underline{<} j_{1} \neq ... \neq j_{k} \underline{<} n$ ,

where $(n)_{k} = n (n - 1)$ $... (n - k + 1)$ . Since $(n)_{k} \sim n^{k}$ as $n$ $\to \infty$ , $l_{n} (π)$ , $...$ ,

$p_{n - k + 1} (π)$ are almost independent $[n]$ -uniforms for large $n$ , and fixed $k$ . Let us make

this asymptotic reduction rigorous. Let $U$ be a uniform- $[0, 1]$ random variable, and

let $U_{1}$ , $...$ , $U_{n}$ be independent copies of $U$ . Then each $⌈ n U_{i} ⌉$ is uniform on $[n]$ , and it

is easy to show that

$P$ $(⌈ n U_{1} ⌉ = i_{1}, ..., ⌈ n U_{k} ⌉ = i_{k} | ⌈ n U_{1} ⌉ \neq ... \neq ⌈ n U_{k} ⌉) = \frac{1}{(n)_{k}}$ .

In other words, ${l_{n - i + 1} (π)}_{1 \leq i \leq k}$ has the same distribution as the random vector

$⌈ n U ⌉$ $: = {⌈ n U_{i} ⌉}_{1 \leq i \leq k}$ conditioned on the event $A_{n, k} = {⌈ n U_{1} ⌉ \neq ... \neq ⌈ n U_{k} ⌉}$ .

Analogously ${l_{n - i + 1} (σ)}_{1 \leq i \leq k}$ is distributed as $⌈ n V ⌉$ $: = {⌈ n V_{i} ⌉}_{1 \leq i \leq k}$ conditioned on

$B_{n, k} = {⌈ n V_{1} ⌉ \neq ... \neq ⌈ n V_{k} ⌉}$ , where $V_{1}$ , $...$ , $V_{k}$ are independent $[0, 1]$ -uniforms,

independent of $U_{1}$ , $...$ , $U_{k}$ . We will need yet another event $D_{n, k}$ on which

$\min {\min_{i \neq j} | U_{i} - U_{j} |, \min_{i \neq j} | V_{i} - V_{j} |, m, j n | U_{Reject}, - V_{j} |} > 1 / n$ .

Clearly on $D_{n, k}$

$(⌈ n U ⌉, ⌈ n V ⌉) \in C_{k} \Leftrightarrow (U, V) \in C_{k}$ ;

here $U : = {U_{i}}_{1 \leq i \leq k}$ , $V : = {V_{i}}_{1 \leq i \leq k}$ . In addition $D_{n, k} \underline{\subset} A_{n, k} \cap B_{n, k}$ , and

$P (D_{n, k}^{c}) \underline{<} 2 k^{2} P (| U_{1} - U_{2} | \underline{<} 1 / n) \underline{<} 4 k^{2} / n$ .

Therefore

$P (E_{n, k}) = P ((l (π), l (σ)) \in C_{k})$

$= \frac{P ({(⌈ n U ⌉, ⌈ n V ⌉) \in C_{k}} \cap {A_{n, k} \cap B_{n, k}})}{P (A_{n, k} \cap B_{n, k})}$

$= \frac{P ({(⌈ n U ⌉, ⌈ n V ⌉) \in C_{k}} \cap D_{n, k}) + O (P (D_{n, k}^{c}))}{1 - O (P (D_{n, k}^{c}))}$

$= \frac{P ((U, V) \in C_{k}) + O (k^{2} / n)}{1 - O (k^{2} / n)}$

$= Q_{k} + O (k^{2} / n)$ ,

where $Q_{k} = P ((U, V) \in C_{k})$ . Let us write $P_{n} = P (π \underline{<} σ)$ . Using (3.1) and the last

estimate we obtain then

$P_{n} \underline{>} Q_{k} P_{n - k}$ $(1 + O (k^{2} / n)) = Q_{k} P_{n - k} \exp (O (k^{2} / n))$ , $n$ $> k$ .

Iterating this inequality $⌋ n / k ⌊$ times gives

$P_{n} \underline{>} Q_{k}^{⌋ n / k ⌊} P_{n - ⌋ n / k ⌊ k} \exp [\sum_{j = 0}^{⌋ n / k ⌊ - 1} O (\frac{k^{2}}{n - j k})]$

Since the sum in the exponent is of order $O (k^{2} \log n)$ , we get

$\lim$ inf $\sqrt[n]{P_{n}} \underline{>} \sqrt[k]{Q_{k}}$ , $\forall k \underline{>} 1$ .

Thus

$\lim$ inf $\sqrt[n]{P_{n}} \underline{>} \sup_{k} \sqrt[k]{Q_{k}}$ .

Therefore, for each $k$ and $ε$ $\in (0, \sqrt[k]{Q_{k}})$ , we have

$P_{n} = Ω ((\sqrt[k]{Q_{k}} - ε)^{n})$ . (3.2)

Lemma 3.2.1. As a function of k, $Q_{k}$ is supermultiplicative, i.e. $Q_{k_{1} + k_{2}} \underline{>} Q_{k_{1}} Q_{k_{2}}$

for all $k_{1}$ , $k_{2} \underline{>} 1$ . Consequently there exists $\lim_{k \to \infty} \sqrt[k]{Q_{k}}$ , and moreover

$\lim_{k \to \infty} \sqrt[k]{Q_{k}} = \sup_{k \geq 1} \sqrt[k]{Q_{k}}$ .

Thus we expect that our lower bound would probably improve as $k$ increases.

Proof. $Q_{k}$ is the probability of the event $E_{k} = {(U^{(k)}, V^{(k)}) \in C_{k}}$ ; here $U^{(k)}$ $: =$

${U_{i}}_{1 \leq i \leq k}$ , $V^{(k)} : = {V_{i}}_{1 \leq i \leq k}$ . Explicitly, for each $j \underline{<} k$ and each $c \in [0, 1]$ , the

number of $U_{1}$ , $...$ , $U_{j}$ not exceeding $c$ is at most the number of $V_{1}$ , $...$ , $V_{j}$ not exceeding

$c$ . So $Q_{k_{1} + k_{2}} = P (E_{k_{1} + k_{2}})$ , $Q_{k_{1}} = P (E_{k_{1}})$ , while $Q_{k_{2}} = P (E_{k_{2}}) = P (E_{k_{2}}^{*})$ . Here the

event $E_{k_{2}}^{*}$ means that for each $j^{*} \underline{<} k_{2}$ and each $c \in [0, 1]$ , the number of $U_{i}$ , $i =$

$k_{1} + 1$ , $...$ , $k_{1} + j^{*}$ , not exceeding $c$ is at most the number of $V_{i}$ , $i = k_{1} + 1$ , $...$ , $k_{1} + j^{*}$ ,

not exceeding $c$ . The events $E_{k_{1}}$ and $E_{k_{2}}^{*}$ are independent. Consider the intersection

of $E_{k_{1}}$ and $E_{k_{2}}^{*}$ . There are two cases:

1) $j \underline{<}$ A4. Then the number of $U_{i}$ , $i \underline{<} j$ not exceeding $c$ is at most the number of

$V_{i}$ , $i \underline{<} j$ not exceeding $c$ , as $E_{k_{1}}$ holds.

2) A4 $< j \underline{<}$ A4 $+ k_{2}$ . Then the number of $U_{i}$ , $i \underline{<} j$ , not exceeding $c$ is at most

the number of $V_{i}$ , $i \underline{<}$ A4 not exceeding $c$ (as $E_{k_{1}}$ holds), plus the number of $V_{i}$ ,

A4 $< i \underline{<} j$ , not exceeding $c$ (as $E_{k_{2}}^{*}$ holds). The total number of these $V_{i}$ is the

number of all $V_{i}$ , $i \underline{<} j$ , that are at most $c$ , $c \in [0, 1]$ .

So $E_{k_{1} + k_{2}} \underline{\supset} E_{k_{1}} \cap E_{k_{2}}^{*}$ , and we get $Q_{k_{1} + k_{2}} \underline{>} Q_{k_{1}} Q_{k_{2}}$ . The rest of the statement

follows from a well-known result about super(sub)multiplicative sequences (see P61ya

and Szegö [43, p. 23, ex. 98] $)$ .

Given $1 \underline{<} j \underline{<} i \underline{<} k$ , let $U_{i, j}$ ( $V_{i, j}$ resp.) denote the j-th element in the increasing

rearrangement of $U_{1}$ , $...$ , $U_{i}$ ( $V_{1}$ , $...$ , $V_{i}$ resp.). Then, to put it another way, $Q_{k}$ is

the probability that the $k$ Ehresmann conditions are met by the independent k-

dimensional random vectors $U$ and $V$ , both of which have independent entries. That

is, we check $U_{i, j} > V_{i, j}$ for each $1 \underline{<} j \underline{<} i \underline{<} k$ by performing element-wise comparisons

in the following tableaux:

$U_{k, 1}$ $U_{k, 2}$ $U_{k, 3}$

$U_{k, k}$

$V_{k, 1}$ $V_{k, 2}$ $V_{k, 3}$

$V_{k, k}$

. $ċ$ . . $ċ$ . . $ċ$ . . $ċ$ . . $ċ$ . . $ċ$ . . $ċ$ . . $ċ$ .

$U_{3, 1}$ $U_{3, 2}$ $U_{3, 3}$ $V_{3, 1}$ $V_{3, 2}$ $V_{3, 3}$

$U_{2, 1}$ $U_{2, 2}$ $V_{2, 1}$ $V_{2, 2}$

$U_{1, 1}$ $V_{1, 1}$

3.3 An Algorithm to Maximize the Bound

What's left is to explain how we determined a $=$ 0.70879....

It should be clear that whether or not $(U^{(k)}, V^{(k)})$ is in $C_{k}$ depends only on the

size ordering of $U_{1}$ , $...$ , $U_{k}$ , $V_{1}$ , $...$ , $V_{k}$ . There are $(2 k)!$ possible orderings, all being

equally likely. Thus $Q_{k} = N_{k} / (2 k)!$ , where $N_{k}$ is the number of these linear orderings

satisfying this modified Ehresmann criterion. Since the best constant in the lower

exponential bound is probably $\lim_{k \to \infty} \sqrt[k]{Q_{k}}$ , our task was to compute $N_{k}$ for $k$ as

large as our computer could handle. ( "Probably", because we do not know for certain

that $\sqrt[k]{Q_{k}}$ increases with $k .$ )

Here is how $N_{k}$ was tabulated. Recursively, suppose we have determined all $N_{k - 1}$

orderings of $x_{1}$ , $...$ , $x_{k - 1}$ , $y_{1}$ , $...$ , $y_{k - 1}$ such that $(x^{(k - 1)}, y^{(k - 1)}) \in C_{k - 1}$ . Each such

ordering can be assigned a2 $(k - 1)$ -long sequence of $O' s$ and l's, $O' s$ for $x_{i}$ 's and Fs

for $y_{j}' s$ , $1 \underline{<} i$ , $j \underline{<} k - 1$ . Each such sequence meets the ballot-theorem condition:

as we read it from left to right the number of Fs never falls below the number of

$O' s$ . We also record the multiplicity of each sequence, which is the number of times

it is encountered in the list of all $N_{k - 1}$ orderings. The knowledge of all $2 (k - 1)$ -long

ballot-sequences together with their multiplicities is all we need to compile the list of

all $2 k$ -long ballot-sequences with their respective multiplicities.

For $k = 1$ , there is only one ballot-sequence to consider, namely 10, and its multiplicity

is 1. So $N_{1} = 1$ , and

$Q_{1} = 1 / 2!$ .

Passing to $k = 2$ , we must count the number of ways to insert 1 and 0 into 10 so that

we get a 4-long ballot-sequence of two $O' s$ and two Fs. Inserting 1 at the beginning,

giving 110, we can insert 0 into positions 2, 3 or 4, producing three ballot-sequences

1010, 1100, 1100,

respectively. (Inserting 0 into position 1 would have resulted in 0110 which is not a

ballot-sequence.) Similarly, inserting 1 into position 2, we get 110, and inserting 0

under the ballot condition gives th $r e e$ ballot-sequences

1010, 1100, 1 tOO.

Finally, inserting 1 at the end, giving 101, we can only insert 0 at the end, obtaining

one ballot-sequence

toto.

Hence, starting from the ballot-sequence 10 of multiplicity 1, we have obtained two

4-long ballot-sequences, 1010 of multiplicity 3 and 1100 of multiplicity 4. Therefore

$N_{2} = 3 + 4 = 7$ , and

$Q_{2} = 7 / 4!$ .

Pass to $k = 3$ . Sequentially we insert 1 in each of 5 positions in the ballot-sequence

1010, and then determine all positions for the new 0 which would result in a $6$ -long

ballot-sequence. While doing this we keep track of how many times each $6$ -long

ballot-sequence is encountered. Multiplying these numbers by 3, the multiplicity of

1010, we obtain a list of 6-long ballot-sequences spawned by 1010 with the number

of their occurrences. We do the same with the second sequence 1100. Adding the

numbers of occurrences of each 6-long ballot-sequence for 1010 and 1tOO we arrive at

the following list of five 6-long ballot-sequences with their respective multiplicities:

tttooo : 36,

ttotoo : 32,

ttooto : 24,

tottoo : 24,

tototo : 19.

Therefore $N_{3} = 36 + 32 + 24 + 24 + 19$ $= 135$ , and

$Q_{3} = 135 / 6!$ .

Table 3.1: Exact computation of $N_{k}$ for smallish $k$ .

We wrote a computer program for this algorithm. Pushed to its limit, the computer

delivered table 3.1.

Combining (3.2) and the value of $1 \sqrt[1]{Q_{11}}$ in this table, we see that for each $ε > 0$ ,

$P_{n} = Ω ((1 \sqrt[1]{Q_{11}} - ε)^{n}) = Ω ((0.708 ... - ε)^{n})$ . $□$

The numbers $\sqrt[k]{Q_{k}}$ increase steadily for $k < 12$ , so at this moment we would not rule

out the tantalizing possibility that $\sqrt[k]{Q_{k}} \to 1$ as $k \to \infty$ . Determination of the actual

limi $t$ is a challenging open problem. The proof just given only involves mention of

the $(0, 1)$ -matrix criterion, but it was the Ehresmann criterion that actually inspired

our initial insights.

(JIAPTER 4

AN EXTENSION TO CHAINS IN BRUHAT ORDER

Our goal in this chapter is to prove Theorem 1.2.2, which extends our upper bound

result on Bruhat-comparability of permutation-pairs. Namely, we will show that for

$π_{1}$ , $...$ , $π_{r} \in S_{n}$ selected independently and uniformly at random, we have

$P (π_{1} \underline{<} ... \underline{<} π_{r}) = O (n^{- r (r - 1)})$ .

So the number of length $r$ chains in the Bruhat poset is of order at most $n^{- r (r - 1)}$ $(n!)^{r}$ .

Our basic approach will be at its core, the same as it was for permutation-pairs, but

our enumerative techniques will mimic those established by Gessel and Viennot to

count various classes of non-intersecting lattice paths (see [26]). These same tech-

niques are also highlighted in Bressoud's book [13], which recounts the proof of the

Alternating-Sign Matrix Conjecture.

4.1 The General Setup

First, some preliminaries. Recall the "superimposed" matrix $M (π, σ)$ of $\times' s$ and $\circ$ 's

we introduced earlier ( $\times' s$ for $π$ and $\circ$ 's for $σ$ ). Let's introduce the analogous more

general matrix $M (π_{1}$ , . . . , $π_{r})$ , where we place $\times_{j}' s$ at positions $(i, π_{j} (i))$ , $1 \underline{<} i \underline{<} n$ ,

$1 \underline{<} j \underline{<} r$ . Here, we read rows bottom to top and columns left to right. For instance,

if $π_{1} = 21543$ , $π_{2} = 25143$ and $π_{3} =$ 54213, we have

$M (π_{1}, π_{2}, π_{3}) =$

1234 5

Given a set of rows $I \underline{\subset} [n]$ and columns $J \underline{\subset} [n]$ , let $M (ċ)_{I, J}$ denote the submatrix

of $M (ċ)$ corresponding to rows I and columns $J$ . Again, rows are labeled 1, 2, . . . ' $n$

from bottom to top, and columns are labeled 1, 2, . . . ' $n$ from left to right. The $(0, 1) -$

matrix criterion says that $π_{1} \underline{<} ... \underline{<} π_{r}$ if and only if for each southwest submatrix

$M (π_{1}$ , . . . , $π_{r})_{[μ], [ν]}$ , $μ$ , $U$ $\in [n]$ , we have

$♯$ $\times_{1}' s \underline{>}$ . . . $\underline{>} ♯$ $\times_{r}$ 's.

Note that this is the case in $M (π_{1}, π_{2}, π_{3})$ above, so that we have $π_{1} \underline{<} π_{2} \underline{<} π_{3}$ . One

more bit of notation: let $M_{j} (μ, u)$ denote the number of $\times_{j}' s$ in $M (π_{j})_{[μ]}$ , $[ν]$ . In this

notation,

$π_{1} \underline{<}$ . . . $\underline{<} π_{r}$ $\Leftrightarrow$ $M_{1} (μ, ν) \underline{>}$ . . . $\underline{>} M_{r} (μ, ν)$ $\forall μ$ , $U$ $\in [n]$ .

4.2 A Tractable Necessary Condition

Now, as in the case of permutation-pairs, we need to find an event which contains

${π_{1} \underline{<} ... \underline{<} π_{r}}$

that is more amenable to enumerative techniques. For simplicity, let's assume $n$ is

even and fix $μ = u$ $= n / 2$ (in what follows, only minor modifications are necessary for

$n$ odd). In our computations, we will primarily concentrate on the single southwest

submatrix

$M_{s w} (π_{1}, ..., π_{r}) : = M (π_{1}, ..., π_{r})_{[n / 2], [n / 2]}$ .

We similarly denote by

$M_{n w} (π_{1}, ..., π_{r})$ , $M_{n e} (π_{1}, ..., π_{r})$ , $M_{s e} (π_{1}, ..., π_{r})$

the northwest, northeast and southeast $n / 2 \times n / 2$ subsquares of $M (π_{1}$ , . . . , $π_{r})$ , re-

spectively. If $π_{1} \underline{<} ... \underline{<} π_{r}$ , it is necessary that

$M_{1} (i, n / 2) \underline{>} ... \underline{>} M_{r} (i, n / 2)$ , $i = 1$ , $...$ , $n / 2$ . (4.1)

This is analogous to the necessary condition we considered for permutation-pairs: we

read off rows of $M_{s w}$ $(π_{1}$ , . . . ' $π_{r})$ one at a time, keeping track of the total number of

$\times_{j}' s$ encountered thus far, $1 \underline{<} j \underline{<} r$ . If $π_{1} \underline{<} ... \underline{<} π_{r}$ , at any intermediate point in

this "reading-off" process, we must never have encountered more $\times_{j}' s$ than $\times_{j - 1}$ 's,

$1 < j \underline{<} r$ .

Let $E_{s w}$ denote the event described in (4.1). Recalling our work with permutation-

pairs, we extract similar events necessary for ${π_{1} \underline{<} ... \underline{<} π_{r}}$ by considering columns

in the northwest $n / 2 \times n / 2$ square (denote this event $E_{n w}$ ), rows in the northeast

square $(E_{n e})$ and columns in the southeast square $(E_{s e})$ . Then

${π_{1} \underline{<} ... \underline{<} π_{r}} \underline{\subset} E : = E_{s w} \cap E_{n w} \cap E_{n e} \cap E_{s e}$ ,

and unlike the set ${π_{1} \underline{<} ... \underline{<} π_{r}}$ , we can compute $| E |!$ Namely, our task is reduced

to showing

$P (E) = \frac{| E |}{(n!)^{r}} = O (n^{- r (r - 1)})$ .

We have seen Figure 4.1 before, but we show it again here to aid in visualizing the

"reading-off" process used to generate the restrictions defining the event $E$ .

4.3 The Core Counting Problem

If a row (column) of a submatrix $M (π_{j})_{I, J}$ contains a marked entry, we say that it

supports the submatrix. Clearly the number of supporting rows (columns) equals

the number of marked entries in $M (π_{j})_{I, J}$ . Now, given $π_{j}$ , $1 \underline{<} j \underline{<} r$ , let $M_{j} : =$

$M_{j} (n / 2, n / 2)$ , the total number of rows that support $M_{s w} (π_{j})$ . Then $M_{n w} (π_{j})$ is

supported by $n / 2 - M_{1}$ columns. The same holds for the southeastern corner, $M_{s e} (π_{j})$ .

Obviously the northeastern submatrix $M_{n e} (π_{j})$ is supported by $M_{j}$ rows. Then we

have

$M (π, 0)$

$↓$

$|$

Figure 4.1: Finding a necessary condition for $π_{1} \underline{<} ... \underline{<} π_{r}$ .

$P (E) =$ $\sum$ $P (E (m_{1}, ..., m_{r}))$ , (4.2)

$m_{1}$ , . . . , $m_{r}$

$E$ $(m_{1}, ..., m_{r}) : = E \cap {(π_{1}, ..., π_{r}) : M_{1} = m_{1}, ..., M_{r} = m_{r}}$ .

Clearly, by the $(0, 1)$ -matrix criterion, if there is $1 \underline{<} i < j \underline{<} r$ such that $m_{i} < m_{j}$ ,

then $E (m_{1}$ , . . . , $m_{r}) = \emptyset$ . Otherwise, we claim:

Theorem 4.3.1. For $m_{1} \underline{>} ... \underline{>} m_{r}$ ,

$P (E$ ( $m_{1}$ , . . . , $m_{r}$ ) $) = [_{1 \leq} I I_{\leq r} \frac{(m_{i} - m_{j} + j - i) (n / 2 + j - i)}{(m_{i} + j - i) (n / 2 - m_{j} + j - i)}]^{4}$ . $\prod_{i = 1}^{r} \frac{(_{m_{i}}^{n / 2}) (_{n / 2 - m_{i}}^{n / 2})}{(_{n / 2}^{n})}$ .

This result is really the crux of our argument. The proof, however, will take a little

work. We present it in three steps.

Proof. Let us assume we are on the event $E (m_{1}$ , . . . , $m_{r})$ and that $m_{1} \underline{>} ... \underline{>} m_{r}$ .

STEP 1. As promised, we first concentrate on the southwest $n / 2 \times n / 2$ subsquare

$M_{s w}$ $(π_{1}$ , . . . , $π_{r})$ . For each $1 \underline{<} j \underline{<} r$ , we need to choose $m_{j}$ rows to support $M_{s w} (π_{j})$

in such a way that $E_{s w}$ is satisfied. We claim that the number of ways to choose these

supporting rows, which we denote $N_{n / 2}$ $(m_{1}$ , . . . , $m_{r})$ , is given by the determinant-type

formula

(4.3)

$N_{n / 2} (m_{1}, ..., m_{r}) = \det [$ $]_{i, j = 1}^{r}$ ;

here $i$ is the row index, and $j$ the column index. To prove (4.3), we will exploit a

connection with non-intersecting lattice paths implicit in the restrictions defining $E_{s w}$ .

As we have already mentioned, these enumerative techniques were first introduced

by Gessel and Viennot [26], and were highlighted by Bressoud [13].

For each $j \in [r]$ , we construct a lattice path associated with $M_{s w} (π_{j})$ as follows: start

at the point $(j, - j)$ in the plane. If the first row of $M_{s w} (π_{j})$ contains a marked entry,

execute the move $(0, 1)$ . Otherwise, execute the move $(1, 0)$ . In general, when looking

at the i-th row of $M_{s w} (π_{j})$ , $1 \underline{<} i \underline{<} n / 2$ , we move from our current position up 1 unit

if the i-th row contains a marked entry, and move right 1 unit otherwise. This way,

$M_{s w} (π_{j})$ generates a lattice path consisting of unit moves $(0, 1)$ or $(1, 0)$ , connecting

the point $(j, - j)$ with $(n / 2 - m_{j} + j, m_{j} - j)$ .

Now, by considering all $r$ of these paths together in the plane, we get what is known

as a nest of lattice paths. The restrictions defining $E_{s w}$ imply that the nest of $r$

lattice paths we have just constructed is non-intersecting , i.e. no two paths touch

each other. So to prove the formula (4.3) we need only show that this determinant

counts the total number of these nests of $r$ non-intersecting lattice paths, with moves

$(0, 1)$ and $(1, 0)$ , joining the points $S$ $: = {(j, - j) : j \in [r]}$ to the points $F : =$

${(n / 2 - m_{i} + i, m_{i} - i) : i \in [r]}$ . Figure 4.2 is an illustration of one such nest of

$r = 7$ paths.

To count the number of these non-intersecting nests, we instead consider the collection

of all nests of $r$ lattice paths, with moves $(0, 1)$ and $(1, 0)$ , joining the points of $S$ to

the points of $F$ . We require only that no two of the $r$ paths in this nest begin at the

same point or end at the same point, with no further restrictions. In particular, such

a nest of $r$ lattice paths uses every point from both $S$ and $F$ . This allows for some

very tangled nests, like the one shown in Figure 4.3.

To weed out the intersecting nests from the non-intersecting ones, we will employ a

special inclusion-exclusion type argument which gives rise to a sum over permutations

of $[r]$ . Each nest gives rise to a permutation of $[r]$ as follows: define the i-th path

to be the one that ends at $(n / 2 - m_{i} + i, m_{i} - i)$ , $i \in [r]$ . If the i-th path starts at

$(j, - j)$ , $j \in [r]$ , then we define $σ (i) = j$ . For instance, the tangled nest in Figure 4.3

corresponds to the permutation $σ =$ 3512476.

$(n / 2 - m_{1} + 1, m_{1} - 1)$

(1,-1)

$(n / 2 - m_{7} + 7$ , $m_{7} - 7$

(7,-7)

Figure 4.2: A non-intersecting nest of 7 lattice paths.

Figure 4.3: An intersecting nest of 7 lattice paths.

On the other hand, given $σ \in S_{r}$ , in order that a nest give rise to a in this cor-

respondence the i-th lattice path must end at $(n / 2 - m_{i} + i, m_{i} - i)$ and begin at

$(σ (i), - σ (i))$ , and so takes a total of $m_{i} - i + σ (i)$ steps northward and $n / 2 - m_{i} + i - σ (i)$

steps eastward, $i \in [r]$ . Hence, the total number of nests corresponding to the per-

mutation a equals

$\prod_{i = 1}^{r}$ .

Introduce

$I (σ) : = | {(i, j) : 1 \underline{<} i < j \underline{<} r, σ^{- 1} (i) > σ^{- 1} (j)} |$ ,

the inversion number of $σ$ . We claim that the number of nests of $r$ non-intersecting

lattice paths joining $S$ to $F$ equals

(4.4)

$\sum_{σ \in S_{r}} (- 1)^{1 (σ)} \prod_{i = 1}^{r} (_{m_{i} - i +} n / 2$ a $(i)) = \det [$ $]_{i, j = 1}^{r}$ ,

which proves the formula (4.3).

To prove (4.4), notice that this determinant sums over all possible nests, both in-

tersecting and non-intersecting, where each nest is counted as +1 if the inversion

number of the corresponding a is even, and as -1 otherwise. If a nest happens to be

non-intersecting, then the corresponding permutation is the identity, 12 $... n$ , which

has inversion number 0, and so these nests are counted as +1. We need to show that

everything else in this sum cancels. To do this, we will pair intersecting nests up,

one corresponding to a permutation with an even inversion number the other an odd

inversion number.

Let a nest $N$ with at least one intersection point be given, and let $σ \in S_{r}$ be its

corresponding permutation. Consider the intersection point $(x, y)$ furthest to the

right in $N$ . If there is more than one intersection point in this column, let $(x, y)$ be

the one that is highest. In Figure 4.3, this is the point $(13, 2)$ . We now "swap tails"

Figure 4.4: "Swapping" the tails in Figure 4.3.

at $(x, y)$ . Specifically, if the paths cross each other at $(x, y)$ , we swap the tails so

that they just meet, and vice versa in the other situation. Figure 4.4 is a graphical

visualization of this "swapping" process in the case of our running example Figure

4.3.

Doing this, we get a new intersecting nest $N^{'}$ that differs from $N$ only at this "swap-

ping point, $(x, y)$ . Let $σ^{'} \in S_{r}$ denote the permutation corresponding to $N^{'}$ . By

our choice of intersection point $(x, y)$ , it is clear that $σ^{'}$ only differs from a by a

single adjacent swap of entries in $σ$ . For instance, in our Figure 4.3 example, we have

$σ =$ 3512476 and $σ^{'} =$ 3512746. In general we will have $I (σ^{'}) = I (σ) \pm 1$ , and so this

pair of intersecting nests cancel each other out in the sum (4.4). Therefore, what we

claimed in (4.4) (and hence (4.3) also) is proved.

STEP 2. Next, we claim that formula (4.3) implies

$P (E (m_{1}, ..., m_{r})) = (\det [$ $]_{i, j = 1}^{r})^{4} ċ \frac{\prod_{i = 1}^{r} [(m_{i}!)^{2} (n / 2 - m_{i})!^{2}]}{(n!)^{r}}$ . (4.5)

As a first step to the proof of (4.5), we notice that we have shown something more

general regarding the count $N_{n / 2}$ $(m_{1}$ , . . . , $m_{r})$ . Consider the following ballot-counting

problem: suppose we have $r$ canditates, $C_{1}$ , $...$ , $C_{r}$ , running for election, receiving a

total of $μ_{1} \underline{>} ... \underline{>} μ_{r}$ votes respectively. Suppose we count the votes in a rather

peculiar way: we have a total of $l J$ ballot boxes arranged in a row. Each box is

allowed to have at most one vote for each candidate with no further restrictions. In

particular, a given box could possibly be empty, and may have at most $r$ ballots in it,

one cast for each candidate. We open the ballot boxes one at a time, keeping track

of the cumulative total votes cast for each candidate at every intermediate point. We

wish to know the total number of allocations of ballots in boxes so that at each of

these intermediate points, we have $C_{1}$ with at least as many votes as $C_{2}$ , who in turn

has at least as many votes as $C_{3}$ , and so on. By our very derivation above this count

is given by $N_{U} (μ_{1}, ..., μ_{r})$ . Namely, we have proved:

Lemma 4.3.2. For the ballot-counting problem above, we have

$□$

$N_{U} (μ_{1}, ..., μ_{r}) = \det [$ $]_{i, j = 1}^{r}$

What's more we claim that

$N_{U} (ν - μ_{r}, ..., u - μ_{1}) = N_{U} (μ_{1}, ..., μ_{r})$ . (4.6)

Indeed, by Lemma 4.3.2, the left-hand side is given by

$N_{U} (ν - μ_{r}, ..., u - μ_{1}) = \det [$ $]_{i, j = 1}^{r}$

$= \det [$ $]_{i, j = 1}^{r}$

We now switch row $i$ with row $r - i + 1$ , and column $j$ with column $r - j + 1$ , $i$ , $j \in [r]$ .

This has no effect on the determinant. Hence

$N_{U} (ν - μ_{r}, ..., u - μ_{1}) = \det [$ $]_{i, j = 1}^{r} = N_{U} (μ_{1}, ..., μ_{r})$ ,

and formula (4.6) is proved.

We now prove (4.5). First of all, we have already seen that the number of allow-

able supporting-row selections in the southwest subsquare, subject to the restrictions

defining $E_{s w}$ is given by the count in (4.3). A second factor (4.3) comes from choosing

supporting-rows subject to the restrictions defining $E_{n e}$ in the northeast subsquare.

By considering supporting- column selections in the northwest subsquare, subject to

$E_{n w}$ , Lemma 4.3.2 together with equation (4.6) tell us that the total number of al-

lowable supporting-column selections equals

$N_{n / 2}$ $(n / 2 - m_{r}, ..., n / 2 - m_{1}) = N_{n / 2} (m_{1}, ..., m_{r}) = \det [$ $]_{i, j = 1}^{r}$

also, thus giving a third factor. Analogously, a fourth factor comes from considering

supporting-column selections in the southeast subsquare, subject to the restrictions

defining $E_{s e}$ . So by multiplying these four factors (4.3) we obtain the total number of

row and column selections on the event $E$ $(m_{1}$ , . . . , $m_{r})$ subject to all four restrictions

defining $E!$

Once such a row-column selection has been made, we have determined which rows

and columns support the four submatrices of $M (π_{i})$ , $i \in [r]$ . Consider, for instance,

the southwest corner of $M (π_{1})$ . We have selected $m_{1}$ rows (from the first $n / 2$ rows)

supporting $M_{s w}$ $(π_{1})$ , and we have selected $n / 2 - m_{1}$ columns (from the first $n / 2$

columns) supporting $M_{n w} (π_{1})$ . Then it is the remaining $n / 2 - (n / 2 - m_{1}) = m_{1}$

columns that support $M_{s w}$ $(π_{1})$ . The number of ways to match these $m_{1}$ rows and

$m_{1}$ columns, thus to determine $M_{s w}$ $(π_{1})$ completely, is $m_{1}!$ . The northeast corner

contributes another $m_{1}!$ , while each of the two other corners contributes $(n / 2 - m_{1})!$ ,

whence the overall matching factor is $(m_{1}!)^{2} (n / 2 - m_{1})!^{2}$ . In general, the matching

factor for $π_{i}$ is $(m_{i}!)^{2} (n / 2 - m_{i})!^{2}$ , $i \in [r]$ . Multiplying the number of admissible row-

column selections by the resulting total matching factor $\prod_{i = 1}^{r} [(m_{i}!)^{2} (n / 2 - m_{i})!^{2}]$ and

dividing by $(n!)^{r}$ , we obtain the formula (4.5).

STEP 3. As a final step in the proof of Theorem 4.3.1, we show that

$\det [$ $]_{i, j = 1}^{r} =$ $... 1 \leq \prod_{i < j \leq r} \frac{(m_{i} - m_{j} + j - i) (n / 2 + j - i)}{(m_{i} + j - i) (n / 2 - m_{j} + j - i)}$ .

(4.7)

By putting (4.7) into equation (4.5), we leave it to the interested reader to verify that

we get the formula stated in the theorem.

First of all, we note that, for $j > i$ ,

$= \frac{(n / 2)!}{(m_{i} + j - i) ... (m_{i} + 1) m_{i}! (n / 2 - m_{i} + i - j)!}$

$= \frac{(n / 2 - m_{i}) (n / 2 - m_{i} - 1) ... (n / 2 - . m_{i} + i + 1 - j)}{(m_{i} + j - i) (m_{i} + j - i - 1) ċ ċ (m_{i} + 1)}$

$= \frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix})}{(m_{i} + r - i) ... (m_{i} + 1) (n / 2 - m_{i} + i - 1)}$ $... (n / 2 - m_{i} + 1)$

$\times (n / 2 - m_{i} + i - 1) (n / 2 - m_{i} + i - 2) ... (n / 2 - m_{i} + i + 1 - j)$

$\times (m_{i} + j - i + 1) (m_{i} + j - i + 2) ... (m_{i} + r - i)$

$= \frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix})}{(m_{i} + r - i) ... (m_{i} + 1) (n / 2 - m_{i} + i - 1)}$ $... (n / 2 - m_{i} + 1)$

$\times [- (x_{i} + b_{2})] [- (x_{i} + b_{3})] ... [- (x_{i} + b_{j})]$

$\times (x_{i} + a_{j + 1}) (x_{i} + a_{j + 2}) ... (x_{i} + a_{r})$ , (4.8)

where $x_{s} : = m_{s} -$ $(s - 1)$ , $1 \underline{<} s \underline{<} r$ , $a_{t} : = t - 1$ and $b_{t} : = - n / 2 + t - 2, 2 \underline{<} t \underline{<} r$ .

Similarly, for $j < i$ ,

$= \frac{(n / 2) .!}{(m_{i} + j - i)! (n / 2 - m_{i} + i - j) ċ ċ (n / 2 - m_{i} + 1) (n / 2 - m_{i})!}$

$= \frac{m_{i} (m_{i} - 1) ... (m_{i} + j - i + . 1)}{(n / 2 - m_{i} + i - j) (n / 2 - m_{i} + i - j - 1) ċ ċ (n / 2 - m_{i} + 1)}$

$= \frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix})}{(m_{i} + r - i) ... (m_{i} + 1) (n / 2 - m_{i} + i - 1)}$ $... (n / 2 - m_{i} + 1)$

$\times (n / 2 - m_{i} + i - 1) (n / 2 - m_{i} + i - 2) ... (n / 2 - m_{i} + i + 1 - j)$

$\times (m_{i} + j - i + 1) (m_{i} + j - i + 2) ... (m_{i} + r - i)$

$= \frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix})}{(m_{i} + r - i) ... (m_{i} + 1) (n / 2 - m_{i} + i - 1)}$ $... (n / 2 - m_{i} + 1)$

$\times [- (x_{i} + b_{2})] [- (x_{i} + b_{3})] ... [- (x_{i} + b_{j})]$

$\times (x_{i} + a_{j + 1}) (x_{i} + a_{j + 2}) ... (x_{i} + a_{r})$ , (4.9)

Obviously, for $j = i$ the identities (4.8) and (4.9) hold also. Hence, we obtain

$\det [$ $]_{i, j = 1}^{r}$

$= I I$ $\frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix})}{(m_{i} + r - i) ... (m_{i} + 1) (n / 2 - m_{i} + i - 1)}$ $... (n / 2 - m_{i} + 1)$

$\times \det [[- (x_{i} + b_{2})] ... [- (x_{i} + b_{j})] (x_{i} + a_{j + 1}) ... (x_{i} + a_{r})]_{i, j = 1}^{r}$

$=$ $... 1 \leq \prod_{i < j \leq r} \frac{1}{(m_{i} + j - i) (n / 2 - m_{j} + j - i)}$

$\times \det [[- (x_{i} + b_{2})] ... [- (x_{i} + b_{j})] (x_{i} + a_{j + 1}) ... (x_{i} + a_{r})]_{i, j = 1}^{r}$ , (4.10)

so our task is reduced to computing the last determinant in (4.10). For this, we

apply the following result of Krattenthaler [35], which extends the Vandermonde

determinant :

Theorem 4.3.3. (Krattenthaler's formula) Given arbitrary values for $x_{1}$ , . . . , $x_{r}$ ,

$a_{2}$ , . . . ' $a_{r}$ , and $b_{2}$ , . . . ' $b_{r}$ , we have

$\det [(x_{i} + b_{2}) ... (x_{i} + b_{j}) (x_{i} + a_{j + 1}) ... (x_{i} + a_{r})] i, j = 1 r$

$= I I (x_{i} - x_{j}) I I (b_{i} - a_{j}) 1 \leq \leq r 2 \leq \leq r$ . $□$

In order to use this result, we must factor $(- l)^{}$ out of column $j$ , $1 \underline{<} j \underline{<} r$ , in the

last determinant in (4.10). Doing this, we obtain

$\det [[- (x_{i} + b_{2})] ... [- (x_{i} + b_{j})] (x_{i} + a_{j + 1}) ... (x_{i} + a_{r})]_{i, j = 1}^{r}$

$= (- 1)^{(_{2}^{r})} \det [(x_{i} + b_{2}) ... (x_{i} + b_{j}) (x_{i} + a_{j + 1}) ... (x_{i} + a_{r})]_{i, j = 1}^{r}$

$= (- 1)^{(_{2}^{r})} \prod_{1 \leq i < j \leq r} (x_{i} - x_{j}) \prod_{2 \leq i \leq j \leq r} (b_{i} - a_{j})$

$= \prod_{1 \leq i < j \leq r} (x_{i} - x_{j}) \prod_{2 \leq i \leq j \leq r} (a_{j} - b_{i})$ , (4.11)

where the second to last equality follows from Krattenthaler's formula. By our defi-

nition of $x_{s}$ , $a_{t}$ and $b_{t}$ , (4.11) implies

$\det [[- (x_{i} + b_{2})] ... [- (x_{i} + b_{j})] (x_{i} + a_{j + 1}) ... (x_{i} + a_{r})]_{i, j = 1}^{r}$

$= \prod_{1 \leq i < j \leq r} (x_{i} - x_{j}) \prod_{2 \leq i \leq j \leq r} (a_{j} - b_{i})$

$= \prod_{1 \leq i < j \leq r} (m_{i} - m_{j} + j - i) \prod_{2 \leq i \leq j \leq r} (n / 2 + j - i + 1)$

$= \prod_{1 \leq i < j \leq r} [(m_{i} - m_{j} + j - i) (n / 2 + j - i)]$ . (4.12)

Combining (4.10) with (4.12), formula (4.7) is proved and hence so is Theorem 4.3.1.

$□$

4.4 A Probabilistic Simplification

Armed with Theorem 4.3.1, and with the combinatorial part behind us, the rest is

relatively straightforward. First, we claim that

$P (E) \underline{<} E [\prod_{1 \leq i < j \leq r} \frac{(M_{i} - M_{j} + j - i)^{4} (n / 2 + j - i)^{4}}{(M_{i} + j - i)^{4} (n / 2 - M_{j} + j - i)^{4}}]$ , (4.13)

where, to repeat, $M_{i} : = M_{i} (n / 2, n / 2)$ , the total number of rows that support $M_{s w} (π_{j})$ .

It should be clear that the $M_{i}$ are independent, with $M_{i} = D M$ , a hypergeometric

random variables with parameters $n / 2$ , $n / 2$ , $n / 2$ . That is, the $M_{i}$ are indepedent

copies of $M$ , which in turn equals the number of red balls in a uniformly random

sample of size $n / 2$ from an urn containing a total of $n$ balls, $n / 2$ of them red and $n / 2$

white. In particular

$P (M_{i} = m_{i}, i \in [r]) = \prod_{i = 1}^{r} P (M_{i} = m_{i}) = \prod_{i = 1}^{r} \frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix}) (\begin{matrix} n / 2 \\ n / 2 - m_{i} \end{matrix})}{(_{n / 2}^{n})}$ .

(4.14)

Now (4.13) follows easily from (4.2), Theorem 4.3.1 and (4.14):

$P (E) =$ $\sum$

$m_{1} \geq ... \geq m_{r} \prod_{1 \leq i < j \leq r} \frac{(m_{i} - m_{j} + j - i)^{4} (n / 2 + j - i)^{4}}{(m_{i} + j - i)^{4} (n / 2 - m_{j} + j - i)^{4}}$ . $\prod_{i = 1}^{r} \frac{(\begin{matrix} n / 2 \\ m_{i} \end{matrix}) (\begin{matrix} n / 2 \\ n / 2 - m_{i} \end{matrix})}{(_{n / 2}^{n})}$

$\underline{<} \sum_{m_{1}, ..., m_{r}} \prod_{1 \leq i < j \leq r} \frac{(m_{i} - m_{j} + j - i)^{4} (n / 2 + j - i)^{4}}{(m_{i} + j - i)^{4} (n / 2 - m_{j} + j - i)^{4}} ċ P (M_{i} = m_{i}, i \in [r])$

$= E [_{1 \leq} I I_{\leq r} \frac{(M_{i} - M_{j} + j - i)^{4} (n / 2 + j - i)^{4}}{(M_{i} + j - i)^{4} (n / 2 - M_{j} + j - i)^{4}}]$

Of course, this runs parallel to what we did for permutation-pairs.

4.5 Asymptotics

Next, as we did in the case $r = 2$ also, we finish the argument by using known prop-

erties of the random variables $M_{i}$ . Namely, it remains to prove that this expectation

is $O (n^{- r (r - 1)})$ . To avoid unnecessarily repeating things we did for the case $r = 2$ ,

suffice it to say that the $M_{i}' s$ are close to their expectation, $n / 4$ , with exponentially

high probability (see Janson et al. [31, p. 29]). In particular, there is an absolute

constant $c > 0$ such that

$E [\prod_{1 \leq i < j \leq r} \frac{(M_{i} - M_{j} + j - i)^{4} (n / 2 + j - i)^{4}}{(M_{i} + j - i)^{4} (n / 2 - M_{j} + j - i)^{4}}]$

$= O (E [\prod_{1 \leq i < j \leq r} \frac{(M_{i} - M_{j} + j - i)^{4} (n / 2 + j - i)^{4}}{(n / 4 + j - i)^{4} (n / 2 - n / 4 + j - i)^{4}}] + e^{- c n^{1 / 3}})$

$= O (n^{- 4 (_{2}^{r})} E [\prod_{1 \leq i < j \leq r} (M_{i} - M_{j} + j - i)^{4}$

$+ e^{- c n^{1 / 3}})$ ,

so we will be done if we can prove that

$E [\prod_{1 \leq i < j \leq r} (M_{i} - M_{j} + j - i)^{4}$

$= O (n^{2 (_{2}^{r})})$ . (4.15)

This will not be difficult, given our careful approach to the similar problem for

permutation-pairs. As we did there, introduce $μ_{i} = M_{i} - E [M_{i}]$ , $i \in [r]$ . Then

$\prod_{1 \leq i < j \leq r} (M_{i} - M_{j} + j - i)^{4} = \prod_{1 \leq i < j \leq r} (μ_{i} - μ_{j} + j - i)^{4}$

$\underline{<} \prod_{1 \leq i < j \leq r} [27 (μ_{i}^{4} + μ_{j}^{4} + (j - i)^{4})]$

$\underline{<} 2 7^{(_{2}^{r})} \prod_{1 \leq i < j \leq r} (μ_{i}^{4} + μ_{j}^{4} + r^{4})$

$= 27 (_{2}^{r}) \sum r^{4 e_{0}} μ_{1}^{4 e_{1}} ... μ_{r}^{4 e_{r}}$ , (4.16)

where the first inequality follows from

$(a + b + c)^{2} \underline{<} 3 (a^{2} + b^{2} + c^{2})$ .

Here, the sum ranges over some set of exponents $e_{0}$ , $e_{1}$ , $...$ , $e_{r} \in {0, 1, ...,}$ with

$e_{0} + ... + e_{r} =$ . Removing the dependencies among these exponents implied by

the product range only increases this sum. Therefore, from (4.16) follows

$\prod_{1 \leq i < j \leq r} (M_{i} - M_{j} + j - i)^{4} \underline{<} 27 (_{2}^{r}) \sum r^{4 e_{0}} μ_{1}^{4 e_{1}} ċ$ . . $I_{r}^{4 e_{r}}$

$\underline{<} 27 (_{2}^{r}) \times$ $\sum_{e_{0}, ..., e_{r} \geq 0}$ $r^{4 e_{0}} μ_{1}^{4 e_{1}}$ . . . $μ_{r}^{4 e_{r}}$

$e_{0} + ... + e_{r} = (_{2}^{r})$

$\underline{<} (27 r^{4})^{(_{2}^{r})} \times$ $\sum_{e_{1}, ..., e_{r} \geq 0}$ $μ_{1}^{4 e_{1}}$ . . . $μ_{r}^{4 e_{r}}$ .

$e_{1} + ... + e_{r} \leq (_{2}^{r})$

Hence, as the $M_{i}$ (hence the $μ_{i}$ ) are independent,

$E [\prod_{1 \leq i < j \leq r} (M_{i} - M_{j} + j - i)^{4}] = O$

So since the total number of terms in this sum is $(_{r}^{r + (_{2}^{r})})$ , (4.15) will be proved if we

demonstrate that

$E [μ_{1}^{4 e_{1}}]$ . . . $E [μ_{r}^{4 e_{r}}] = O (n^{2 (_{2}^{r})})$ (4.17)

for some fixed one of these $r$ -tuples $(e_{1}$ , . . . , $e_{r})$ . To this end, notice first that $E [μ_{i}^{2}]$

is of order $n$ exactly. Indeed, recall that

$E [M_{i} (M_{i} - 1)] = \frac{n}{2} (\frac{n}{2} - 1)$ $\frac{(\begin{matrix} n - 2 \\ n / 2 - 2 \end{matrix})}{(_{n / 2}^{n})}$

$= \frac{n (n - 2)^{2}}{16 (n - 1)}$ .

Therefore

$E [μ_{i}^{2}] =$ Var $[M_{i}]$

$= E [M_{i} (M_{i} - 1)] + E [M_{i}] - E^{2} [M_{i}]$

$= \frac{n (n - 2)^{2}}{16 (n - 1)} + \frac{n}{4} - \frac{n^{2}}{16}$ (4.18)

$= \frac{n}{16} + O (1)$ .

Furthermore, as a special instance of the hypergeometrically distributed random vari-

able, $M_{i}$ has the same distribution as the sum of $n / 2$ independent Bernoulli variables

$Y_{j} \in {0, 1}$ (see Vatutin and Mikhailov [38], alternatively [31, p. 30]). Therefore,

(4.18) and the Lindeberg-Feller Central Limit Theorem imply

$\frac{μ_{i}}{\sqrt{n / 16}} \to N (0, 1)$ , (4.19)

where $N (0, 1)$ is the standard normal random variable. In fact, since

$\frac{Y_{j} - E [Y_{j}]}{\sqrt{n / 16}} \to 0$ , $n$ $\to \infty$ ,

we can say more. Indeed, we have (4.19) together with convergence of all the moments

(see Billingsley [4, p. 391]). Therefore, in particular

$\frac{E [μ_{i}^{4 e_{i}}]}{(\sqrt{n / 16})^{4 e_{i}}} \to E [N (0, 1)^{4 e_{i}}]$ , $n$ $\to \infty$ ,

$i . e$ .

$E [μ_{1}^{4 e_{1}}]$ . . . $E [μ_{r}^{4 e_{r}}] = O (n^{2 (e_{1} + ... + e_{r})}) = O (n^{2 (_{2}^{r})})$

as $e_{1} + ... + e_{r} \underline{<}$ . This completes the proof of (4.17), and thus of Theorem 1.2.2.

$□$

(JIAPTER 5

SOME PROPERTIES OF THE WEAK ORDERING

We now move away from the Bruhat order to focus on its more restrictive counterpart,

namely the weak ordering. In anticipation of the proof of Theorem 1.4.1, this chapter

is devoted to various properties of this order.

5.1 A Criterion for Weak Comparability

Recall that $π$ precedes a in the weak order $(π \underline{≺} σ)$ if and only if there is a chain

$σ = ω_{1} \to ... \to ω_{s} = π$ where each $ω_{t}$ iiss aa ssiimmppllee reduction of $ω_{t - 1}$ , i.e. obtained by

transposing two adjacent elements $ω_{t - 1} (i)$ , $ω_{t - 1} (i + 1)$ such that $ω_{t - 1} (i) > ω_{t - 1} (i + 1)$ .

Clearly the weak order is more restrictive than the Bruhat order, so that $π \underline{≺} σ$ impies

$π \underline{<} σ$ . In particular, $P (π \underline{≺} σ) \underline{<} P (π \underline{<} σ)$ , hence (Theorem 1.2.1) $P (π \underline{≺} σ) =$

$O (n^{- 2})$ . We will show that, in fact, this probability is exponentially small. The proof

is based on an inversion set criterion for $π \underline{≺} σ$ implicit in [3, pp. 135-139].

Lemma 5.1.1. Given $ω \in S_{n}$ , recall the set of non-inversion s of $ω$ :

$E (ω) : = {(i, j) : i < j, ω^{- 1} (i) < ω^{- 1} (j)}$ .

$π \underline{≺} σ$ if and only if $E (π) \underline{\supset} E (σ)$ .

Proof. Assume $π \underline{≺} σ$ . Then there exists a chain of simple reductions $ω_{t}$ , $1 \underline{<} t \underline{<} s$ ,

connecting a $= ω_{1}$ and $π = ω_{s}$ . By the definition of a simple reduction, for each

$t > 1$ there is $i = i_{t} < n$ such that $E (ω_{t}) = E (ω_{t - 1}) \cup {(ω_{t} (i), ω_{t} (i + 1))}$ , where

$ω_{t} (i) = ω_{t - 1} (i + 1)$ , $ω_{t} (i + 1)$ $= ω_{t - 1} (i)$ , and $ω_{t - 1} (i) > ω_{t - 1} (i + 1)$ . So the set $E (ω_{t})$

increases with $t$ , hence $E (π) \underline{\supset} E (σ)$ .

Conversely, suppose $E (π) \underline{\supset} E (σ)$ . Since a permutation $ω$ is uniquely determined

by its $E (ω)$ , we may assume $E (π) < \supset E (σ)$ .

Claim If $E (π) < \supset E (σ)$ , then there exists $u < v \underline{<} n$ such that $(v, u)$ is an adjacent

inversion of $σ$ , but $(u, v) \in E (π)$ .

Assuming validity of the claim, we ascertain existence of an adjacent inversion $(v, u)$

in a with $(u, v) \in E (π)$ . Interchanging the adjacent elements $u$ and $v$ in a $= ω_{1}$ ,

we obtain a simple reduction $ω_{2}$ , with $E (ω_{1}) \subset E (ω_{2}) \underline{\subset} E (π)$ . If $E (ω_{2}) = E (π)$

then $ω_{2} = π$ , and we stop. Otherwise we determine $ω_{3}$ , a simple reduction of $ω_{2}$ ,

with $E (ω_{2}) \subset E (ω_{3}) \underline{\subset} E (π)$ and so on. Eventually we determine a chain of simple

reductions connecting a and $π$ , which proves that $π \underline{≺} σ$ .

Proof Of CLAIM. The claim is obvious for $n$ $= 1, 2$ . Assume inductively that the

claim holds for permutations of length $n$ $- 1 \underline{>} 2$ . Let $π$ , $σ \in S_{n}$ and $E (π) < \supset E (σ)$ .

As in the proof of Theorem 1.2.1, let $l_{n} (π) = π^{- 1} (n)$ , $l_{n} (σ) = σ^{- 1} (n)$ , and $π^{*}$ , $σ^{*}$ are

obtained by deletion of $n$ from $π$ and $σ$ . Since $E (π) \underline{\supset} E (σ)$ , we have $E (π^{*}) \underline{\supset} E (σ^{*})$ .

Suppose first that $E (π^{*}) = E (σ^{*})$ . Then $π^{*} = σ^{*}$ , and as $E (π) < \supset E (σ)$ , we must

have $l_{n} (π) > l_{n} (σ)$ , i.e. $l_{n} (σ) < n$ . Setting $v = n$ and $u = σ (l_{n} (σ) + 1)$ , we obtain

an adjacent inversion $(v, u)$ in a with $(u, v) \in E (π)$ .

Alternatively, $E (π^{*}) < \supset E (σ^{*})$ . By inductive hypothesis, there exists $u < v \underline{<} n$ $- 1$

such that $(v, u)$ is an adjacent inversion of $σ^{*}$ , but $(u, v) \in E (π^{*})$ . Now insert $n$ back

into $π^{*}$ , $σ^{*}$ , recovering $π$ and $σ$ . If $n$ sits to the right of $u$ or to the left of $v$ in $σ$ , then

$(v, u)$ is still an adjacent inversion of $σ$ . Otherwise $n$ is sandwiched between $v$ on the

left and $u$ on the right. Therefore $(n, u)$ is an adjacent inversion in $σ$ . On the other

hand $(v, n)$ $\in E (σ)$ , so since $E (π) \underline{\supset} E (σ)$ , we have $(v, n)$ $\in E (π)$ also. Hence, the

triple $(u, v, n)$ are in exactly this order (not necessarily adjacent) in $π$ . Therefore the

adjacent inversion $(n, u)$ in a is such that $(u, n)$ $\in E (π)$ , and this proves the inductive

step.

$□$

Denote by $\bar{ω}$ the permutation $ω$ reversed in rank. For example, with $ω =$ 13254 we

have $\bar{ω} =$ 53412. Then it is easy to see that

$E (π) \underline{\supset} E (σ) \Leftrightarrow E (\bar{π}) \underline{\subset} E (\bar{σ})$ .

By Lemma 5.1.1, these statements are equivalent to

$π \underline{≺} σ \Leftrightarrow \bar{σ} \underline{≺} \bar{π}$ .

We immediately obtain the following corollary to Lemma 5.1.1:

Corollary 5.1.2. For $ω \in S_{n}$ , define

$E_{i} (ω) : = {j < i : (j, i) \in E (ω)}$ , $1 \underline{<} i \underline{<} n$ .

Then

$E (ω) = \prod_{i = 1}^{n} {(j, i) : j \in E_{i} (ω)}$ ,

and consequently

$π \underline{≺} σ \Leftrightarrow E (π) \underline{\supset} E (σ) \Leftrightarrow E_{i} (π) \underline{\supset} E_{i} (σ)$ , $\forall i \underline{<} n$ . $□$

5.2 Submultiplicativity of $P_{n}^{*}$

Next, we establish one of the claims of Theorem 1.4.1, namely that $P_{n}^{*} : = P (π \underline{≺} σ)$

is submultiplicative. Of course ([43, p. 23, ex. 98] again) this implies that there

exists $\lim \sqrt[n]{P_{n}^{*}}$ .

Lemma 5.2.1. Let $π$ , $σ \in S_{n}$ be selected independently and uniformly at random. As

a function of n, $P_{n}^{*}$ is submultiplicative, i.e. for all $n_{1}$ , $n_{2} \underline{>} 1$

$P_{n_{1} + n_{2}}^{*} \underline{<} P_{n_{1}}^{*} P_{n_{2}}^{*}$ .

Consequently there exists $\lim_{n \to \infty} \sqrt[n]{P_{n}^{*}} = \inf_{n \geq 1} \sqrt[n]{P_{n}^{*}}$ .

Proof. Let $π$ , a be two permutations of $[n_{1} + n_{2}]$ . Then $π \underline{≺} σ$ if and only if

$E_{i} (π) \underline{\supset} E_{i} (σ)$ , $1 \underline{<} i \underline{<} n_{1} + n_{2}$ .

Using these conditions for $i \underline{<} n_{1}$ , we see that

$π [1, 2, ..., n_{1}] \underline{≺}$ a $[$ 1, 2, $...$ , $n_{1}]$ .

Here $π [1, 2, ..., n_{1}]$ , say, is what is left of the permutation $π$ when the elements

$n_{1} + 1$ , $...$ , $n_{1} + n_{2}$ are deleted.

Likewise , $π \underline{≺} σ$ if and only if

$E_{i} (\bar{π}) \underline{\subset} E_{i} (\bar{σ})$ , $1 \underline{<} i \underline{<} n_{1} + n_{2}$ .

Using these conditions for $i \underline{<} n_{2}$ , we see that

$π [n_{1} + 1, ..., n_{1} + n_{2}] \underline{≺}$ a $[n_{1} + 1, ..., n_{1} + n_{2}]$ .

Now, since $π$ and a are uniformly random and mutually independent, so are the four

permutations

$π [1, ..., n_{1}]$ , $π [n_{1} + 1, ..., n_{1} + n_{2}]$ , $σ [1, ..., n_{1}]$ , a $[n_{1} + 1, ..., n_{1} + n_{2}]$ .

Hence,

$P (π \underline{≺} σ) \underline{<} P$ ( $π [1$ , $...$ , $n_{1}] \underline{≺}$ a[1, $...$ , $n_{1}]$ )

$\times P$ ( $π [n_{1} + 1$ , $...$ , $n_{1} + n_{2}] \underline{≺}$ a $[n_{1} + 1$ , $...$ , $n_{1} + n_{2}]$ ),

so that

$P_{n_{1} + n_{2}}^{*} \underline{<} P_{n_{1}}^{*} P_{n_{2}}^{*}$ . $□$

(JIAPTER 6

THE PROOF OF THE WEAK ORDER UPPER BOUND

We now present the proof of Theorem 1.4.1, upper bound. We will prove something

better than what was stated there, showi $n g$ that for each $ε > 0$ ,

$P_{n}^{*} = O ((β + ε)^{n})$ ,

where

$β = \sqrt[6]{\frac{1065317}{12!}} = 0.36129$ . . .

6.1 A Necessary Condition for Weak Comparability

The proof of this upper bound for $P_{n}^{*}$ parallels the proof of the lower bound for $P_{n}$ in

Theorem 1.2.1. As in that proof, given $k \underline{>} 1$ , let $π^{k *}$ and $σ^{k *}$ be obtained by deletion

of the elements $n$ , $...$ , $n$ $- k + 1$ from $π$ and $σ$ , and let $l_{i} (π) = π^{- 1} (i)$ , $l_{i} (σ) = σ^{- 1} (i)$ ,

$n$ $- k + 1 \underline{<} i \underline{<} n$ . In the notations of the proof of Lemma 5.2.1, $π^{k *} = π [1, ..., n - k]$

and $σ^{k *} = σ [1, ..., n - k]$ , and we saw that $π^{k *} \underline{≺} σ^{k *}$ if $π \underline{≺} σ$ . Our task is to find

the conditions these $l_{i} (ċ)' s$ must satisfy if $π \underline{≺} σ$ holds.

To start, notice that

$π \underline{≺} σ \to | E_{n} (π) | \underline{>} | E_{n} (σ) | \Leftrightarrow l_{n} (π) \underline{>} l_{n} (σ)$ .

$π \underline{≺} σ \to π^{*} \underline{≺} σ^{*} \to l_{n - 1} (π) \underline{>} l_{n - 1} (π^{*}) \underline{>} l_{n - 1} (σ^{*}) \underline{>} l_{n - 1} (σ) - 1$ ,

as deletion of $n$ from $π$ , $σ$ decreases the location of $n$ $- 1$ in each permutation by at

most one. In general, for $0 < j < k$ we get

$π \underline{≺} σ \to π^{j *} \underline{≺} σ^{j *} \to l_{n - j} (π) \underline{>} l_{n - j} (σ) - j$ .

So, introducing $1 (π) = {l_{n - i + 1} (π)}_{1 \leq i \leq k}$ and $1 (σ) = {l_{n - i + 1} (σ)}_{1 \leq i \leq k}$ ,

${π \underline{≺} σ} \underline{\subset} {(l (π), l (σ) \in S_{k}},$ (6.1)

$S_{k} : = {(x, y) \in R^{2 k} : x_{j} \underline{>} y_{j} - j + 1, 1 \underline{<} j \underline{<} k}$ .

In addition, on ${π \underline{≺} σ}$ every pair of elements, which forms an inversion in $π$ , also

forms an inversion in $σ$ . Applying this to the elements $n$ $- k + 1$ , $...$ , $n$ , we have then

${y r \underline{≺} σ} \underline{\subset} {(l (π), l (σ)) \in T_{k}}$ , (6.2)

$T_{k} : =$ { ( $x$ , $y) \in R^{2 k}$ : Vl $\underline{<} i < j \underline{<} k$ , $x_{i} < x_{j} \to y_{i} < y_{j}$ }.

Combining (6.1) and (6.2), we get

${π \underline{≺} σ} \underline{\subset} {(l (π), l (σ)) \in S_{k} \cap T_{k}} \cap {π^{k *} \underline{≺} σ^{k *}}$ .

So, since the two events on the right are independent,

$P_{n}^{*} \underline{<} P ((l (π), l (σ)) \in S_{k} \cap T_{k}) P_{n - k}^{*}$ . (6.3)

6.2 A Reduction to Uniforms

It remains to estimate

$P ((l (π), l (σ)) \in S_{k} \cap T_{k})$ .

As in the proof of Theorem 1.2.1 (lower bound), we observe that $(l (π), l (σ))$ has the

same distribution as $(⌈ n U ⌉, ⌈ n V ⌉)$ , conditioned on

$A_{n, k} \cap B_{n, k} = {⌈ n U_{1} ⌉ \neq ... \neq ⌈ n U_{k} ⌉} \cap {⌈ n V_{1} ⌉ \neq ... \neq ⌈ n V_{k} ⌉}$ .

Here $U_{1}$ , $...$ , $U_{k}$ , $V_{1}$ , $...$ , $V_{k}$ are independent $[0, 1]$ -uniforms. Then

$P ((l (π), l (σ)) \in S_{k} \cap T_{k}) = \frac{P ({(⌈ n U ⌉, ⌈ n V ⌉) \in, S_{k} \cap T_{k}} \cap C_{n, k})}{P (C_{n k})}$ , $C_{n, k} = A_{n, k} \cap B_{n, k}$ .

Introduce the event ${\tilde{D}}_{n, k}$ on which

$\min {\min_{i \neq j} | U_{Reject Reject} - U_{j} |, \min_{i \neq j} | V_{i} - V_{j} |, \min_{i, j} | U_{Reject}, - V_{j} |, k^{- 1} \min_{j} | U_{j} - V_{j} |} > 1 / n$ .

Certainly ${\tilde{D}}_{n, k} \underline{\subset} c_{n, k}$ and, thanks to the factor $1 / k$ by $\min_{j} | U_{j} - V_{j} |$ , on ${\tilde{D}}_{n, k}$

$⌈ n U_{j} ⌉ \underline{>} ⌈ n V_{j} ⌉ - j + 1$ $\to U_{j} \underline{>} V_{j} - k / n \to U_{j} > V_{j}$ .

Therefore on ${\tilde{D}}_{n, k}$ ,

$(⌈ n U ⌉, ⌈ n V ⌉) \in S_{k} \cap T_{k} \to (U, V) \in {\tilde{S}}_{k} \cap T_{k}$ ,

${\tilde{S}}_{k} : = {(x, y) \in R^{2 k} : x_{j} > y_{j}, 1 \underline{<} j \underline{<} k}$ .

Clearly ${\tilde{S}}_{k} \cap T_{k}$ is a cone-shaped subset of $R^{2 k}$ . III addition, $P ({\tilde{D}}_{n, k}^{c}) = O (k^{2} / n)$ .

Hence

$P ((l (π), l (σ)) \in S_{k} \cap T_{k}) \underline{<} \frac{P ((U, V) \in {\tilde{S}}_{k} \cap T_{k}) + O (P ({\tilde{D}}_{n, k}^{c}))}{1 - O (P ({\tilde{D}}_{n, k}^{c}))}$

$= Q_{k}^{*} (1 + O (k^{2} / n))$ , $Q_{k}^{*} : = P ((U, V) \in {\tilde{S}}_{k} \cap T_{k})$ .

This and (6.3) imply

$P_{n}^{*} \underline{<} Q_{k}^{*} P_{n - k}^{*} \exp (O (k^{2} / n))$ .

Hence, as in the proof of Theorem 1.2.1 (lower bound),

$\lim \sup \sqrt[n]{P_{n}^{*}} \underline{<} \sqrt[k]{Q_{k}^{*}}$ , $\forall k \underline{>} 1$ ,

and so

$P_{n}^{*} = O ((\sqrt[k]{Q_{k}^{*}} + ε)^{n})$ , $k \underline{>} 1$ , $ε > 0$ . (6.4)

Furthermore from the definition of $Q_{k}^{*}$ , it follows directly that $Q_{k}^{*}$ is submultiplicative,

$i . e$ .

$Q_{k_{1} + k_{2}}^{*} \underline{<} Q_{k_{1}}^{*} Q_{k_{2}}^{*}$ , $k_{1}$ , $k_{2} \underline{>} 1$ .

Therefore ([43, p. 23, ex. 98] again)

$\lim$ ${\sqrt{Q_{k}^{*}}}^{k} = \inf {\sqrt{Q_{k}^{*}}}^{k}$ .

$k \to \infty$ $k \geq 1$

So the further we can push tabulation of $Q_{k}^{*}$ , the better our exponential upper bound

for $P_{n}^{*}$ would probably be. ( $" P r o b a b l y "$ , because we do not have a proof that $\sqrt[k]{Q_{k}^{*}}$

decreases with $k .$ )

6.3 An Algorithm to Minimize the Bound

As in the case of $Q_{k}$ , $Q_{k}^{*} = N_{k}^{*} / (2 k)!$ . Here, by the definition of the sets ${\tilde{S}}_{k}$ and $T_{k}$ ,

$N_{k}^{*}$ is the total number of ways to order $x_{1}$ , $...$ , $x_{k}$ , $y_{1}$ , $...$ , $y_{k}$ so that two conditions

are met: (1) for each $j$ , $x_{j}$ is to the right of $y_{j}$ ; (2) for all $i < j$ , if $x_{i}$ is to the left of

$x_{j}$ then $y_{i}$ is to the left of $y_{j}$ .

It is instructive first to evaluate $N_{k}^{*}$ by hand for $k = 1, 2$ . $N_{1}^{*} = 1$ as there is only

one sequence, $y_{1} x_{1}$ , meeting the conditions (1), (2). Passing to $N_{2}^{*}$ , we must decide

how to insert $y_{2}$ and $x_{2}$ into the sequence $y_{1} x_{1}$ in compliance with conditions (1),

(2). First of all, $y_{2}$ has to precede $x_{2}$ . If we insert $x_{2}$ at the beginning of $y_{1} x_{1}$ , giving

$x_{2} y_{1} x_{1}$ , then we can only insert $y_{2}$ at the beginning of this triple, giving

$y_{2} x_{2} y_{1} x_{1}$ .

Alternatively, inserting $x_{2}$ in the middle of $y_{1} x_{1}$ , we have 2 possibilities for insertion

of $y_{2}$ , and we get two admissible orderings,

$y_{2} y_{1} x_{2} x_{1}$ , $y_{1} y_{2} x_{2} x_{1}$ .

Finally, insertion of $x_{2}$ at the end of $y_{1} x_{1}$ brings the condition (2) into play as we now

have $x_{1}$ preceding $x_{2}$ , and so $y_{1}$ must precede $y_{2}$ . Consequently, we get two admissible

orderings,

$y_{1} y_{2} x_{1} x_{2}$ , $y_{1} x_{1} y_{2} x_{2}$ .

Hence $N_{2}^{*} = 1$ $+ 2 + 2 = 5$ . Easy so far! However, passing to $k = 3$ is considerably

more time-consuming than it was for computation of $N_{3}$ in the proof of the lower

bound in Theorem 1.2.1. There, once we had determined the $N_{2}$ admissible order-

ings, we could afford not to keep track of relative orderings of $x_{1}$ , $...$ , $x_{k - 1}$ , and of

$y_{1}$ , $...$ , $y_{k - 1}$ , whence the coding by Fs and $O' s$ . All we needed for passing from $k - 1$

to $k$ was the list of all binary ballot-sequences of length 2 $(k - 1)$ together with their

multiplicities. Here the nature of the conditions (1), (2) does not allow lumping vari-

ous sequences together, and we have to preserve the information of relative orderings

of $x' s$ , and relative orderi $n g s$ of $y' s$ . This substantial complication seriously inhibits

the computer's ability to compute $N_{k}^{*}$ for $k$ as large as in the case of $N_{k}$ .

To get a feeling for how sharply the amount of computation increases for $k = 3$ , let

us consider one of the $N_{2}^{*} = 5$ admissible sequences, namely $y_{2} x_{2} y_{1} x_{1}$ . As above, we

write down all possible ways to insert $y_{3}$ and $x_{3}$ into this sequence so that (1) and

(2) hold. Doing this, we produce the 10 sequences:

$y_{3} x_{3} y_{2} x_{2} y_{1} x_{1}$ , $y_{3} y_{2} x_{3} x_{2} y_{1} x_{1}$ ,

$y_{2} y_{3} x_{3} x_{2} y_{1} x_{1}$ , $y_{2} y_{3} x_{2} x_{3} y_{1} x_{1}$ ,

$y_{2} x_{2} y_{3} x_{3} y_{1} x_{1}$ , $y_{2} y_{3} x_{2} y_{1} x_{3} x_{1}$ ,

$y_{2} x_{2} y_{3} y_{1} x_{3} x_{1}$ , $y_{2} x_{2} y_{1} y_{3} x_{3} x_{1}$ ,

$y_{2} x_{2} y_{1} y_{3} x_{1} x_{3}$ , $y_{2} x_{2} y_{1} x_{1} y_{3} x_{3}$ .

We treat similarly the other four sequences from the $k = 2$ case, eventually arriving

at $N_{3}^{*} = 55$ . We wouldn't even think of computing $N_{4}^{*}$ by hand.

Once again the computer programming to the rescue! Table 6.1 was produced by the

computer after a substantial running time.

Using (6.4) with the value $k = 6$ from this table, we get for each $ε > 0$

$P_{n}^{*} = ((\sqrt[6]{Q_{6}^{*}} + ε)^{n}) = ((0.361 ... + ε)^{n})$ . $□$

Table 6.1: Exact computation of $N_{k}^{*}$ for smallish $k$ .

(JIAPTER 7

THE PROOF OF THE WEAK ORDER LOWER BOUND

We now prove the lower bound stated in Theorem 1.4.1. Despite its sharp qualitative

contrast to the upper bound in this same theorem, its proof requires a much deeper

combinatorial insight. In particular, we will get as a consequence a lower bound

(which is known [46, p. 312, ex. 1]) for the number of linear extensions of an

arbitrary poset $P$ of cardinality $n$ .

7.1 A Formula for P $(E_{i} (π) \underline{\supset} E_{i} (σ))$

To bound $P (π \underline{≺} σ)$ from below we will use the criterion (Corollary 5.1.2)

$π \underline{≺} σ \Leftrightarrow E_{i} (π) \underline{\supset} E_{i} (σ)$ , $\forall i \underline{<} n$ .

First of all,

Lemma 7.1.1. Let i $\in [n]$ , $B \underline{\subset} [i - 1]$ ( $[0] = \emptyset)$ . If $π \in S_{n}$ is chosen uniformly at

random, then

$P (E_{i} (π) \underline{\supset} B) = \frac{1}{| B | + 1}$ .

Proof. By the definition of $E_{i} (π)$ ,

${E_{i} (π) \underline{\supset} B} = {π^{- 1} (j) < π^{- 1} (i), \forall j \in B}$ .

It remains to observe that $π^{- 1}$ is also uniformly random. $□$

Lemma 7.1.1 implies the following key statement:

Lemma 7.1.2. Let $π$ , $σ \in S_{n}$ be selected independently and uniformly at random.

Then, for i $\in [n]$ ,

$P (E_{i} (π) \underline{\supset} E_{i} (σ)) = H (i) / i$ , $H (i) : = \sum_{j = 1}^{i} \frac{1}{j}$ .

Proof. By Lemma 7.1.1,

$P (E_{i} (π) \underline{\supset} E_{i} (σ)) = \sum_{B \subseteq [i - 1]} P (E_{i} (π) \underline{\supset} B) P (E_{i} (σ) = B)$

$= \sum_{B \subseteq [i - 1]} \frac{P (E_{i} (σ) = B)}{| B | + 1}$

$= E [\frac{1}{| E_{i} (σ) | + 1}]$

$= \sum_{j = 0}^{i - 1} \frac{1}{i (j + 1)} = \frac{H (i)}{i}$ . $□$

Note. In the second to last equality, we have used the fact that $| E_{i} (σ) |$ is distributed

uniformly on ${0, 1, ..., i - 1}$ . In addition, $| E_{1} (σ) |, ...$ , $| E_{n} (σ) |$ are independent, a

property we will use later. For completeness, here is a bijective proof of these facts.

By induction, the numbers $| E_{i} (σ) |$ , $i \underline{<} t$ , determine uniquely the relative ordering of

elements 1, . . . ' $t$ in the permutation $σ$ . Hence the numbers $| E_{i} (σ) |$ , $i \in [n]$ , determine

a uniquely. Since the range of $| E_{i} (σ) |$ is the set ${0, ..., i - 1}$ of cardinality $i$ , and

$| S_{n} | = n$ !, it follows that the numbers $| E_{i} (σ) |$ , $i \in [n]$ , are uniformly distributed, and

independent of each other.

7.2 Positive Correlation of the Events ${E_{i} (π) \underline{\supset} E_{i} (σ)}$

Needless to say we are interested in $P (π \underline{≺} σ) = P (\cap_{i = 1}^{n} {E_{i} (π) \underline{\supset} E_{i} (σ)})$ . For-

tunately, the events ${E_{i} (π) \underline{\supset} E_{i} (σ)}$ turn out to be positively correlated, and the

product of the marginals $P (E_{i} (π) \underline{\supset} E_{i} (σ))$ bounds that probability from below.

Theorem 7.2.1. Let $π$ , $σ \in S_{n}$ be selected independently and uniformly at random.

Then

$P (π \underline{≺} σ) \underline{>} \prod_{i = 1}^{n} P (E_{i} (π) \underline{\supset} E_{i} (σ)) = I I$ $\frac{H (i)}{i}$ .

Proof. First notice that conditioning on a and using the independence of $π$ and $σ$ ,

$P (E_{i} (π) \underline{\supset} E_{i} (σ), \forall i \underline{<} n)$

$= E$ $[P (E_{i} (π) \underline{\supset} E_{i} (σ), \forall i \underline{<} n | σ)]$

$= E [P (E_{i} (π) \underline{\supset} B_{i}, \forall i \underline{<} n) |_{B_{i} = E_{i} (σ)}]$ .

So our task is to bound $P (E_{i} (π) \underline{\supset} B_{i}, \forall i \underline{<} n)$ , where these $B_{i}' s$ inherit the following

property from the $E_{i} (σ)' s$ :

$i \in E_{j} (σ)$ and $j \in E_{k} (σ) \to i \in E_{k} (σ)$ .

Lemma 7.2.2. Let $n \underline{>} 1$ be an integer, and let $B_{i} \underline{\subset} [n]$ , i $= 1$ , ..., n, be such that

$i \notin B_{i}$ and $i \in B_{j}$ , $j \in B_{k} \to i \in B_{k}$ , $\forall i$ , $j$ , $k \in [n]$ .

Then, for $π \in S_{n}$ selected uniformly at random,

$P (E_{i} (π) \underline{\supset} B_{i}, \forall i \underline{<} n) \underline{>} \prod_{i = 1}^{n} \frac{1}{| B_{i} | + 1}$ .

Proof Of LEIVIIVIA 7.2.2. Notice upfront that $\cup_{i} B_{i} \neq [n]$ . Otherwise there would

exist $i_{1}$ , $...$ , $i_{s}$ such that $i_{t} \in B_{i_{t + 1}}, 1 \underline{<} t \underline{<} s$ , $(i_{s + 1} = i_{1})$ , and - using repeatedly

the property of the sets $B_{i}$ - we would get that, say, $i_{1} \in B_{i_{2}}$ and $i_{2} \in B_{i_{1}}$ , hence

$i_{2} \in B_{i_{2}}$ ; contradiction.

Let $U_{1}$ , $...$ , $U_{n}$ be independent uniform- $[0, 1]$ random variables. Let a random permu-

tation $ω$ be defined by

$ω (i) = k \Leftrightarrow U_{i}$ is $k^{t h}$ smallest amongst $U_{1}$ , $...$ , $U_{n}$ .

Clearly $ω$ is distributed uniformly, and then so is $π : = ω^{- 1}$ With $π$ so defined, we

obtain

${E_{i} (π) \underline{\supset} B_{i}, \forall i \underline{<} n}$ $= {π^{- 1} (i) > π^{- 1} (j), \forall j \in B_{i}, i \underline{<} n}$

$= {U_{i} > U_{j}, \forall j \in B_{i}, i \underline{<} n}$ .

Hence, the probability in question equals

$P (U_{i} > U_{j}, \forall j \in B_{i}, i \underline{<} n)$ .

We write this probability as the $n$ -dimensional integral

$P (U_{i} > U_{j}, \forall j \in B_{i}, i \underline{<} n)$ $= \int ... \int d x_{1} ... d x_{n} D$ ,

$D =$ ${(x_{1}, ..., x_{n}) \in [0, 1]^{n} : x_{i} > x_{j}, \forall j \in B_{i}, i \underline{<} n}$ .

Since $\cup_{i} B_{i} \neq [n]$ , we can choose an index $k \in [n]$ such that $k \notin B_{i}$ for all $i$ . Then we

may rewrite the integral above as

$\int_{0}^{1}$ ( $\int_{D (x_{k})} ... \int d x_{1} ... d x_{k - 1} d x_{k + 1}$ $... d x_{n}$ ) $d x_{k}$ ,

$D (x_{k}) = {(x_{1}, ..., x_{k - 1}, x_{k + 1}, ..., x_{n}) \in [0, 1]^{n - 1} : x_{i} > x_{j}, \forall j \in B_{i}, i \underline{<} n}$ .

On $D (x_{k})$ , the only inequalities involving $x_{k}$ are of the form $x_{k} > x_{j}$ , $j \in B_{k}$ . This

suggests scaling those $x_{j}$ by $x_{k}$ , i.e. introducing new variables $t_{j} : = x_{j} / x_{k}$ , so that

$t_{j} \in [0, 1]$ , $j \in B_{k}$ . To keep notation uniform, let us also replace the remaining $x_{i}$ ,

$i \notin B_{k} \cup {k}$ , with $t_{i}$ . Let $D$ $(x_{k})$ denote the integration region for the new variables

$t_{i}$ , $i \neq k$ . Explicitly, the constraints $x_{j} < x_{k}$ , $j \in B_{k}$ , become $t_{j} < 1$ , $j \in B_{k}$ .

Obviously each listed constraint $x_{a} < x_{b} (a, b \in B_{k})$ is replaced, upon scaling, with

$t_{a} < t_{b}$ . We only rename the other variables, so every constraint $x_{a} < x_{b} (a, b \notin B_{k})$

similarly becomes $t_{a} < t_{b}$ . By the property of the sets $B_{i}$ , there are no inequalities

$x_{a} > x_{b}$ , $a \in B_{k}$ , $b \notin B_{k}$ (since the presence of this inequality implies $b \in B_{a}$ ). The

only remaining inequalities are all of the type $x_{a} < x_{b}$ , $a \in B_{k}$ , $b \notin B_{k}$ . In the new

variables, such a constraint becomes $x_{k} t_{a} < t_{b}$ , and it is certainly satified if $t_{a} < t_{b}$ ,

as $x_{k} \underline{<} 1$ . Hence, $D$ $(x_{k}) \underline{\supset} D^{*}$ , where

$D^{*} : =$ ${(t_{1}, ..., t_{k - 1}, t_{k + 1}, ..., t_{n}) \in [0, 1]^{n - 1} : t_{i} > t_{j}, \forall j \in B_{i}, i \neq k}$ ,

and $D^{*}$ does not depend on $x_{k}$ ! Observing that the constraints that determine $D^{*}$

are those for $D$ with the constraints $x_{i} < x_{k}$ , $i \in B_{k}$ , removed, we conclude that the

innermost integral over $D (x_{k})$ is bounded below by

$x_{k}^{| B_{k} |} P (U_{i} > U_{j}, \forall j \in B_{i}, i \neq k)$ .

( $x_{k}^{| B_{k} |}$ is the Jacobian of the linear transformation ${x_{i}}_{i \neq k} \to {t_{i}}_{i \neq k} .$ ) Integrating

with respect to $x_{k}$ , we arrive at

$P (U_{i} > U_{j}, \forall j \in B_{i}, i \underline{<} n) \underline{>} \frac{1}{| B_{k} | + 1} ċ P (U_{i} > U_{j}, \forall j \in B_{i}, i \neq k)$ . (7.1)

By induction on the number of sets $B_{i}$ , with Lemma 7.1.1 providing basis of induction

and (7.1) - the inductive step, we get

$P (U_{i} > U_{j}, \forall j \in B_{i}, i \underline{<} n) \underline{>} \prod_{i = 1}^{n} \frac{1}{| B_{i} | + 1}$ . $□$

The rest is short. First, by Lemma 7.2.2,

$P (E_{i} (π) \underline{\supset} E_{i} (σ), \forall i \underline{<} n)$ $= E [P (E_{i} (π) \underline{\supset} B_{i}, \forall i \underline{<} n)$ $|_{B_{i} = E_{i} (σ)}]$

$\underline{>} E [\prod_{i = 1}^{n} \frac{1}{| E_{i} (σ) | + 1}]$

Since the cardinalities $| E_{i} (σ) |$ are independent, the last expected value equals

$\prod_{i = 1}^{n} E [\frac{1}{| E_{i} (σ) | + 1}] = \prod_{i = 1}^{n} (\frac{1}{i} \sum_{j = 0}^{i - 1} \frac{1}{j + 1}) = \prod_{i = 1}^{n} \frac{H (i)}{i}$ ;

for the second to last equality see the proof of Lemma 7.1.2.

7.3 Linear Extensions of Arbitrary Finite Posets

Note. Let $P$ be a poset on $[n]$ , and put $B_{i} : =$ { $j \in P$ : $j < i$ in $P$ } . $B_{i} \cup {i}$ is

called the order ideal at $i$ . By the properties of $P$ , the $B_{i}' s$ satisfy the hypotheses of

Lemma 7.2.2, so letting $e (P)$ denote the number of linear extensions of $P$ we get

$P (E_{i} (π) \underline{\supset} B_{i}, \forall i \underline{<} n)$ $= . \frac{| {ω . ω (i) > ω (j), \forall j \in B_{i}, i \underline{<} n} |}{n!}$

$= \frac{e (P)}{n!} \underline{>} \prod_{i = 1}^{n} \frac{1}{| B_{i} | + 1}$ .

Thus we have proved

Corollary 7.3.1. For a poset P with n elements,

$e (P) \underline{>} n! / \prod_{i = 1}^{n} d (i)$ , $d (i) : = |$ { $j \in P$ : $j \underline{<} i$ in $P$ } $|$ . $□$

In a very special case of $P$ , whose Hasse diagram is a forest of rooted trees with edges

directed away from the roots, this simple bound is actually the value of $e (P)$ $([46,$ $p$ .

312, ex. 1], [34, sect. 5.1.4, ex. 20], [8] $)$ . There exist better bounds for the number

of linear extensions in the case of the Boolean lattice (see Brightwell and Tetali [14],

Kleitman and Sha [33] $)$ , but nothing has been done in the way of improving this

bound for $P$ $= P (σ)$ , the permutation-induced poset. Indeed, our proof of the lower

bound for $P_{n}^{*}$ used only the universal bound of Corollary 7.3.1, and not one specific

to this special poset. So this begs the question of whether we might improve the

bound in this case, and consequently improve on our lower estimate for $P_{n}^{*}$ . We are

presently working in this direction.

(JIAPTER 8

NUMERICS

We now present some numerical results we have generated in hopes of determining

how close our present bounds are to being sharp. These computer simulations were

only done for comparability of permutation-pairs.

8.1 Bruhat Order Numerics

From computer-generated data we have collected, it appears that our $O (n^{- 2})$ upper

bound given in Theorem 1.2.1 correctly predicts the qualitative behavior of $P (π \underline{<} σ)$ .

The data suggests that $P (π \underline{<} σ)$ is of exact order $n^{- (2 + δ)}$ for some $δ \in [0.5, 1]$ ,

which begs the question of how to improve on our current bound. Writing $P_{n} =$

$P (π \underline{<} σ)$ , Figure 8.1 is a graph (based on this numerical experimentation) exhibiting

convergence to the exponent $- a$ in the asymptotic equation $P_{n} \sim c n^{- a}$ , $c > 0$ a

constant, and $- a$ appears to be near -2.5. In table 8.1, we also provide a portion of

the accompanying data used to generate this graph.

In this table, $R_{n}$ represents the number of pairs $(π, σ)$ out of 10 randomly-generated

pairs such that we had $π \underline{<} σ$ . We have also utilized the computer to find the actual

probability $P_{n}$ for $n$ $= 1$ , 2, $...$ , 9. Table 8.2 lists these true proportions.

Table 8.1: Computer simulation data for $P_{n}$ .

Table 8.2: Exact computation of $P_{n}$ for smallish $n$ .

Value of $n$

-1

$. \dot{0} " e \in \circ \circ \hat{s} - 1.5$

$. - \dot{\infty D} ∖ \underline{⋁ -}$

$\bar{0 . e \frac{o}{.}} \hat{⋁ t^{s} -}$

$z \supset \in \circ -$ -2

-2.5

Figure 8.1: Experimental determination of the exponent $- a$ in the asymptotic equa-

tion $P_{n} \sim c n^{- a}$ .

8.2 Weak Order Numerics

Concerning the weak order, computer-generated data suggests that $P (π \underline{≺} σ)$ is of

exact order $(0.3)^{n}$ . So our current upper bound $O ((0.362)^{n})$ is a qualitative match

for $P (π \underline{≺} σ)$ , but it appears that improvements are possible here also. Writing $P_{n}^{*} =$

$P (π \underline{≺} σ)$ , Figure 8.2 is a graph (based on our numerical experiments) exhibiting

convergence to the ratio $ρ$ in the asymptotic equation $P_{n}^{*} \sim c ρ^{n}$ , $c > 0$ a constant, and

$ρ$ appears to be near 0.3. In table 8.3 we also provide a portion of the accompanying

data used to generate this graph.

Value of $n$

1.1

0.9

$\underline{" . \circ \dot{s^{e} 0^{D} \dot{\infty}}} ⋆ - | 0.7$

$\frac{D}{o e, 0} ., \overset{`}{⋆} t^{s} t^{s}$

$\bar{\dot{z \supset \in \circ}}$ 0.5

0.3

Figure 8.2: Experimental determination of the ratio $ρ$ in the asymptotic equation

$P_{n}^{*} \sim c ρ^{n}$ .

In this table, 77; is defined analogously to $R_{n}$ above. Table 8.4 lists the true propor-

tions $P$ : for $n$ $= 1$ , 2, $...$ , 9.

Surprisingly, our Theorem 1.4.1 lower bound for $P_{n}^{*}$ is quite good for these smallish

values of $n$ , as is seen in table 8.5.

Table 8.3: Computer simulation data for $P_{n}^{*}$ .

Table 8.4: Exact computation of $P_{n}^{*}$ for smallish $n$ .

Table 8.5: Our theoretical lower bound for $P_{n}^{*}$ applied for smallish $n$ .

(JIAPTER 9

ON INFS AND SUPS IN THE WEAK ORDER LATTICE

Finally, we focus on the proof of Theorem 1.4.2. Before we prove what was stated

there, we have a good deal in the way of preliminaries to take care of. The discussion

below is inspired almost exclusively by material contained in the work [3].

9.1 A Connection with Complete, Directed, Acyclic Graphs

Given $ω \in S_{n}$ , recall the set of non-inversions of $ω$ ,

$E (ω) : = {(i, j) : i < j, ω^{- 1} (i) < ω^{- 1} (j)}$ ,

and the set of inversions of $ω$ ,

$E^{*} (ω) : = {(i, j) : i > j, ω^{- 1} (i) < ω^{- 1} (j)}$ .

Note that $ω$ is uniquely determined by its $E (ω)$ (equivalently, by its $E^{*} (ω)$ ). We have

seen that, given permutations $π$ , $σ \in S_{n}$ , we have $π \underline{<} σ$ in the weak order (written

$π \underline{≺} σ)$ if and only if $E (π) \underline{\supset} E (σ)$ (equivalently $E^{*} (π) \underline{\subset} E^{*} (σ)$ ). It is beneficial to

consider the sets $E (ω)$ and $E^{*} (ω)$ as directed edges in a complete, simple, labelled

digraph. Namely, we define

$G (ω) =$ ( $[n]$ , $E (ω)$ I $E^{*} (ω)$ )

by joining $i$ and $j$ with an arc directed from $i$ to $j$ if $(i, j) \in E (ω) ((i, j) \in E^{*} (ω)$

resp.). Note that $G (ω)$ is acyclic, where we are considering paths (hence cycles) in

the sense of directed graphs, always moving in the direction specified by arcs.

Now consider an arbitrary complete, simple, labelled digraph $G =$ ( $[n],$ EU $E^{*}$ ), where

$E : = {(i, j) : i < j}$ ,

$E^{*} : = {(i, j) : i > j}$ .

Given a subset $A \underline{\subset} E \cup$ $E^{*}$ of edges, we define the transitive closure $\bar{A}$ of $A$ in $G$ to

be the set of ordered pairs $(i, j)$ of vertices which are joined by a path consisting of

$A$ -edges in $G$ directed from $i$ to $j$ . The transitive part of this closure $\bar{A}$ is defined to

$T (A) : = \bar{A} ∖ A$

so that

$\bar{A} = A \cup$ $T (A)$ .

In particular, $E$ and $E^{*}$ are subsets of edges of $G$ so we may consider their transitive

closure in $G$ . Note that $E$ and $E^{*}$ (equivalently $G$ ) coming from a permutation will

be unchanged by this transitive closure operation, i.e. in this case we would have

$T (E) = \emptyset = T (E^{*})$ . The following is a trivial, but important, observation about

taking transitive closures:

Lemma 9.1.1. Given a subset $A$ of edges of $G$ , we have $\bar{\bar{A}} = A$ . Equivalently,

$T (\bar{A}) = \emptyset$ .

Proof. Evidently $\bar{\bar{A}} \underline{\supset}$ A. For the opposite containment, let $(i, j) \in \bar{\bar{A}}$ . This means

there is a path $P$ consisting of edges $e_{1}$ , $...$ , $e_{k} \in \bar{A}$ directed from $i$ to $j$ (if $k = 1$ , this

means $(i, j) = e_{1} \in \bar{A})$ . Here, we have indexed the edges $e_{1}$ , . . . , $e_{k}$ in the order they

appear in $P$ . Namely, $e_{1}$ has initial vertex $i$ and terminal vertex equal to the initial

vertex of $e_{2}$ , and so on. Of course, $e_{k}$ has terminal vertex $j$ .

Note that each $e_{i}$ is either an original edge of $A$ , or else comes from a directed path

$P_{i}$ consisting of edges from $A$ directed from the initial end to the terminal end of $e_{i}$ .

Hence, we can construct from $P$ a path $P^{'}$ consisting only of $A$ -edges in the following

way: if $e_{i} \in A$ , keep it; otherwise, replace $e_{i}$ with the directed path $P_{i}$ . Then $P^{'}$ is a

directed path of $A$ -edges from $i$ to $j$ , so $(i, j) \in A$ .

$□$

In other words, Lemma 9.1.1 says that taking the transitive closure of a set of edges

produces a set of edges which is transitively closed. We are ready to give some

equivalent criteria which guarantee that $G$ is induced by a permutation:

Lemma 9.1.2. The following are equivalent:

(i) $G = G (ω)$ for some unique permutation $ω \in S_{n}$ .

(ii) $G$ is acyclic.

(iii) $E = \bar{E}$ and $E^{*} = \bar{E^{*}} (e q u i v a l e n t l y T (E) = \emptyset = T (E^{*}))$ .

Proof. $(i) \to (i i)$ . This is obvious, as all edges of $G (ω)$ are directed from $ω (i)$ to $ω (j)$

for each $1 \underline{<} i < j \underline{<} n$ .

$(i i) \to (i)$ . Suppose $G$ is acyclic. We claim that there exists a unique vertex $v_{1} \in [n]$

such that all edges incident there are inwardly-directed. Indeed, if there were no such

vertex then we could enter and leave every vertex, eventually constructing a cycle as

$G$ is finite; contradiction. We get uniqueness of $v_{1}$ since, for any other vertex $v \neq v_{1}$ ,

$G$ complete implies there is an edge directed from $v$ to $v_{1} (v_{1}$ has all inwardly-directed

incident edges) so that $v$ has an outwardly-directed incident edge.

Define $ω (n) = v_{1}$ , and delete $v_{1}$ from $G$ , giving a new labelled, complete, simple

digraph $G - {v_{1}}$ with vertex set $[n] ∖ {v_{1}}$ . Of course $G - {v_{1}}$ is still acyclic, so we may

repeat the above argument on this new digraph, giving a unique vertex $v_{2} \in [n] ∖ {v_{1}}$

such that all edges incident there are inwardly-directed. We put $ω (n - 1)$ $= v_{2}$ and

continue in this way, finally arriving at a unique permutation $ω \in S_{n}$ such that

$G = G (ω)$ .

(ii) $\to (i i i)$ . Suppose, say, $E \neq E$ . Then there exists $(i, j) \in \bar{E} ∖ E$ . Hence, we can find

edges $e_{1}$ , $...$ , $e_{k} \in E$ , $k > 1$ , that form a directed path from $i$ to $j$ in $G$ (i.e., the

terminal end of $e_{t}$ is the initial end of $e_{t + 1}$ for each $1 \underline{<} t \underline{<} k -$ $1$ ). Since $(i, j) \notin E$

and $G$ is complete, we have $(j, i) \in E^{*}$ Therefore $C : = (e_{1}, ..., e_{k}, (j, i))$ forms a

cycle in $G$ . By a similar argument we can show that $E^{*} \neq \bar{E^{*}}$ implies $G$ contains a

cycle.

(iii) $\to (i i)$ . Suppose $G$ contains a cycle. Since $G$ is both antisymmetric and complete,

it contains a cycle of length 3. Let $a$ , $b$ and $c$ be the distinct vertices in $[n]$ that form

this cycle. $Re$ -labelling if necessary, we may assume $a < b < c$ . If the cycle is $(a, b, c)$ ,

then

$(a, b)$ , $(b, c) \in E$ ; $(c, a) \in E^{*}$

so that $(a, c) \in \bar{E} ∖ E$ , i.e., $E \neq E$ . On the other hand, if $(a, c, b)$ is the cycle, then

$(a, c) \in E$ ; $(c, b)$ , $(b, a) \in E^{*}$

so that $(c, a) \in \bar{E^{*}} ∖ E^{*}$ , i.e., $E^{*} \neq \bar{E^{*}}$ . This completes the proof of Lemma 9.1.2.

$□$

9.2 Computing Infs and Sups in the Weak Order Lattice

With this machinery, we now show that the poset $(S_{n}, \underline{≺})$ is a lattice. What's more,

we can say precisely how to compute $\inf {π_{1}$ , . . . ' $π_{r}}$ ( $\sup {π_{1}$ , . . . ' $π_{r}}$ resp.), where

$π_{1}$ , $...$ , $π_{r} \in S_{n}$ .

Lemma 9.2.1. $(S_{n}, \underline{≺})$ is a lattice with

$E (\inf {π_{1}, ..., π_{r}}) = \cup_{i = 1}^{r} E (π_{i})$

and

$E^{*}$ $(\sup {π_{1}, ..., π_{r}}) = \cup_{i = 1}^{r} E^{*} (π_{i})$ .

Proof. We will prove this only for infimums; the proof for supremums is completely

analogous. By Lemma 9.1.2 it is sufficient to prove that the complete, simple, labelled

digraph $G = ([n], E U E^{*})$ , where $E = \cup_{i = 1}^{r} E (π_{i})$ , contains no cycle.

Suppose $G$ does contain a cycle. Then, since $G$ is both antisymmetric and complete,

it contains a cycle of length 3, passing through the vertices $a$ , $b$ and $c$ , say. We may

assume $a < b < c$ ; otherwise just $r e$ -label the vertices. If the cycle is $(a, b, c)$ , then

$(a, b)$ , $(b, c) \in E$ ; $(c, a) \in E^{*}$ ,

which violates the transitivity of $E$ (note that $E$ is transitively closed by Lemma

9.1.1). So this is impossible.

On the other hand, suppose the cycle is $(a, c, b)$ . Then

$(a, c) \in E$ ; $(c, b)$ , $(b, a) \in E^{*}$

Therefore $(a, b)$ , $(b, c) \notin \cup_{i = 1}^{r} E (π_{i})$ , and hence

$(c, b)$ , $(b, a) \in \cap_{i = 1}^{r} E^{*} (π_{i})$ .

From transitivity, $(c, a) \in \cap_{i = 1}^{r} E^{*} (π_{i})$ , and therefore

$(a, c) \notin \cup_{i = 1}^{r} E (π_{i})$ .

So, as $(a, c) \in E$ , there exist indices $i_{1}$ , $...$ , $i_{k}$ and vertices $a = x_{1}$ , $x_{2}$ , $...$ , $x_{k}$ , $x_{k + 1} = c$

with $x_{j} < x_{j + 1}$ , $x_{j} \neq b$ and

$(x_{j}, x_{j + 1}) \in E (π_{i_{j}})$ , $\forall j \underline{<} k$ .

Let $1 \underline{<} p \underline{<} k$ be the index such that $x_{ℓ} < b < x_{ℓ + 1}$ . If it happens that $(b, x_{ℓ}) \in$

$E^{*} (π_{i ℓ})$ , then as $(x_{ℓ}, x_{ℓ + 1}) \in E (π_{i ℓ})$ we must have $(b, x_{ℓ + 1})$ $\in E (π_{i ℓ})$ by transitivity

of the permutation $π_{i ℓ}$ . Hence $(b, x_{ℓ + 1}) \in E$ , and since $(x_{ℓ + 1}, x_{ℓ + 2}) \in E$ we get

$(b, x_{ℓ + 2}) \in E$ by transitivity of $E$ . Using repeatedly the transitivity of $E$ in this way,

we eventually obtain $(b, c) \in E$ , contradicting $(c, b) \in E^{*}$

Hence, it must be that $(x_{ℓ}, b) \in E (π_{i ℓ})$ . So $(x_{ℓ}, b) \in E$ , and by the transitivity of $E$ we

have $(a, x_{ℓ}) \in E$ . Therefore, using transitivity once more, $(a, b) \in E$ , contradicting

$(b, a) \in E^{*}$ Therefore $G$ must be acyclic, and hence (Lemma 9.1.2) $G = G (π)$ for

some unique permutation $π \in S_{n}$ . Finally, any permutation $ω \in S_{n}$ that is a lower

bound for all of $π_{1}$ , $...$ , $π_{r}$ will have

$E (ω) \underline{\supset} \cup_{i = 1}^{r} E (π_{i})$

by definition of the weak order. Hence, since $E (ω)$ is transitively closed, we have

$E (ω) \underline{\supset} E$ . We have just shown $E = E (π)$ , and hence

$E (ω) \underline{\supset} E (π) \underline{\supset} \cup_{i = 1}^{r} E (π_{i})$

so that $ω \underline{≺} π \underline{≺} π_{i}$ , $1 \underline{<} i \underline{<} r$ . That is, $π = \inf {π_{1}$ , . . . ' $π_{r}}$ and we are done. $□$

9.3 Some Equivalent Criteria for $\inf {π_{1},$ ..., $π_{r}} = 12$ ... $n$

Let $T (E_{r})$ denote the transitive part of the closure of $E_{r} : = \cup_{ℓ = 1}^{r} E (π_{ℓ})$ . Note that

any pair $(i, k) \in T (E_{r})$ has $k \underline{>} i + 2$ since we must be able to find $j$ with $i < j < k$ .

Hence, no pair $(i, i + 1)$ , $1 \underline{<} i \underline{<} n$ $- 1$ , could possibly belong to $T (E_{r})$ . By Lemma

9.2.1,

$E (\inf {π_{1}, ..., π_{r}}) = \bar{E_{r}} = E_{r} \cup$ $T (E_{r})$ .

So, if $\inf {π_{1}$ , . . . , $π_{r}} = 12$ $... n$ , the unique minimum in this lattice, then every

pair $(i, j)$ with $i < j$ belongs to $E (\inf {π_{1}, ..., π_{r}})$ and hence every pair $(i, i + 1)$ ,

$1 \underline{<} i \underline{<} n$ $- 1$ , must belong to $E_{r}$ . Thus, choosing $π_{1}$ , $...$ , $π_{r} \in S_{n}$ independently and

uniformly at random, we have proved the containment of events

${\inf {π_{1}, ..., π_{r}} = 12 ... n} \underline{\subset} \bar{\cap} {(i, i + 1) n 1 i = 1 \in \cup_{ℓ = 1}^{r} E (π_{ℓ})}$ .

But the event on the right is also sufficient for ${\inf {π_{1}, ..., π_{r}} = 12 ... n}!$ Indeed,

if every pair $(i, i + 1)$ , $1 \underline{<} i \underline{<} n$ $- 1$ , belongs to $E_{r}$ , then taking the transitive closure

of this set gives us every pair $(i, j)$ with $i < j!$ We have therefore proved

${\inf {π_{1}, ..., π_{r}} = 12 ... n}$ $= \bar{\cap} n 1 i = 1 {(i, i + 1) \in \cup_{ℓ = 1}^{r} E (π_{ℓ})}$ . (9.1)

We can take this a step further. Given $ω \in S_{n}$ , introduce the set of descents of $ω$ :

$D (ω) : = {i : ω (i) > ω (i + 1)}$ .

Consider the event on the right-hand side of (9.1). We have

$(i, i + 1)$ $\in \cup_{ℓ = 1}^{r} E (π_{ℓ}) \forall i \in [n - 1]$ $\Leftrightarrow \forall i \in [n - 1]$ , $\exists l \in [r]$ , $(i, i + 1)$ $\in E (π_{ℓ})$

$\Leftrightarrow \forall i \in [n - 1]$ , El $\in [r]$ , $i \notin D (π_{ℓ}^{- 1})$

$\Leftrightarrow \cap_{ℓ = 1}^{r} D (π_{ℓ}^{- 1}) = \emptyset$ .

(9.2)

Moreover, observe that

$i \in D$ $(\inf {π_{1}, ..., π_{r}}^{- 1}) \Leftrightarrow (i + 1, i) \in E^{*} (\inf {π_{1}, ..., π_{r}})$

$\Leftrightarrow (i, i + 1)$ $\notin E (\inf {π_{1}, ..., π_{r}})$

$\Leftrightarrow (i, i + 1)$ $\notin E (π_{j}) \forall j$

$\Leftrightarrow (i + 1, i) \in E^{*} (π_{j}) \forall j$

$\Leftrightarrow i \in D (π_{j}^{- 1}) \forall j$ .

This shows that $D$ $(\inf {π_{1}, ..., π_{r}}^{- 1}) = \cap_{ℓ = 1}^{r} D (π_{ℓ}^{- 1})$ . Combining this with (9.1) and

(9.2), we have therefore proved:

Lemma 9.3.1. Let $π_{1}$ , . . . , $π_{r} \in S_{n}$ be selected independently and uniformly at ran-

dom, and let $P_{n}^{(r)} : = P$ $(\inf {π_{1},$ ..., $π_{r}} = 12$ ...n). Then

$P_{n}^{(r)} (a) = P (_{i = 1}^{n_{\bar{\cap}} 1} {(i, i + 1) \in \cup_{ℓ = 1}^{r} E (π_{ℓ})})$

$(b) = P (D (\inf {π_{1}, ..., π_{r}}^{- 1}) = \cap_{ℓ = 1}^{r} D (π_{ℓ}^{- 1}) = \emptyset)$ $□$

This allows us to instead study the probabilities (a) and (b), whichever happens to

be convenient for us.

Given $ω \in S_{n}$ , let $ω^{'}$ denote $ω = ω (1) ... ω (n)$ reversed in order, so that $ω^{'} =$

$ω (n) ... ω (1)$ , i.e. $ω^{'} (j) = ω (n - j + 1)$ , $1 \underline{<} j \underline{<} n$ . For example, if $ω =$ 45123 then

$ω^{'} =$ 32154. It is trivial to check that

$\inf {π_{1}$ , . . . , $π_{r}} = τ$ $\Leftrightarrow$ $\sup {π_{1}^{'}$ , . . . , $π_{r}^{'}} = τ^{'}$ .

Indeed, this only requires the observation

$\cup_{ℓ = 1}^{r} E^{*} (π_{ℓ}^{'}) = {(j, i) : (i, j) \in \cup_{ℓ = 1}^{r} E (π_{ℓ})}$

followed by an application of Lemma 9.2.1. So we have

Lemma 9.3.2. Let $π_{1}$ , ..., $π_{r} \in S_{n}$ be selected independently and uniformly at ran-

dom. Then

$P_{n}^{(r)} = P (\inf {π_{1}, ..., π_{r}} = 12 ... n)$ $= P (\sup {π_{1}, ..., π_{r}} = n (n - 1) ... 1)$ .

Proof. We need only observe that $π_{1}$ , $...$ , $π_{r} \in S_{n}$ independent and uniformly ran-

dom implies that the permutations $π_{1}^{'}$ , . . . , $π_{r}^{'}$ are as well.

$□$

Hence, when answering the question "How likely is it that $r$ independent and uni-

formly random permutations have infimum (supremum resp.) equal to the unique

minimum (maximum resp.)?", Lemma 9.3.2 allows us to restrict our attention to

infimums. We are now in a position to prove Theorem 1.4.2, part 1.

9.4 Submultiplicativity Again

We wish to prove the submultiplicativity of $P_{n}^{(r)}$ as a function of $n$ , thus proving

existence of

$\lim_{n \to \infty} \sqrt[n]{P_{n}^{(r)}} = \inf_{n \geq 1} \sqrt[n]{P_{n}^{(r)}}$

([43, p. 23, ex. 98] again). For this, we make use of Lemma 9.3.1.

Let $π_{1}$ , $...$ , $π_{r}$ be independent and uniformly random permutations of $[n_{1} + n_{2}]$ . In-

troduce

$π_{i} [1, 2, ..., n_{1}]$ , $1 \underline{<} i \underline{<} r$ ,

the permutation of $[n_{1}]$ left after deletion of the elements $n_{1} + 1$ , $n_{1} + 2$ , $...$ , $n_{1} + n_{2}$

from $π_{i}$ . Similarly

$π_{i} [n_{1} + 1, n_{1} + 2, ..., n_{1} + n_{2}]$ , $1 \underline{<} i \underline{<} r$ ,

is the permutation of ${n_{1} + 1, n_{1} + 2, ..., n_{1} + n_{2}}$ left after deletion of the elements

1, 2, . . . ' $n_{1}$ from $π_{i}$ . Then the permutations

$π_{1} [1, ..., n_{1}]$ , . . . ' $π_{r} [1, ..., n_{1}]$ , $π_{1} [n_{1} + 1, ..., n_{1} + n_{2}]$ , . . . ' $π_{r} [n_{1} + 1, ..., n_{1} + n_{2}]$

are all uniform on their respective sets of permutations, and are mutually independent.

By Lemma 9.3.1,

$\inf {π_{1}, ..., π_{r}} = 12$ $... (n_{1} + n_{2}) \Leftrightarrow (i, i + 1)$ $\in \cup_{ℓ = 1}^{r} E (π_{ℓ})$ , $1 \underline{<} i \underline{<} n_{1} + n_{2} - 1$ ,

and hence

$\inf {π_{1}, ..., π_{r}} = 12$ $... (n_{1} + n_{2})$

$\to (i, i + 1)$ $\in \cup_{ℓ = 1}^{r} E (π_{ℓ} [1, ..., n_{1}])$ , $1 \underline{<} i \underline{<} n_{1} - 1$

$\Leftrightarrow \inf {π_{1} [1, ..., n_{1}], ..., π_{r} [1, ..., n_{1}]} = 12$ $... n_{1}$ .

Denote this first event by $E_{n_{1} + n_{2}}$ , and the last by $E_{n_{1}}$ . Thus we have proved the

containment of events $E_{n_{1} + n_{2}} \underline{\subset} E_{n_{1}}$ . Similarly, we have

$\inf {π_{1}$ , . . . , $π_{r}} = 12$ $... (n_{1} + n_{2})$

$\to (i, i + 1)$ $\in \cup_{ℓ = 1}^{r} E (π_{ℓ} [n_{1} + 1, ..., n_{1} + n_{2}])$ , $n_{1} + 1 \underline{<} i \underline{<} n_{1} + n_{2} - 1$

$\Leftrightarrow \inf {π_{1} [n_{1} + 1, ..., n_{1} + n_{2}], ..., π_{r} [n_{1} + 1, ..., n_{1} + n_{2}]}$

$= (n_{1} + 1) (n_{1} + 2)$ . . . $(n_{1} + n_{2})$ .

Denote the last event by $E_{n_{2}}^{*}$ , so that we have the containment $E_{n_{1} + n_{2}} \underline{\subset} E_{n_{2}}^{*}$ . Conse-

quently

$E_{n_{1} + n_{2}} \underline{\subset} E_{n_{1}} \cap E_{n_{2}}^{*}$ ,

and since the events on the right are independent, this implies $P_{n_{1} + n_{2}}^{(r)} \underline{<} P_{n_{1}}^{(r)} P_{n_{2}}^{(r)}$ Of

course, the rest of the statement follows from the (by now familiar) classical Fekete

lemma concerning sub(super)multiplicative sequences [43, p. 23, ex. 98].

too

9.5 Sharp Asymptotics of $P_{n}^{(r)}$

We are now ready to finish the proof of Theorem 1.4.2. The proof divides naturally

into three steps. First, we will establish the exact formula

$P_{n}^{(r)} = \sum_{k = 0}^{n - 1} (- 1)^{k}$ $b_{1} + ... + b_{n - k} = n \sum_{b_{1}, ..., b_{n - k} \geq 1}, (b_{1}!)^{r} ... (b_{n - k}!)^{r} 1$ . (9.3)

which in turn facilitates computation of a bivariate generating function related to

$P_{n}^{(r)}$ Finally, analytical techniques applied to a special case of this generating function

yields the asymptotic result stated in Theorem 1.4.2:

$P_{n}^{(r)} \sim - \frac{1}{z^{*} h_{r}^{'} (z^{*})} \frac{1}{(z^{*})^{n}}$ , $r \underline{>} 2$ , $n$ $\to \infty$ ,

where $z^{*} = z^{*} (r) \in (1, 2)$ is the unique (positive) root of the equation

$h_{r} (z) : = \sum_{j \geq 0} \frac{(- 1)^{j}}{(j!)^{r}} z^{j} = 0$

within the disk $| z | \underline{<} 2$ .

Specifically, we will use this exact formula for $P_{n}^{(r)}$ to show that

$P_{n}^{(r)} = [z^{n}] \frac{1}{h_{r} (z)}$ , $r \underline{>} 1$ , (9.4)

followed by some asymptotic analysis. As a partial check, for $r = 1$ we obtain

$P_{n}^{(1)} = [z^{n}] \frac{1}{e^{- z}} = \frac{1}{n!}$ ,

101

as we should! Also, we immediately see that for $r \underline{>} 2$ , the limit $\lim_{n \to \infty} \sqrt[n]{P_{n}^{(r)}}$ ,

whose existence we established last section, equals $1 / z^{*}$

9.5.1 Step 1: An Exact Formula for $P_{n}^{(r)}$

Here, we establish formula (9.3). Notice that, if $π_{1}$ , $...$ , $π_{r} \in S_{n}$ are independent

and uniformly random, then so are the $n$ -permutations $π_{1}^{- 1}$ , $...$ , $π_{r}^{- 1}$ . Hence, the

probability (b) in Lemma 9.3.1 is the same as

$P (i = \cap^{r} D (ω_{i}) 1 = \emptyset)$ ,

where $ω_{1}$ , $...$ , $ω_{r} \in S_{n}$ are independent and uniformly random. That is, we need

to compute the probability that $r$ independent and uniformly random permutations

have no common descents.

Now, given $I \underline{\subset} [n - 1]$ , let $E_{I}$ denote the event "I belongs to $D (ω_{j})$ , $1 \underline{<} j \underline{<} r$ " So

$E_{I}$ is the event that I is common to all of the $D (ω_{j})' s$ . Then, by Lemma 9.3.1,

$1 - P_{n}^{(r)} = P (_{i \in [n - 1]} \cup E_{{i}})$

By the principle of inclusion-exclusion,

$P (_{i \in [n - 1]} \cup E_{{i}}) = \sum_{k = 1}^{n - 1} (- 1)^{k - 1} I \subseteq$ $| I | = k \sum_{[n - 1]},$ $P (i \in \cap E_{{i}}) I$ (9.5)

But notice that, given $I \underline{\subset} [n - 1]$ ,

102

$i \in I \cap E_{{i}} = E_{I}$ .

Hence, (9.5) becomes

$P$ $(i \in [n \cup - 1] E_{{i}})$ $= \sum (- 1 n - 1$ $)^{k - 1}$ $\sum$ $P$ $(E_{I})$ . $(9.6)$

$k = 1$ $I \subseteq [n - 1]$

$| I | = k$

So it only remains to compute $P (E_{I})$ for a fixed $I \underline{\subset} [n - 1]$ , $| I |$ $= k$ , $k \in [n - 1]$ . This

computation is an $r$ -analog of the formula in Bona's book $[11, p g . 4]$ . We present a

modification of his argument.

Observe that

$P (E_{I}) = \frac{| E_{I} |}{(n!)^{r}}$ ,

so we need to count the number of $r$ -tuples $(ω_{1}$ , . . . , $ω_{r}) \in E_{I}$ .

Write $I$ $= {i_{1} < ... < i_{k}}$ , and $J : = [n - 1] ∖ I = {j_{1} < ... < j_{(n - 1) - k}}$ . For

$ω \in S_{n}$ , let $\bar{ω}$ denote $ω$ reversed in rank. So if $ω =$ 45123, then $\bar{ω} =$ 21543. Formally,

$\bar{ω} (j) = n$ $- ω (j) + 1$ , $1 \underline{<} j \underline{<} n$ . Notice that $D (ω) \cup$ $D (\bar{ω}) = [n - 1]$ . Hence

$D (ω_{j}) \underline{\supset} I$ , $1 \underline{<} j \underline{<} r$ $\Leftrightarrow$ $D ({\bar{ω}}_{j}) \underline{\subset} J$ , $1 \underline{<} j \underline{<} r$ .

Again, $ω_{1}$ , . . . , $ω_{r}$ independent and uniformly random implies that so are the permuta-

tions ${\bar{ω}}_{1}$ , $...$ , ${\bar{ω}}_{r}$ , so our task becomes to count the number of $r$ -tuples of permutations

$(τ_{1}$ , . . . , $τ_{r})$ such that $D (τ_{j}) \underline{\subset} J$ for every $j$ . As the $τ_{j}$ are independent, this is just

103

$| {ω \in S_{n} : D (ω) \underline{\subset} J} |^{r}$

To count $| {ω \in S_{n} : D (ω) \underline{\subset} J} |$ , we arrange the $n$ entries of $ω$ into $n$ $- k$ segments

so that the first $i$ segments together have $j_{i}$ entries for each $i$ . Then, within each

segment, we put the entries into increasing order. Then the only places where the

resulting $ω$ could possibly have a descent is where two segments meet, i.e., at entries

$j_{1}$ , $...$ , $j_{(n - 1) - k}$ , and hence $D (ω) \underline{\subset} J$ .

The first segment of $ω$ has to have length $j_{1}$ , and therefore can be chosen in ways.

The second segment has to be of length $j_{2} - j_{1}$ , and must be disjoint from the first

one, so may be chosen in ways. In general, segment $i$ must have length $j_{i} - j_{i - 1}$

if $1 < i < n$ $- k$ , and has to be chosen from the remaining $n$ $- j_{i - 1}$ entries, in

ways. There is only one choice for the last segment, as all remaining $n$ $- j_{(n - 1) - k}$

entries must go there. Therefore

$| {ω \in S_{n} : D (ω) \underline{\subset} J} | =$ . . .

$n$ !

$= \bar{j_{1}! (j_{2} - j_{1})! ... (n - j_{(n - 1) - k})!}$ '

and consequently

$P (E_{I}) = \frac{| E_{I} |}{(n!)^{r}} = \frac{1}{j_{1}!^{r} (j_{2} - j_{1})!^{r} ... (n - j_{(n - 1) - k})!^{r}}$ .

Putting this into (9.6), we obtain

104

$1 - P_{n}^{(r)} = P (_{i \in [n - 1]} \cup E_{{i}})$

$= \sum_{k = 1}^{n - 1} (- 1)^{k - 1} I \subseteq$ $| I | = k \sum_{[n - 1]}, \frac{1}{j_{1}!^{r} (j_{2} - j_{1})!^{r} ... (n - j_{(n - 1) - k})!^{r}}$

$= \sum_{k = 1}^{n - 1} (- 1)^{k - 1}$ $b_{1} + ... + b_{n - k} = n \sum_{b_{1}, ..., b_{n - k} \geq 1}, (b_{1}!)^{r} ... (b_{n - k}!)^{r} 1$ ,

where $b_{1} = j_{1}$ , $b_{i} = j_{i} - j_{i - 1}, 1$ $< i < n$ $- k$ , and $b_{n - k} = n$ $- j_{(n - 1) - k}$ . This is clearly

equivalent to (9.3).

9.5.2 Step 2: A Generating Function for $P_{n}^{(r)}$

Let us next use the formula (9.3) to establish the relation (9.4). Recall that we have

defined $E {i}$ as the event " $i$ belongs to every $D (π_{j}^{- 1})$ , $1 \underline{<} j \underline{<} n$ $- 1 "$ , and that

$1 - P_{n}^{(r)} = P (_{i = 1}^{n - 1} \cup E_{{i}})$

Introduce the random variable $S_{n}^{(r)} = S_{n}^{(r)}$ $(π_{1}, ..., π_{r})$ , the number of events $E {i}$ that

are satisfied. As we have seen (Lemma 9.3.1), $S_{n}^{(r)}$ is also the number of descents in

$\inf {π_{1}$ , . . . ' $π_{r}}^{- 1}$ Formally, $S_{n}^{(r)}$ is the sum of indicators

$S_{n}^{(r)} = \sum_{i = 1}^{n - 1} I_{E_{{i}}}$ .

Observe that

105

$P_{n}^{(r)} = P (S_{n}^{(r)} = 0)$ ,

so the formula (9.3) gives the probability $P (S_{n}^{(r)} = 0)$ . BBuutt, in ffaacctt, this formula tells

us even more about $S_{n}^{(r)}$ Indeed, consider the k-th (unsigned) term in this expression

$\sum 1 P$ $(i \in \cap E_{{i}}) I$ $=$ $\sum_{b_{1}, ..., b_{n - k} \geq 1}$ $(b_{1}!)^{r} ċ ċ . 1 (b_{n - k}!)^{r}$ .

$I \subseteq [y t - 1]$

$| I | = k$ $b_{1} + ... + b_{n - k} = n$

This is the expected number of $k$ -sets of the events $E_{{i}}$ that occur simultaneously.

That is,

$E [$ $] =$ $b_{1} + ... + b_{n - k} = n \sum_{b_{1}, ..., b_{n - k} \geq 1}, (b_{1}!)^{r} ... (b_{n - k}!)^{r} 1$ , $0 \underline{<} k \underline{<} n$ $- 1$ . (9.7)

This produces the simple expression

$P_{n}^{(r)} = \sum_{k = 0}^{n - 1} (- 1)^{k} E [$ $]$

We could have seen this another way, by observing that

$P_{n}^{(r)} = P (S_{n}^{(r)} = 0) = E [(1 - 1)^{S_{n}^{(r)}}] = E [\sum_{k = 0}^{n - 1} (- 1)^{k}$ $]$ ,

and using the linearity of expectation.

We will use these observations about $S_{n}^{(r)}$ to get a compact generating function re-

lated to this random variable, which happens to be amenable to asymptotic analysis.

Introduce the bivariate generating function

106

$F_{r} (x, y) : = \sum_{n \geq 1} x^{n} E [(1 + y)^{S_{n}^{(r)}}]$ ,

and let

$f_{r} (z) : = \sum_{β \geq 0} \frac{z^{β}}{(β + 1)!^{r}}$ .

Using what we know about $S_{n}^{(r)}$ , we can simplify $F_{r} (x, y) s$

$F_{r} (x, y) = \sum_{n \geq 1} x^{n} E [(1 + y)^{S_{n}^{(r)}}]$

$= \sum_{n \geq 1} x^{n} \sum_{k = 0}^{n - 1} y^{k} E [$ $]$

$= \sum_{n \geq 1} x^{n} \sum_{k = 0}^{n - 1} y^{k}$

$= \sum_{k \geq 0} (x y)^{k} \sum_{n > k}$

$= \sum_{k \geq 0} (x y)^{k} 1$

$= \sum_{k \geq 0} (x y)^{k} \sum_{ν \geq 1}$

$b_{1} + ... + b_{n - k} = n \sum_{b_{1}, ..., b_{n - k} \geq 1}$ $(b_{1}$ ! $)^{r}$ . . $1$ . $(b_{n - k}!)^{r}$

$x^{n - k}$ $b_{1} + ... + b_{n - k} =' n \sum_{b_{1}, ..., b_{n - k} \geq 1}$ $(b_{1}!)^{r} ... (b_{n - k}!)^{r} 1$

$x^{U} \sum_{b_{1} .' . ċ, b_{U} \geq 1 b_{1} + ċ + b_{U} = ν + k} (b_{1}!)^{r} ċ ċ (b_{U}!)^{r} 1$ .

$x^{U}$ $β_{1} + ... + β_{U} =' k \sum_{β_{1}, ..., β_{U} \geq 0} (β_{1} + 1)!^{r} ... (β_{U} + 1)!^{r}$

107

$= \sum_{k \geq 0} (x y)^{k} [z^{k}] \sum_{ν \geq 1} (x f_{r} (z))^{ν}$

$= \sum_{k \geq 0} (x y)^{k} [z^{k}] \frac{x f_{r} (z)}{1 - x f_{r} (z)}$

$= \frac{x f_{r} (x y)}{1 - x f_{r} (x y)}$

$= \frac{1}{1 - x f_{r} (x y)} - 1$ .

Therefore

$E [(1 + y)^{S_{n}^{(r)}}] = [x^{n}] \frac{1}{1 - x f_{r} (x y)}$ , $n \underline{>} 1$ . (9.8)

Plugging $y = - 1$ into this expression, we obtain

$P_{n}^{(r)} = P (S_{n}^{(r)} = 0) = E [(1 - 1)^{S_{n}^{(r)}}] = [x^{n}] \frac{1}{1 - x f_{r} (- x)}$

(9.9)

$= [x^{n}] \frac{1}{h_{r} (x)}$ , $n \underline{>} 1$ ,

where $h_{r} (x) = \sum_{j \geq 0} ((- 1)^{j} / (j!)^{r}) x^{j}$ , and this is (9.4). It should be duly noted that

this generating function is a special case of one found by Richard Stanley [45], but it

is probably safe to say that he was unaware of any connection with the weak ordering.

9.5.3 Step 3: Asymptotics

We are about to finish the proof; all of the combinatorial insights are behind us, and

only some asymptotic analysis remains. Armed with formula (9.9), our goal is to use

Darboux's theorem [2] to estimate

108

$[z^{n}] \frac{1}{h_{r} (z)}$ , $h_{r} (z) = \sum_{j \geq 0} \frac{(- 1)^{j}}{(j!)^{r}} z^{j}$ , $r \underline{>} 2$ .

First of all notice that for $z > 0$ we have

$1 - z$ $< h_{r} (z) < 1$ $- z + z^{2} / (2!)^{r}$

Hence, we get

$0 = 1$ $- (1)$ $< h_{r} (1)$ ; $h_{r} (2) < 1$ $- (2) + (2)^{2} / (2!)^{r} \underline{<} 0$ , $r \underline{>} 2$ .

So $h_{r} (z) = 0$ has a root in $(1, 2)$ by the intermediate value theorem.

Now consider the circle $| z | = u$ , where $u > 1$ will be specified later. Let

$g (z) = 1$ $- z$ , $G (z) = \sum_{j \geq 2} \frac{(- 1)^{j}}{(j!)^{r}} z^{j}$ .

$g (z) = 0$ has a single root, of multiplicity 1, within the circle $| z | = u$ . For $| z | = u$ ,

$| g (z) | \underline{>} \min_{t \in [0, 2 π)} | 1$ $- u e^{i t} | = u - 1$ ,

and

$| G (z) | \underline{<} \frac{u^{2}}{2^{r}} (1$ $+ \frac{u}{3^{r}} + \frac{u}{3^{r}} \frac{u}{4^{r}} + ...)$

$\underline{<} \frac{u^{2}}{2^{r}}$ . $\frac{1}{1 - \frac{u}{3^{r}}}$ , $u < 3^{r}$

If we can find $u \in$ $(1, 3^{r})$ such that

109

$u - 1$ $> \frac{\frac{u^{2}}{2^{r}}}{1 - \frac{u}{3^{r}}}$ ,

(9.10)

then, by Rouche's theorem [48], $h_{r} (z) = g (z) + G (z)$ also has a unique, whence real

positive, root $z^{*}$ within the circle $| z | = u$ . The inequality (9.10) is equivalent to

$F (u) : = u^{2} (2^{- r} + 3^{- r}) - u (1 + 3^{- r}) + 1$ $< 0$ .

$F (u)$ attains its minimum at

$\bar{u} = \frac{1 + 3^{- r}}{2 (2^{- r} + 3^{- r})} \in$ $(1, 3^{r})$ ,

and

$F (\bar{u}) = 1$ $- \frac{(1 + 3^{- r})^{2}}{4 (2^{- r} + 3^{- r})}$ .

For $r > 2$ ,

4 $(2^{- r} + 3^{- r}) \underline{<} 8$ . $2^{- 3} = 1$ ,

and so $F (\bar{u}) < 0$ in this case, and we are done. Actually, notice that our choice of

circle radius

$| z | = \bar{u} = \frac{1 + 3^{- r}}{2 (2^{- r} + 3^{- r})} \in (2, 3^{r})$ , $r > 2$ .

So we have proved $h_{r} (z) = 0$ has a unique (positive) root $z^{*} = z^{*} (r) \in (1, 2)$ within

the disk $| z | \underline{<} 2$ , $r > 2$ , which is what we wanted.

110

On the other hand, for $r = 2$ ,

$F (\bar{u}) = 1$ $- \frac{(1 + 1 / 9)^{2}}{1 + 4 / 9} > 0$ ,

so this case requires a bit more attention. Instead, consider

$g (z) = 1$ $- z + \frac{z^{2}}{(2!)^{2}} - \frac{z^{3}}{(3!)^{2}}$ , $G (z) = \sum_{j \geq 4} \frac{(- 1)^{j}}{(j!)^{2}} z^{j}$ ,

and our strategy will be analogous to the above. First,

$g^{'} (z) = - 1 + z / 2 - z^{2} / 12 = - \frac{(z - 3)^{2} + 3}{12} < 0$ , $z \in R$ ,

so $g (z) = 0$ has one real root, $z_{1}$ . Since $g (1)$ $= 2 / 9 > 0$ and $g (2) = - 2 / 9 < 0$ , we

have $z_{1} \in$ $(1, 2)$ .

Let $z_{2} = a + i b$ , $z_{2}^{-} = a - i b$ denote the two complex roots of $g (z) = 0$ . Then (Vieta's

relations [48] $)$

$2 a + z_{1} = 9$ , $(a^{2} + b^{2}) z_{1} = 36$ .

In particular

$a = \frac{9 - z_{1}}{2} > 3.5$ ,

hence $| z_{2} | = | z_{2}^{-} | > 3.5$ . So, if we can find $u \in$ $(z_{1}$ , 3.5 $)$ with

$| g (z) | > | G (z) |$ , $| z | = u$ ,

we will be done once again by Rouche's theorem. For $| z | = u$ ,

$| G (z) | \underline{<} \frac{u^{4}}{(4!)^{2}} (1$ $+ \frac{u}{52} + \frac{u}{52} \frac{u}{6^{2}} + ...)$

(9.11)

$\underline{<} \frac{u^{4}}{(4!)^{2}}$ . $\frac{1}{1 - \frac{u}{5^{2}}}$ , $u < 5^{2}$

Take $u = 2$ . Let us show that

$\min_{| z | = 2} | g (z) | = | g (2) | = \frac{2}{9}$ .

To this end, we bound

$| g (z) | = \frac{1}{36} | (z - z_{1}) (z - z_{2}) (z - z_{2}^{-}) |$

$\underline{>} \frac{1}{36} (2 - z_{1}) \min_{| z | = 2} | z - z_{2} | | z - z_{2}^{-} |$ .

Setting $z = 2 e^{i t}$ , we obtain

$| z - z_{2} |^{2} | z - z_{2}^{-} |^{2} =$ [(2 cos7 $- a)^{2} + (2$ $\sin t$ $- b)^{2}$ ] [(2 cos7 $- a)^{2} + (2$ $\sin t$ $+ b)^{2}$ ]

$= (4 - 4 a \cos t + a^{2} + b^{2} - 4 b \sin t) (4 - 4 a \cos t + a^{2} + b^{2} + 4 b \sin t)$

$= (4 - 4 a \cos t + a^{2} + b^{2})^{2} - 16 b^{2} \sin^{2} t$

$: = F (t)$ .

Then

$F^{'} (t) = 8 a \sin t (4 - 4 a \cos t + a^{2} + b^{2}) - 32 b^{2} \sin t \cos t$

$= 8$ $\sin t [a (4 + a^{2} + b^{2}) - 4 (a^{2} + b^{2}) \cos t]$

112

So $F^{'} (t) = 0$ if and only if $t = 0$ , $π$ , since

$\frac{a (4 + a^{2} + b^{2})}{4 (a^{2} + b^{2})} = \frac{a}{4} + \frac{a}{a^{2} + b^{2}}$

$= \frac{9 - z_{1}}{8} + \frac{z_{1} (9 - z_{1})}{72}$

$= \frac{81 - z_{1}^{2}}{72} > \frac{77}{72} > 1$ .

This inequality also shows that $F^{'} (t)$ always has the same sign as $\sin t$ , hence $F^{'} (t) > 0$

for $t \in (0, π)$ and $F^{'} (t) < 0$ for $t \in (π, 2 π)$ . So $F (t)$ attains its minimum at $t = 0$ ,

and consequently on $| z | = 2$

$| g (z) | \underline{>} (2 - z_{1}) \sqrt{F (0)} = (2 - z_{1}) (4 - 4 a + a^{2} + b^{2})$

$= (2 - z_{1}) (2 - z_{2}) (2 - z_{2}^{-})$

$= g (2) = \frac{2}{9}$ .

Combining this with (9.11), we are done since

$| g (z) | \underline{>} \frac{2}{9} > \frac{\frac{2^{4}}{(4!)^{2}}}{1 - \frac{2}{5^{2}}} \underline{>} | G (z) |$ , $| z | = 2$ . $□$

113

(JIAPTER 10

OPEN PROBLEMS

In this final chapter, we present some problems that we find important $a n d / o r$ inter-

esting, and which we intend to pursue in future research.

10.1 The Problems

Problem 10.1.1. Compute exactly the limit $\lim_{n \to \infty} \sqrt[n]{Q_{n}}$ in the proof of Theorem

1.2.1, lower bound.

Problem 10.1.2. Compute exactly the limit $\lim_{n \to \infty} \sqrt[n]{Q_{n}^{*}}$ in the proof of Theorem

1.4.1, upper bound.

Problem 10.1.3. Find an argument that improves the lower bound in Theorem Le. 1

to something on the order of $n^{-}$ ' for some a $> 0$ .

Problem 10.1.4. Find an argument that improves the lower bound in Theorem 1.4.1

to something of exponentially small order.

Problem 10.1.5. Find extensions to chains of length r for the other bounds in both

orders, similar to that in the case of Bruhat order (upper bound).

114

BIBLIOGRAPHY

[1] R. M. ADIN, Y. ROICHIVIAN, On Degrees in the Hasse Diagram of the

Strong Bruhat Order, Seminaire Lotharingien de Combinatoire 53 (2004),

12 pp.

[2] E. BENDER, Asymptotic Methods in Enumeration, SIAM Review 16 (1974),

no. 4, pp. 485-515.

[3] C. BERGE, Principles of Combinatorics, Vol. 72 of Mathematics in Science

and Engineering: A Series of Monographs and Textbooks, Academic Press,

Inc., New York, 1971.

[4] P. BILLINGSLEY, Probability and Measure, 3 d ed., John Wiley & Sons, 1nc.,

New York, 1995.

[5] A. BJÖRNER, Orderings of Coxeter Groups, in Combinatorics and Algebra

(C. GREENE, ed.), Vol. 34 of Contemp. Math., American Mathematical

Society, Providence, RI, 1984 pp. 175-195.

[6] A. BJÖRNER, F. BRENTI, An Improved Tableau Criterion for Bruhat Or-

der, Electron. J. Combin. 3 (1996), #R22, 5 pp. (electronic).

[7] A. BJÖRNER, F. BRENTI, Combinatorics of Coxeter Groups, Springer, New

York, 2005.

[8] A. BJÖRNER, M. Wachs, $q$ -Hook Length Formulas for Forests, Journal of

Combinatorial Theory, Series A 52 (1989), pp. 165-187.

[9] IVI. BOacuteNA, The Permutation Classes Equinumerous to the Smooth Class,

Electron. J. Combin. 5 (1998), #R31, 12 pp. (electronic).

[10] IVI. BOacuteNA, The Solution of a Conjecture of Stanley and Wilf for all Layered

Patterns, Journal of Combinatorial Theory, Series A 85 (1999), pp. 96-104.

[11] IVI. BOacuteNA, Combinatorics of Permutations, Discrete Mathematics and its

Applications, Chapman & $H a 11 / C R C$ , Boca Raton, 2004.

115

[12]

IVI. BOacuteNA, Personal communication about an early preprint, August 2006.

[13] D. BRESSOUD, Proofs and Confirmations: The Story of the Alternating

Sign Matrix Conjecture, Cambridge University Press, Cambridge, 1999.

[14] G. BRIGHTWELL, P. TETALI, The Number of Linear Extensions of the

Boolean Lattice, Order 20 (2003), pp. 333-345.

[15] E. R. CANFIELD, The Size of the Largest Antichain in the Partition Lattice,

Journal of Combinatorial Theory, Series A 83 (1998), no. 2, pp. 188-201.

[16] E. R. CANfiELD, Meet and Join within the Lattice of Set Partitions, Elec-

tron. J. Combin. 8 (2001), #R15, 8 pp. (electronic).

[17] E. R. CANFIELD, Integer Partitions and the Sperner Property: Selected

Papers in Honor of Lawrence Harper, Theoret. Comput. Sci. 307 (2003),

no. 3, pp. 515-529.

[18] E. R. CANFIELD, K. ENGEL, An Upper Bound for the Size of the Largest

Antichain in the Poset of Partitions of an Integer, Proceedings of the Con-

ference on Optimal Discrete Structures and Algorithms-ODSA '97 (Ros-

tock), Discrete Appl. Math. 95 (1999), no. 1-3, pp. 169-180.

[19] IVI. -P. DELEST, G. VIENNOT, Algebraic Languages and Polyominoes Enu-

meration, Theoret. Comput. Sci. 34 (1984), no. 1-2, pp. 169-206.

[20] V. DEODHAR, Some Characterizations of Bruhat Ordering on a Coxeter

Group and Determination of the Relative Möbius Function, Inventiones

Math. 39 (1977), pp. 187-198.

[21] B. DRAKE, S. GERRISH, IVI. SKANDERA, Trvo Nerv Criteria for Compar-

ison in the Bruhat Order, Electron. J. Combin. 11 (2004), #N6, 4 pp.

(electronic).

[22] C. EHRESIVIANN, Sur la Topologie de Certains Espaces Homogenes, Ann.

Math. 35 (1934), pp. 396-443.

[23] K. ENGEL, Sperner Theory, Encyclopedia of Mathematics and its Applica-

tions 65, Cambridge University Press, Cambridge, New York, 1997.

[24] S. FOIVIIN, Personal communication at the Michigan University Combina-

torics Seminar, April 2005.

116

[25]

W. FULTON, Young Tableaux: With Applications to Representation The-

ory and Geometry, Vol. 35 of London Mathematical Society Student Texts,

Cambridge University Press, New York, 1997.

[26] I. GESSEL, G. VIENNOT, Binomial Determinants, Paths, and Hook Length

Formulae, Advances in Mathematics 58 (1985), no. 3, pp. 300-321.

[27] A. HAIVIIVIETT, On the Random Permutation-induced Poset, in preparation.

[28] A. HAIVIIVIETT, B. PITTEL, Horv Often are Trvo Permutations Comparable $l . ?$ ,

to appear in Transactions of the American Mathematical Society, accepted

2006; $a r X i v : m a t h . P R / 0605490$ .

[29] A. HAIVIIVIETT, B. PITTEL, Meet and Join in the Weak Order Lattice,

preprint, 2006; available at http://www.math.ohio-state.edu/ $\sim h a m m e t t$ .

[30] J. E. HUIVIPHREYS, Reflection Groups and Coxeter Groups, Cambridge

Studies in Advanced Mathematics, No. 29, Cambridge University Press,

Cambridge, 1990.

[31] S. JANSON, T. Luczak, A. $R U C I \overset{´}{N}$ SKI, Random Graphs, John Wiley &

Sons, Inc., New York, 2000.

[32] J. H. KIM, B. PITTEL, On Tail Distribution of Interpost Distance, Journal

of Combinatorial Theory, Series B80 (2000), no. 1, pp. 49-56.

[33] D. KLEITIVIAN, J. SHA, The Number of Linear Extensions of Subset Order-

ing, Discrete Math. 63 (1987), pp. 271-279.

[34] D. KNUTH, Sorting and Searching: The Art of Computer Programming,

Vol. III, Addison-Wesley Publishing Company, Inc., Reading, 1973.

[35] C. KRATTENTHALER, Generating Functions for Plane Partitions of a Given

Shape, Manuscripta Mathematica 69 (1990), pp. 173-201.

[36] A. Lascoux, IVI. P. SCHUTZENBERGER, Treillis et bases des groupes de

Coxeter, Electron. J. Combin. 3 (1996), #R27, 35 pp. (electronic).

[37] A. MARCUS, G. TARDOS, Excluded Permutation 7atrices and the Stanley-

Wilf Conjecture, Journal of Combinatorial Theory, Series A 107 (2004), no.

1, pp. 153-160.

117

[38]

V. G. MIKHAILOV, V. A. VATUTIN, Limit Theorems for the Number of

Empty Cells in an Equiprobable Scheme for Group Allocation of Particles,

Teor. Veroyatnost. i Primenen. 27 (1982), pp. 684-692 (Russian); Theor.

Probab. Appl. 27, pp. 734-743 (English transl.).

[39] B. PITTEL, Random Set Partitions: Asymptotics of Subset Counts, Journal

of Combinatorial Theory, Series A 79 (1997), pp. 326-359.

[40] B. PITTEL, Confirming Trvo Conjectures About the Integer Partitions, Jour-

nal of Combinatorial Theory, Series A 88 (1999), pp. 123-135.

[41] B. PITTEL, Where the Typical Set Partitions Meet and Join, Electron. J.

Combin. 7 (2000), #R5, 15 pp. (electronic).

[42] B. PITTEL, R. TUNGOL, A Phase Transition Phenomenon in a Random

Directed Acyclic Graph, Random Structures and Algorithms 18 (2001), no.

2, pp. 164-184.

[43] G. POacuteLYA, G. SZEGO, Problems and Theorems in Analysis, Springer, New

York, 1976.

[44] V. N. SACHKOV, Probabilistic Aethods in Combinatorial Analysis, Encyclo-

pedia of Mathematics and its Applications, Vol. 56, Cambridge University

Press, Cambridge, 1997.

[45] R. STANLEY, Binomial Posets, Möbius Inversion, and Permutation Enu-

meration, Journal of Combinatorial Theory, Series A 20 (1976), pp. 336-

356.

[46] R. STANLEY, Enumerative Combinatorics, Vol. I, Cambridge University

Press, Cambridge, 1997.

[47] R. STANLEY, Enumerative Combinatorics, Vol. II, Cambridge University

Press, Cambridge, 1999.

[48] E. STEIN, R. SHAKARCHI, Princeton Lectures in Analysis II.. Complex

Analysis, Princeton University Press, Princeton, 2003.

[49] L. TAKACS, Combinatorial 0ethods in the Theory of Stochastic Processes,

John Wiley & Sons, Inc., New York, 1967.

[50]

R. WARLIIVIONT, Permutations Avoiding Consecutive Patterns, Ann. Univ.

Sci. Budapest. Sect. Comput. 22 (2003), pp. 373-393.

[51] R. WARLIIVIONT, Permutations Avoiding Consecutive Patterns, If Arch.

Math. (Basel) 84 (2005), no. 6, pp. 496-502.

119