ON COMPARABILITY OF RANDOM PERMUTATIONS

DISSERTATIO $\mathrm{N}$

Presented in Partial Fulfillment of the Requirements for

the Degree Doctor of Philosophy in the Graduate

School of the Ohio State University

By

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

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

The Ohio State University

2007

Dissertation Committee:

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

Dr. Boris Pittel, Advisor

Dr. Gerald Edgar

1 $\mathrm{ċ}$.

Advisor

Dr. Akos Seress Graduate Program in

Graduate Program in Mathematics

ABSTRACT

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ii

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

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

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

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

working in this direction.

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

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

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

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

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

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

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

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

iii

To my wife, Rachael, for her unending suppport.

iv

ACKNOWLEDGMENTS

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

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

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

outstanding example of what a mentor should be.

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

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

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

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

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

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

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

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

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

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

Richard Stanley's book.

$\mathrm{v}$

VITA

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

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

Westmont College - Santa Barbara, CA

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

Westmont College

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

The Ohio State University

FIELDS OF STUDY

Major Field: Mathematics

Specialization: Combinatorial Probability

vi

TABLE OF CONTENTS

Abstract ii

Dedication . 1v

Acknowledgments . $\mathrm{v}$

Vita vi

List of Figures $\mathrm{x}$

List of Tables xi

CHAPTER PAGE

1 Introduction 1

1.1 Bruhat Order, Preliminaries 1

1.2 Main Results Related to the Bruhat Order 5

1.3 Weak Order, Preliminaries 7

1.4 Main Results Related to the Weak Order 8

2The Proof of the Bruhat Order Upper Bound 14

2.1 A Necessary Condition for Bruhat Comparability 14

2.2 A Probabilistic Simplification 21

2.3 Asymptotics 23

3The Proof of the Bruhat Order Lower Bound . 26

3.1 A Sufficient Condition for Bruhat Comparability 26

3.2 A Reduction to Uniforms 29

3.3 An Algorithm to Maximize the Bound 34

vii

4

An Extension to Chains in Bruhat Order

39

4.1 The General Setup . 39

4.2 A Tractable Necessary Condition 41

4.3 The Core Counting Problem 42

4.4 A Probabilistic Simplification 56

4.5 Asymptotics 57

5Some Properties of the Weak Ordering 62

5.1 A Criterion for Weak Comparability 62

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

6 The Proof of the Weak Order Upper Bound 67

6.1 A Necessary Condition for Weak Comparability 67

6.2 A Reduction to Uniforms 69

6.3 An Algorithm to Minimize the Bound 71

7The Proof of the Weak Order Lower Bound 75

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

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

7.3 Linear Extensions of Arbitrary Finite Posets 81

8Numerics . 83

8.1 Bruhat Order Numerics 83

8.2 Weak Order Numerics 85

9On Infs and Sups in the Weak Order Lattice 89

9.1 A Connection with Complete, Directed, Acyclic Graphs 89

9.2 Computing Infs and Sups in the Weak Order Lattice 93

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

9.4 Submultiplicativity Again 99

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

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

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

9.5.3 Step 3: Asymptotics 108

Vlll

10

Open Problems

114

10.1 The Problems 114

Bibliography 115

IX

LIST OF FIGURES

FIGURE PAGE

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

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

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

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

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

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

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

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

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

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

4.3 An intersecting nest of 7 lattice paths. 47

4.4 "Swapping" the tails in Figure 4.3. 49

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

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

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

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

$\mathrm{x}$

LIST OF TABLES

TABLE PAGE

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

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

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

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

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

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

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

Xi

(JIAPTER 1

INTRODUCTION

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

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

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

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

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

torics, [46] and [47].

1.1 Bruhat Order, Preliminaries

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

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

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

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

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

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

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

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

1

4321

321

312

132

123

1234

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

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

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

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

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

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

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

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

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

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

2

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

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

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

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

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

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

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

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

comparisons of the two tableaux

12451235

14 5 1 2 5

1412

4 2

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

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

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

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

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

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

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

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

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

3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4

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

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

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

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

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

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

is illustrated in this figure.

1.2 Main Results Related to the Bruhat Order

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

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

5

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

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

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

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

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

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

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

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

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

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

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

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

out of sight presently.

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

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

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

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

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

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

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

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

6

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

to r-tuples:

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

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

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

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

the Bruhat order poset.

1.3 Weak Order, Preliminaries

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

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

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

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

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

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

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

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

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

7

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

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

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

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

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

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

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

1.4 Main Results Related to the Weak Order

We prove the following probabilistic result for weak order comparability:

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

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

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

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

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

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

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

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

8

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

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

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

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

to be a way to vastly improve it.

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

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

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

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

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

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

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

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

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

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

in the proof of Theorem 1.4.1, lower bound.

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

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

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

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

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

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

9

1 2

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

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

(1.1) delivers only

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

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

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

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

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

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

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

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

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

prove the following:

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

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

to

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

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

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

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

from which we obtain (Darboux theorem [2])

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

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

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

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

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

the exact formula

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

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

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

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

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

11

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

question here is:

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

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

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

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

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

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

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

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

work had with the weak ordering.

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

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

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

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

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

of set partitions of $\mathrm{\left[}\mathit{n}\mathrm{\right]}$ ordered by refinement. In [16], E. R. Canfield presents an

enlightening extension of the $\inf \mathrm{/}\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.

12

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).

13

(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

$\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right)}\mathrm{=}\mathit{O}\mathrm{\left(}{\mathit{n}}^{\mathrm{-}\mathrm{2}}\mathrm{\right)}$.

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

minor modifications are necessary for $\mathit{n}$ odd.

2.1 A Necessary Condition for Bruhat Comparability

The $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{1}\mathrm{)}$-matrix criterion requires that a set of ${\mathit{n}}^{\mathrm{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 $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ satisfies all the chosen conditions. On the other hand, collectively

these conditions need to be quite stringent for this probability to be $\mathit{o}\mathrm{\left(}\mathrm{1}\mathrm{\right)}$. In our first

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

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

job.

14

Let us split the matrices $\mathit{M}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$, $\mathit{M}$ $\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and $\mathit{M}$ $\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ into 4 submatrices of equal size

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

${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{(}\mathrm{ċ}\mathrm{)}$, ${\mathit{M}}_{\mathit{n}\mathit{e}}\mathrm{(}\mathrm{ċ}\mathrm{)}$, ${\mathit{M}}_{\mathit{n}\mathit{w}}\mathrm{(}\mathrm{ċ}\mathrm{)}$ and ${\mathit{M}}_{\mathit{s}\mathit{e}}\mathrm{(}\mathrm{ċ}\mathrm{)}$ respectively. In the southwest corner ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$,

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

If $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$, then as we read off rows of ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ 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

$\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ such that this occurs by ${{E}}_{\mathit{s}\mathit{w}}$. We draw analogous conclusions for the northeast

corner, reading rows from top to bottom, and we denote by ${{E}}_{\mathit{n}\mathit{e}}$ the set of pairs $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$

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 $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$

by ${{E}}_{\mathit{n}\mathit{w}}$. The same condition holds for the southeast corner when we read columns

from right to left. Denote the set of these pairs $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ by ${{E}}_{\mathit{s}\mathit{e}}$. Letting ${E}$ denote the

set of pairs $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ satisfying all four of the conditions above, we get

$\mathrm{\left\{}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right\}}\underset{\mathrm{‾}}{\mathrm{\subset }}{E}\mathrm{=}{{E}}_{\mathit{s}\mathit{w}}\mathrm{\cap }{{E}}_{\mathit{n}\mathit{e}}\mathrm{\cap }{{E}}_{\mathit{n}\mathit{w}}\mathrm{\cap }{{E}}_{\mathit{s}\mathit{e}}$.

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

criterion. And unlike the set $\mathrm{\left\{}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right\}}$, we are able to compute $\mathrm{\left|}{E}\mathrm{\right|}$, and to show that

$\mathit{P}\mathrm{\left(}{E}\mathrm{\right)}\mathrm{=}\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathrm{-}\mathrm{2}}\mathrm{|}{E}\mathrm{|}\mathrm{=}\mathit{O}\mathrm{(}{\mathit{n}}^{\mathrm{-}\mathrm{2}}\mathrm{)}$. 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 $\mathit{M}\mathrm{(}\mathit{\pi }{\mathrm{)}}_{\mathit{I}\mathrm{,}\mathit{J}}$ ( $\mathit{M}\mathrm{(}\mathit{\sigma }{\mathrm{)}}_{\mathit{I}\mathrm{,}\mathit{J}}$ resp.) contains a marked entry, we

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

15

$\mathit{M}\mathrm{(}\mathit{\pi }\mathrm{,}\mathit{0}\mathrm{)}$

-

$\mathrm{\downarrow }$

$\mathrm{|}$

-

Figure 2.1: Finding a necessary condition for $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$.

equals the number of marked entries in $\mathit{M}\mathrm{(}\mathit{\pi }{\mathrm{)}}_{\mathit{I}\mathrm{,}\mathit{J}}$ ( $\mathit{M}\mathrm{(}\mathit{\sigma }{\mathrm{)}}_{\mathit{I}\mathrm{,}\mathit{J}}$ resp.). Now, given $\mathit{\pi }$, $\mathit{\sigma }$,

let ${\mathit{M}}_{\mathrm{1}}\mathrm{=}{\mathit{M}}_{\mathrm{1}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$, ${\mathit{M}}_{\mathrm{2}}\mathrm{=}{\mathit{M}}_{\mathrm{2}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ denote the total number of rows that support ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$

and ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ respectively. Then ${\mathit{M}}_{\mathit{n}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ , ${\mathit{M}}_{\mathit{n}\mathit{w}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ are supported by ${\mathit{M}}_{\mathrm{3}}\mathrm{=}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{M}}_{\mathrm{1}}$

columns and by ${\mathit{M}}_{\mathrm{4}}\mathrm{=}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{M}}_{\mathrm{2}}$ columns respectively. The same holds for the

southeastern corners of $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and $\mathit{M}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$. Obviously the northeastern submatrices of

$\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and $\mathit{M}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ are supported by ${\mathit{M}}_{\mathrm{1}}$ rows and ${\mathit{M}}_{\mathrm{2}}$ rows respectively. Then we have

16

$\mathit{P}\mathrm{\left(}{E}\mathrm{\right)}\mathrm{=}{{\displaystyle \sum }}_{{\mathit{m}}_{\mathrm{1}}\mathrm{,}{\mathit{m}}_{\mathrm{2}}}\mathit{P}\mathrm{(}{E}\mathrm{\cap }\mathit{A}\mathrm{}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{\left)}\mathrm{\right)}$,

(2.1)

$\mathit{A}$ $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{)}\mathrm{:}\mathrm{=}\mathrm{\left\{}\mathrm{\right(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}\mathrm{}\mathrm{:}\mathrm{}{\mathit{M}}_{\mathrm{1}}\mathrm{=}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{M}}_{\mathrm{2}}\mathrm{=}{\mathit{m}}_{\mathrm{2}}\mathrm{\}}$ .

Clearly ${E}\mathrm{\cap }\mathit{A}$ $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{)}\mathrm{=}\mathrm{\varnothing }$ if ${\mathit{m}}_{\mathrm{1}}\mathrm{<}{\mathit{m}}_{\mathrm{2}}$. We claim that, for ${\mathit{m}}_{\mathrm{1}}\underset{\mathrm{‾}}{\mathrm{>}}{\mathit{m}}_{\mathrm{2}}$,

$\mathit{P}\mathrm{(}{E}\mathrm{\cap }\mathit{A}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{\left)}\mathrm{\right)}\mathrm{=}\mathrm{[}\frac{\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}\mathrm{)}}{\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{+}\mathrm{1}\mathrm{)}}{\mathrm{]}}^{\mathrm{4}}\mathrm{ċ}\frac{{{\displaystyle \prod }}_{\mathit{i}\mathrm{=}\mathrm{1}}^{\mathrm{4}}\left(\begin{array}{c}\mathit{n}\mathrm{/}\mathrm{2}\\ {\mathit{m}}_{\mathit{i}}\end{array}\right)}{{\mathrm{(}}_{\mathit{n}\mathrm{/}\mathrm{2}}^{\mathit{n}}{\mathrm{)}}^{\mathrm{2}}}$. (T)

Here and below ${\mathit{m}}_{\mathrm{3}}\mathrm{:}\mathrm{=}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{1}}$ and ${\mathit{m}}_{\mathrm{4}}\mathrm{:}\mathrm{=}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}$ stand for generic values of ${\mathit{M}}_{\mathrm{3}}$

and ${\mathit{M}}_{\mathrm{4}}$ in the event $\mathit{A}$ $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{)}$.

To prove (T), let us count the number of pairs $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ in ${E}\mathrm{\cap }\mathit{A}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{)}$. First consider

the southwest corner, ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$. Introduce ${\mathit{L}}_{\mathrm{1}}\mathrm{=}{\mathit{L}}_{\mathrm{1}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$, the number of rows

supporting both ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$. So ${\mathit{L}}_{\mathrm{1}}$ is the number of rows in the southwest

corner ${\mathit{M}}_{\mathit{s}\mathit{w}}$ $\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ containing both a cross and a ball. Suppose that we are on the

event $\mathrm{\{}{\mathit{L}}_{\mathrm{1}}\mathrm{=}{\mathit{P}}_{\mathrm{1}}\mathrm{\}}$. We choose ${\mathit{p}}_{\mathrm{1}}$ rows to support both ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ from the

$\mathit{n}\mathrm{/}\mathrm{2}$ first rows. Then, we choose $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{+}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{)}$ more rows from the remaining

$\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{)}$ rows. Each of these secondary rows is to support either ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ or ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ ,

but not both. This step can be done in

ways. Next, we partition the set of $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{+}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{)}$ secondary rows into two row

subsets of cardinality $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}$ (rows to contain crosses) and $\mathrm{(}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}$ (rows to contain

balls) that will support ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ , accompanying the ${\mathit{p}}_{\mathrm{1}}$ primary rows

17

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

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

${\mathit{p}}_{\mathrm{1}}$ elements labeled by a ball and a cross, and another with $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{+}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{)}$ elements,

$\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}$ labeled by crosses and the remaining $\mathrm{(}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}$ elements labeled by balls.

The condition ${{E}}_{\mathit{s}\mathit{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 $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{+}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{)}$-long

sequences of ${\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}$ crosses and ${\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{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] $\mathrm{)}$, the total number of such sequences equals

$\frac{\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{-}\mathrm{(}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}}{\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{+}\mathrm{(}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}}$

$\mathrm{=}\frac{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{+}\mathrm{1}}$ .

The second binomial coefficient is the total number of $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{p}}_{\mathrm{1}}\mathrm{+}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{P}}_{\mathrm{1}}\mathrm{)}$-long

sequences of $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}$ crosses and $\mathrm{(}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}$ 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 ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$ , subject to the condition ${{E}}_{\mathit{s}\mathit{w}}$, is the product of two

counts, namely

18

${\mathrm{(}}_{{\mathit{l}}_{\mathrm{1}}}^{\mathit{n}\mathrm{/}\mathrm{2}}\mathrm{)}{\mathrm{(}}_{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{+}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}{\mathrm{(}}^{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{+}{\mathit{m}}_{\mathrm{2}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{)}\frac{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{+}\mathrm{1}}$

$\mathrm{=}\frac{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}{\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}{\mathrm{(}}_{{\mathit{m}}_{\mathrm{2}}}^{\mathit{n}\mathrm{/}\mathrm{2}}\mathrm{\left)}{\mathrm{(}}_{{\mathit{p}}_{\mathrm{1}}}^{{\mathit{m}}_{\mathrm{2}}}\mathrm{\right)}{\mathrm{(}}_{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{l}}_{\mathrm{1}}\mathrm{+}\mathrm{1}}^{\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}\mathrm{)}$

Suummmmirng this last expression over all ${\mathit{p}}_{\mathrm{1}}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{m}}_{\mathrm{2}}$, we obtain

$\frac{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}{\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}$ ${{\displaystyle \sum }}_{\mathrm{\le }{\mathit{m}}_{\mathrm{2}}}$

$\mathrm{=}\frac{{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}{\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}}$ (2.2)

$\mathrm{=}\frac{\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}\mathrm{)}}{\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{+}\mathrm{1}\mathrm{)}}$ .

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 $\mathit{n}\mathrm{/}\mathrm{2}$ rows, ${\mathit{m}}_{\mathrm{1}}$ to contain crosses and ${\mathit{m}}_{\mathrm{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 $\mathrm{\left(}\mathit{X}\mathrm{\right(}\mathit{t}\mathrm{)}\mathrm{,}\mathrm{}\mathit{Y}\mathrm{(}\mathit{t}\mathrm{)}{\mathrm{)}}_{\mathrm{0}\mathrm{\le }\mathit{t}\mathrm{\le }\mathit{n}\mathrm{/}\mathrm{2}}$ on the square lattice

connecting $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{}\mathrm{0}\mathrm{)}$ and $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{)}$ such that $\mathit{X}\mathrm{(}\mathit{t}\mathrm{+}\mathrm{1}\mathrm{)}$ $\mathrm{-}\mathit{X}\mathrm{\left(}\mathit{t}\mathrm{\right)}$, $\mathit{Y}\mathrm{(}\mathit{t}\mathrm{+}\mathrm{1}\mathrm{)}$ $\mathrm{-}\mathit{Y}\mathrm{\left(}\mathit{t}\mathrm{\right)}\mathrm{\in }\mathrm{\{}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{\}}$, and

$\mathit{X}\mathrm{\left(}\mathit{t}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{>}}\mathit{Y}\mathrm{\left(}\mathit{t}\mathrm{\right)}$ for every $\mathit{t}$. (To be sure, if $\mathit{X}\mathrm{(}\mathit{t}\mathrm{+}\mathrm{1}\mathrm{)}$ $\mathrm{-}\mathit{X}\mathrm{\left(}\mathit{t}\mathrm{\right)}\mathrm{=}\mathrm{1}$ and $\mathit{Y}\mathrm{(}\mathit{t}\mathrm{+}\mathrm{1}\mathrm{)}$ $\mathrm{-}\mathit{Y}\mathrm{\left(}\mathit{t}\mathrm{\right)}\mathrm{=}\mathrm{1}$,

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

Likewise, we consider the northeast corner, ${\mathit{M}}_{\mathit{n}\mathit{e}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$. We introduce ${\mathit{L}}_{\mathrm{2}}\mathrm{=}{\mathit{L}}_{\mathrm{2}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$,

the number of rows in ${\mathit{M}}_{\mathit{n}\mathit{e}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ containing both a cross and a ball. By initially

restricting to the event $\mathrm{\{}{\mathit{L}}_{\mathrm{2}}\mathrm{=}{\mathit{P}}_{\mathrm{2}}\mathrm{\}}$, then later summing over all ${\mathit{p}}_{\mathrm{2}}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{m}}_{\mathrm{2}}$, we obtain

19

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

sidering columns in the northwest and southeast corners, ${\mathit{M}}_{\mathit{n}\mathit{w}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ and ${\mathit{M}}_{\mathit{s}\mathit{e}}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$.

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 $\mathit{A}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{)}$ subject to all four restrictions defining ${E}\mathrm{!}$

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

and columns support the four submatrices of $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ and $\mathit{M}\mathrm{\left(}\mathit{\sigma }\mathrm{\right)}$. Consider, for instance,

the southwest corner of $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$. We have selected ${\mathit{m}}_{\mathrm{1}}$ rows (from the first $\mathit{n}\mathrm{/}\mathrm{2}$ rows)

supporting ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ , and we have selected ${\mathit{m}}_{\mathrm{3}}$ columns (from the first $\mathit{n}\mathrm{/}\mathrm{2}$ columns)

supporting ${\mathit{M}}_{\mathit{n}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$. Then it is the remaining $\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{3}}\mathrm{=}{\mathit{m}}_{\mathrm{1}}$ columns that support

${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$. The number of ways to match these ${\mathit{m}}_{\mathrm{1}}$ rows and ${\mathit{m}}_{\mathrm{1}}$ columns, thus to

determine ${\mathit{M}}_{\mathit{s}\mathit{w}}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ completely, is ${\mathit{m}}_{\mathrm{1}}\mathrm{!}$. The northeast corner contributes another ${\mathit{m}}_{\mathrm{1}}\mathrm{!}$,

while each of the two other corners contributes ${\mathit{m}}_{\mathrm{3}}\mathrm{!}$, whence the overall matching

factor is $\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{!}{\mathit{m}}_{\mathrm{3}}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}$. The matching factor for a is $\mathrm{(}{\mathit{m}}_{\mathrm{2}}\mathrm{!}{\mathit{m}}_{\mathrm{4}}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}$. Multiplying the number

of admissible row-column selections by the resulting ${{\displaystyle \prod }}_{\mathit{i}\mathrm{=}\mathrm{1}}^{\mathrm{4}}\mathrm{(}{\mathit{m}}_{\mathit{i}}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}$ and dividing by $\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}$,

we obtain

$\mathit{P}\mathrm{(}{E}\mathrm{\cap }\mathit{A}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{m}}_{\mathrm{2}}\mathrm{\left)}\mathrm{\right)}\mathrm{=}\mathrm{[}\frac{\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}\mathrm{)}}{\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}\mathrm{)}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{+}\mathrm{1}\mathrm{)}}$ ${\mathrm{]}}^{\mathrm{4}}$. $\frac{{{\displaystyle \prod }}_{\mathit{i}\mathrm{=}\mathrm{1}}^{\mathrm{4}}\mathrm{(}{\mathit{m}}_{\mathit{i}}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}}{\mathrm{(}\mathit{n}\mathrm{!}{\mathrm{)}}^{\mathrm{2}}}$,

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

factor. In it, we show the matrix $\mathit{M}\mathrm{\left(}\mathit{\pi }\mathrm{\right)}$ in a case when in the southwest and the

20

$\mathit{n}\mathrm{/}\mathrm{2}\mathrm{\text{"}}\mathrm{-}\mathit{m}$

$\mathrm{\left]}\mathrm{\right)}\mathit{m}$

$\mathit{m}\mathrm{(}$

${\mathrm{\setminus }}_{\mathrm{-}\mathrm{v}}\mathrm{\bigvee }$

$\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}\mathit{m}$

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

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

northeast squares $\mathit{\pi }$ is supported by the bottom $\mathit{m}\mathrm{(}\mathrm{=}{\mathit{m}}_{\mathrm{1}}\mathrm{)}$ and the top $\mathit{m}$ rows re-

spectively; likewise, in the northwest and the southeast squares $\mathit{\pi }$ is supported by the

$\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}\mathit{m}$ leftmost and the $\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}\mathit{m}$ rightmost columns respectively.

2.2 A Probabilistic Simplification

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

21

P $\mathrm{\left(}{E}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{E}\mathrm{[}\frac{\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{-}{\mathit{M}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}{\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{M}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}$

$\mathrm{(}\mathrm{‡}\mathrm{)}$

First, ${\mathit{M}}_{\mathrm{1}}$ and ${\mathit{M}}_{\mathrm{2}}$ are independent with

$\mathit{P}\mathrm{(}{\mathit{M}}_{\mathit{i}}\mathrm{=}{\mathit{m}}_{\mathit{i}}\mathrm{)}\mathrm{=}\frac{\left(\begin{array}{c}\mathit{n}\mathrm{/}\mathrm{2}\\ {\mathit{m}}_{\mathit{i}}\end{array}\right)}{{\mathrm{(}}_{\mathit{n}\mathrm{/}\mathrm{2}}^{\mathit{n}}\mathrm{)}}$, $\mathit{i}\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{2}$.

Indeed, ${\mathit{M}}_{\mathit{i}}$ obviously equals the cardinality of the intersection with $\mathrm{[}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{]}$ of a uni-

formly random subset of size $\mathit{n}\mathrm{/}\mathrm{2}$ from $\mathrm{\left[}\mathit{n}\mathrm{\right]}$, which directly implies these formulas.

Thus, each ${\mathit{M}}_{\mathit{i}}$ has the hypergeometric distribution with parameters $\mathit{n}\mathrm{/}\mathrm{2}$, $\mathit{n}\mathrm{/}\mathrm{2}$, $\mathit{n}\mathrm{/}\mathrm{2}$; in

other words, ${\mathit{M}}_{\mathit{i}}$ has the same distribution as the number of red balls in a uniformly

random sample of $\mathit{n}\mathrm{/}\mathrm{2}$ balls from an urn containing $\mathit{n}\mathrm{/}\mathrm{2}$ red balls and $\mathit{n}\mathrm{/}\mathrm{2}$ white balls.

By the independence of ${\mathit{M}}_{\mathrm{1}}$ and ${\mathit{M}}_{\mathrm{2}}$ , we obtain

$\mathit{P}\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{=}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{M}}_{\mathrm{2}}\mathrm{=}{\mathit{m}}_{\mathrm{2}}\mathrm{)}\mathrm{=}\frac{\left(\begin{array}{c}\mathit{n}\mathrm{/}\mathrm{2}\\ {\mathit{m}}_{\mathrm{1}}\end{array}\right)\left(\begin{array}{c}\mathit{n}\mathrm{/}\mathrm{2}\\ {\mathit{m}}_{\mathrm{2}}\end{array}\right)}{{\mathrm{(}}_{\mathit{n}\mathrm{/}\mathrm{2}}^{\mathit{n}}{\mathrm{)}}^{\mathrm{2}}}$ $\mathrm{2}$.

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

$\mathit{P}\mathrm{\left(}{E}\mathrm{\right)}\mathrm{=}{{\displaystyle \sum }}_{{\mathit{m}}_{\mathrm{1}}\mathrm{\ge }{\mathit{m}}_{\mathrm{2}}}\frac{\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}{\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}\mathrm{ċ}\mathit{P}\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{=}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{M}}_{\mathrm{2}}\mathrm{=}{\mathit{m}}_{\mathrm{2}}\mathrm{)}$

$\underset{\mathrm{‾}}{\mathrm{<}}{{\displaystyle \sum }}_{{\mathit{m}}_{\mathrm{1}}\mathrm{,}{\mathit{m}}_{\mathrm{2}}}\frac{\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}{\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{m}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}{\mathit{m}}_{\mathrm{1}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}\mathrm{ċ}\mathit{P}\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{=}{\mathit{m}}_{\mathrm{1}}\mathrm{,}\mathrm{}{\mathit{M}}_{\mathrm{2}}\mathrm{=}{\mathit{m}}_{\mathrm{2}}\mathrm{)}$

$\mathrm{=}\mathit{E}\mathrm{\left[}\frac{\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{-}{\mathit{M}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}{\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}{\mathit{M}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}}\mathrm{\right]}$,

and (‡) is proved.

22

2.3 Asymptotics

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

independence of the random variables ${\mathit{M}}_{\mathrm{1}}$ and ${\mathit{M}}_{\mathrm{2}}$. Typically the ${\mathit{M}}_{\mathit{i}}\mathrm{\text{'}}\mathrm{s}$ are close to

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

$\mathit{P}\mathrm{\left(}{E}\mathrm{\right)}\mathrm{=}\mathit{O}\mathrm{\left(}{\mathit{n}}^{\mathrm{-}\mathrm{2}}\mathrm{\right)}$.

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

pretation of ${\mathit{M}}_{\mathit{i}}$,

$\mathit{E}\mathrm{\left[}{\mathit{M}}_{\mathit{i}}\mathrm{\right]}\mathrm{=}\frac{\mathit{n}}{\mathrm{2}}\frac{\left(\begin{array}{c}\mathit{n}\mathrm{-}\mathrm{1}\\ \mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}\mathrm{1}\end{array}\right)}{{\mathrm{(}}_{\mathit{n}\mathrm{/}\mathrm{2}}^{\mathit{n}}\mathrm{)}}$ $\mathrm{=}\mathit{n}\mathrm{/}\mathrm{4}$. (2.3)

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

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

$\mathit{P}\mathrm{\left(}\mathrm{\right|}{\mathit{M}}_{\mathit{i}}\mathrm{-}\mathit{n}\mathrm{/}\mathrm{4}\mathrm{\left|}\underset{\mathrm{‾}}{\mathrm{>}}\mathit{t}\mathrm{\right)}\mathrm{=}\mathit{O}\mathrm{\left(}\exp \mathrm{\right(}\mathrm{-}\mathrm{4}{\mathit{t}}^{\mathrm{2}}\mathrm{/}\mathit{n}\mathrm{\left)}\mathrm{\right)}$ .

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

$\mathit{P}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{4}\mathrm{-}{\mathit{n}}^{\mathrm{2}\mathrm{/}\mathrm{3}}\mathrm{<}{\mathit{M}}_{\mathit{i}}\mathrm{<}\mathit{n}\mathrm{/}\mathrm{4}\mathrm{+}{\mathit{n}}^{\mathrm{2}\mathrm{/}\mathrm{3}}\mathrm{)}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{1}$ $\mathrm{-}{\mathit{e}}^{\mathrm{-}\mathit{c}{\mathit{n}}^{\mathrm{1}\mathrm{/}\mathrm{3}}}$,

for some absolute constant $\mathit{c}\mathrm{>}\mathrm{0}$. Introduce the event

${\mathit{A}}_{\mathit{n}}\mathrm{=}{\mathrm{\cap }}^{\mathrm{2}}\mathit{i}\mathrm{=}\mathrm{1}\mathrm{\{}\mathit{n}\mathrm{/}\mathrm{4}\mathrm{-}{\mathit{n}}^{\mathrm{2}\mathrm{/}\mathrm{3}}\mathrm{<}{\mathit{M}}_{\mathit{i}}\mathrm{<}\mathit{n}\mathrm{/}\mathrm{4}\mathrm{+}{\mathit{n}}^{\mathrm{2}\mathrm{/}\mathrm{3}}\mathrm{\}}$ .

Combining the estimates for ${\mathit{M}}_{\mathit{i}}$, we see that for some absolute constant ${\mathit{c}}_{\mathrm{1}}\mathrm{>}\mathrm{0}$,

$\mathit{P}\mathrm{\left(}{\mathit{A}}_{\mathit{n}}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{>}}\mathrm{1}$ $\mathrm{-}{\mathit{e}}^{\mathrm{-}{\mathit{c}}_{\mathrm{1}}{\mathit{n}}^{\mathrm{1}\mathrm{/}\mathrm{3}}}$

23

Now the random variable in (‡), call it ${\mathit{X}}_{\mathit{n}}$, is bounded by 1, and on the event ${\mathit{A}}_{\mathit{n}}$,

within a factor of $\mathrm{1}\mathrm{+}\mathit{O}\mathrm{\left(}{\mathit{n}}^{\mathrm{-}\mathrm{1}\mathrm{/}\mathrm{3}}\mathrm{\right)}$,

${\mathit{X}}_{\mathit{n}}\mathrm{=}\mathrm{\left(}\frac{\mathrm{4}}{\mathit{n}}{\mathrm{)}}^{\mathrm{8}}\mathrm{\right(}{\mathit{M}}_{\mathrm{1}}\mathrm{-}{\mathit{M}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}$

Therefore

$\mathit{P}\mathrm{\left(}{E}\mathrm{\right)}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{\left(}\frac{\mathrm{5}}{\mathit{n}}{\mathrm{)}}^{\mathrm{8}}\mathrm{\right(}\mathit{n}\mathrm{/}\mathrm{2}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathit{E}\mathrm{\left[}\mathrm{\right(}{\mathit{M}}_{\mathrm{1}}\mathrm{-}{\mathit{M}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{]}\mathrm{+}\mathit{O}\mathrm{(}{\mathit{e}}^{\mathrm{-}{\mathit{c}}_{\mathrm{1}}{\mathit{n}}^{\mathrm{1}\mathrm{/}\mathrm{3}}}\mathrm{)}$.

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

$\mathit{i}\mathrm{=}\mathrm{1}\mathrm{,}\mathrm{2}$. Then

$\mathrm{(}{\mathit{M}}_{\mathrm{1}}\mathrm{-}{\mathit{M}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{=}\mathrm{(}{\overline{\mathit{M}}}_{\mathrm{1}}\mathrm{-}{\overline{\mathit{M}}}_{\mathrm{2}}\mathrm{+}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{2}\mathrm{7}\mathrm{(}{\overline{\mathit{M}}}_{\mathrm{1}}^{\mathrm{4}}\mathrm{+}{\overline{\mathit{M}}}_{\mathrm{2}}^{\mathrm{4}}\mathrm{+}\mathrm{1}\mathrm{)}$,

as

$\mathrm{(}\mathit{a}\mathrm{+}\mathit{b}\mathrm{+}\mathit{c}{\mathrm{)}}^{\mathrm{2}}\underset{\mathrm{‾}}{\mathrm{<}}\mathrm{3}\mathrm{(}{\mathit{a}}^{\mathrm{2}}\mathrm{+}{\mathit{b}}^{\mathrm{2}}\mathrm{+}{\mathit{c}}^{\mathrm{2}}\mathrm{)}$.

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

order $\mathit{n}$ exactly. Indeed, extending the computation in (2.3),

$\mathit{E}\mathrm{\left[}{\mathit{M}}_{\mathit{i}}\mathrm{\right(}{\mathit{M}}_{\mathit{i}}\mathrm{-}\mathrm{1}\mathrm{\left)}\mathrm{\right]}\mathrm{=}\frac{\mathit{n}}{\mathrm{2}}\mathrm{(}\frac{\mathit{n}}{\mathrm{2}}\mathrm{-}\mathrm{1}\mathrm{)}$ $\frac{\left(\begin{array}{c}\mathit{n}\mathrm{-}\mathrm{2}\\ \mathit{n}\mathrm{/}\mathrm{2}\mathrm{-}\mathrm{2}\end{array}\right)}{{\mathrm{(}}_{\mathit{n}\mathrm{/}\mathrm{2}}^{\mathit{n}}\mathrm{)}}$

$\mathrm{=}\frac{\mathit{n}\mathrm{(}\mathit{n}\mathrm{-}\mathrm{2}{\mathrm{)}}^{\mathrm{2}}}{\mathrm{1}\mathrm{6}\mathrm{(}\mathit{n}\mathrm{-}\mathrm{1}\mathrm{)}}$.

Therefore

24

E $\mathrm{\left[}{\overline{\mathit{M}}}_{\mathit{i}}^{\mathrm{2}}\mathrm{\right]}\mathrm{=}\mathrm{V}\mathrm{a}\mathrm{r}\mathrm{\left[}{\mathit{M}}_{\mathit{i}}\mathrm{\right]}$

$\mathrm{=}\mathit{E}\mathrm{\left[}{\mathit{M}}_{\mathit{i}}\mathrm{\right(}{\mathit{M}}_{\mathit{i}}\mathrm{-}\mathrm{1}\mathrm{\left)}\mathrm{\right]}\mathrm{+}\mathit{E}\mathrm{\left[}{\mathit{M}}_{\mathit{i}}\mathrm{\right]}\mathrm{-}{\mathit{E}}^{\mathrm{2}}\mathrm{\left[}{\mathit{M}}_{\mathit{i}}\mathrm{\right]}$

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

$\mathrm{=}\frac{\mathit{n}}{\mathrm{1}\mathrm{6}}\mathrm{+}\mathit{O}\mathrm{\left(}\mathrm{1}\mathrm{\right)}$.

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

able, ${\mathit{M}}_{\mathit{i}}$ has the same distribution as the sum of $\mathit{n}\mathrm{/}\mathrm{2}$ independent Bernoulli variables

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

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

$\frac{{\overline{\mathit{M}}}_{\mathit{i}}}{\sqrt{\mathit{n}\mathrm{/}\mathrm{1}\mathrm{6}}}\mathrm{\to }\mathit{N}\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$, (2.5)

where $\mathit{N}\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$ is the standard normal random variable. In fact, since

$\frac{{\mathit{Y}}_{\mathit{j}}\mathrm{-}\mathit{E}\mathrm{\left[}{\mathit{Y}}_{\mathit{j}}\mathrm{\right]}}{\sqrt{\mathit{n}\mathrm{/}\mathrm{1}\mathrm{6}}}\mathrm{\to }\mathrm{0}$, $\mathit{n}$ $\mathrm{\to }\mathrm{\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{\mathit{E}\mathrm{\left[}{\overline{\mathit{M}}}_{\mathit{i}}^{\mathrm{4}}\mathrm{\right]}}{\mathrm{(}\sqrt{\mathit{n}\mathrm{/}\mathrm{1}\mathrm{6}}{\mathrm{)}}^{\mathrm{4}}}\mathrm{\to }\mathit{E}\mathrm{\left[}\mathit{N}\mathrm{\right(}\mathrm{0}\mathrm{,}\mathrm{1}{\mathrm{)}}^{\mathrm{4}}\mathrm{]}$, $\mathit{n}$ $\mathrm{\to }\mathrm{\infty }$,

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

$\mathrm{\square }$

25

(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 $\mathit{\epsilon }$ $\mathrm{>}\mathrm{0}$

$\mathit{P}\mathrm{\left(}\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }\mathrm{\right)}\mathrm{=}\mathrm{\Omega }\mathrm{\left(}\mathrm{\right(}\mathit{\alpha }\mathrm{-}\mathit{\epsilon }{\mathrm{)}}^{\mathit{n}}\mathrm{)}$,

where

$\mathrm{(}\mathit{y}$ $\mathrm{=}\mathrm{1}\sqrt[\mathrm{1}]{}\frac{\mathrm{2}\mathrm{5}\mathrm{4}\mathrm{9}\mathrm{7}\mathrm{9}\mathrm{3}\mathrm{8}\mathrm{8}\mathrm{5}\mathrm{1}\mathrm{3}\mathrm{2}\mathrm{4}\mathrm{2}\mathrm{1}\mathrm{3}\mathrm{3}\mathrm{3}\mathrm{5}}{\mathrm{2}\mathrm{2}\mathrm{!}}\mathrm{=}\mathrm{0}\mathrm{.}\mathrm{7}\mathrm{0}\mathrm{8}\mathrm{7}\mathrm{9}$ . . . .

First, some preliminaries.

3.1 A Sufficient Condition for Bruhat Comparability

Introduce ${\mathit{\pi }}^{\mathrm{*}}$ ( ${\mathit{\sigma }}^{\mathrm{*}}$ resp.), the permutation $\mathit{\pi }$ ( $\mathit{\sigma }$ resp.) with the element $\mathit{n}$ deleted.

More generally, for $\mathit{k}\underset{\mathrm{‾}}{\mathrm{<}}\mathit{n}$, ${\mathit{\pi }}^{\mathit{k}\mathrm{*}}$ ( ${\mathit{\sigma }}^{\mathit{k}\mathrm{*}}$ resp.) is the permutation of $\mathrm{[}\mathit{n}\mathrm{}\mathrm{-}\mathit{k}\mathrm{]}$ obtained from

$\mathit{\pi }$ ( $\mathit{\sigma }$ resp.) by deletion of the $\mathit{k}$ largest elements, $\mathit{n}$, $\mathit{n}$ $\mathrm{-}\mathrm{1}$, $\mathrm{\text{...}}$, $\mathit{n}$ $\mathrm{-}\mathit{k}\mathrm{+}\mathrm{1}$. The key to

the proof is the following:

26

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

Lemma 3.1.1. Let k $\mathrm{\in }\mathrm{\left[}\mathit{n}\mathrm{\right]}$. If every northeastern submatrix of $\mathit{M}\mathrm{(}\mathit{\pi }\mathrm{,}\mathrm{}\mathit{\sigma }\mathrm{)}$ with at most

k rows contains at least as many crosses as balls, and ${\mathit{\pi }}^{\mathit{k}\mathrm{*}}\underset{\mathrm{‾}}{\mathrm{<}}{\mathit{\sigma }}^{\mathit{k}\mathrm{*}}$, then $\mathit{\pi }\underset{\mathrm{‾}}{\mathrm{<}}\mathit{\sigma }$.