Random Trees: An Interplay Between Combinatorics and Probability Book

1 Classes of Random Trees 1

1.1 Basic Notions 2

1.1.1 Rooted Versus Unrooted trees 2

1.1.2 Plane Versus Non-Plane trees 3

1.1.3 Labelled Versus Unlabelled Trees 3

1.2 Combinatorial Trees 4

1.2.1 Binary Trees 5

1.2.2 Planted Plane Trees 6

1.2.3 Labelled Trees 7

1.2.4 Labelled Plane Trees 8

1.2.5 Unlabelled Trees 8

1.2.6 Unlabelled Plane Trees 9

1.2.7 Simply Generated Trees - Galton-Watson Trees 9

1.3 Recursive Trees 13

1.3.1 Non-Plane Recursive Trees 13

1.3.2 Plane Oriented Recursive Trees 14

1.3.3 Increasing Trees 15

1.4 Search Trees 17

1.4.1 Binary Search Trees 18

1.4.2 Fringe Balanced m-Ary Search Trees 19

1.4.3 Digital Search Trees 21

1.4.4 Tries 22

2 Generating Functions 25

2.1 Counting with Generating Functions 26

2.1.1 Generating Functions and Combinatorial Constructions 27

2.1.2 Pólya's Theory of Counting 33

2.1.3 Lagrange Inversion Formula 36

2.2 Asymptotics with Generating Functions 37

2.2.1 Asymptotic Transfers 38

2.2.2 Functional Equations 43

2.2.3 Asymptotic Normality and Functional Equations 46

2.2.4 Transfer of Singularities 54

2.2.5 Systems of Functional Equations 62

3 Advanced Tree Counting 69

3.1 Generating Functions and Combinatorial Trees 70

3.1.1 Binary and m-ary Trees 70

3.1.2 Planted Plane Trees 71

3.1.3 Labelled Trees 73

3.1.4 Simply Generated Trees - Galton-Watson Trees 75

3.1.5 Unrooted Trees 77

3.1.6 Trees Embedded in the Plane 81

3.2 Additive Parameters in Trees 82

3.2.1 Simply Generated Trees - Galton-Watson Trees 84

3.2.2 Unrooted Trees 87

3.3 Patterns in Trees 90

3.3.1 Planted, Rooted and Unrooted Trees 91

3.3.2 Generating Functions for Planted Rooted Trees92

3.3.3 Rooted and Unrooted Trees 99

3.3.4 Asymptotic Behaviour 101

4 The Shape of Galton-Watson Trees and Pólya Trees 107

4.1 The Continuum Random Tree 108

4.1.1 Depth-First Search of a Rooted Tree 108

4.1.2 Real Trees 109

4.1.3 Galton-Watson Trees and the Continuum Random Tree 111

4.2 The Profile of Galton-Watson Trees 115

4.2.1 The Distribution of the Local Time 118

4.2.2 Weak Convergence of Continuous Stochastic Processes 120

4.2.3 Combinatorics on the Profile of Galton-Watson Trees 125

4.2.4 Asymptotic Analysis of the Main Recurrence 126

4.2.5 Finite Dimensional Limiting Distributions 129

4.2.6 Tightness 134

4.2.7 The Height of Galton-Watson Trees 139

4.2.8 Depth-First Search 149

4.3 The Profile of Pólya Trees 154

4.3.1 Combinatorial Setup 154

4.3.2 Asymptotic Analysis of the Main Recurrence 156

4.3.3 Finite Dimensional Limiting Distributions 164

4.3.4 Tightness 168

4.3.5 The Height of Pólya Trees 177

5 The Vertical Profile of Trees 187

5.1 Quadrangulations and Embedded Trees 188

5.2 Profiles of Trees and Random Measures 196

5.2.1 General Profiles 196

5.2.2 Space Embedded Trees and ISE 196

5.2.3 The Distribution of the ISE 204

5.3 Combinatorics on Embedded Trees 207

5.3.1 Embedded Trees with Increments &plus,minus; 207

5.3.2 Embedded Trees with Increments 0, &plus,minus;1 214

5.3.3 Naturally Embedded Binary Trees 216

5.4 Asymptotics on Embedded Trees 219

5.4.1 Trees with Small Labels 219

5.4.2 The Number of Nodes of Given Label 225

5.4.3 The Number of Nodes of Large Labels 229

5.4.4 Embedded Trees with Increments 0 and &plus,minus;1 235

5.4.5 Naturally Embedded Binary Trees 235

6 Recursive Trees and Binary Search Trees 237

6.1 Permutations and Trees 238

6.1.1 Permutations and Recursive Trees 239

6.1.2 Permutations and Binary Search Trees 246

6.2 Generating Functions and Basic Statistics 247

6.2.1 Generating Functions for Recursive Trees 248

6.2.2 Generating Functions for Binary Search Trees 249

6.2.3 Generating Functions for Plane Oriented Recursive Trees 251

6.2.4 The Degree Distribution of Recursive Trees 253

6.2.5 The Insertion Depth 262

6.3 The Profile of Recursive Trees 265

6.3.1 The Martingale Method 266

6.3.2 The Moment Method 275

6.3.3 The Contraction Method 278

6.4 The Height of Recursive Trees 280

6.5 Profile and Height of Binary Search Trees and Related Trees 291

6.5.1 The Profile of Binary Search Trees and Related Trees 291

6.5.2 The Height of Binary Search Trees and Related Trees 300

7 Tries and Digital Search Trees 307

7.1 The Profile of Tries 308

7.1.1 Generating Functions for the Profile 308

7.1.2 The Expected Profile of Tries 311

7.1.3 The Limiting Distribution of the Profile of Tries 321

7.1.4 The Height of Tries 323

7.1.5 Symmetric Tries 324

7.2 The Profile of Digital Search Trees 325

7.2.1 Generating Functions for the Profile 325

7.2.2 The Expected Profile of Digital Search Trees 327

7.2.3 Symmetric Digital Search Trees 337

8 Recursive Algorithms and the Contraction Method 343

8.1 The Number of Comparisons in Quicksort 345

8.2 The L2 Setting of the Contraction Method 350

8.2.1 A General Type of Recurrence 350

8.2.2 A General L2 Convergence Theorem 352

8.2.3 Applications of the L2 Setting 357

8.3 Limitations of the L2 Setting and Extensions 361

8.3.1 The Zolotarev Metric 362

8.3.2 Degenerate Limit Equations 363

9 Planar Graphs 365

9.1 Basic Notions 366

9.2 Counting Planar Graphs 368

9.2.1 Outerplanar Graphs 368

9.2.2 Series-Parallel Graphs 376

9.2.3 Quadrangulations and Planar Maps 382

9.2.4 Planar Graphs 389

9.3 Outerplanar Graphs 396

9.3.1 The Degree Distribution of Outerplanar Graphs 396

9.3.2 Vertices of Given Degree in Dissections 400

9.3.3 Vertices of Given Degree in 2-Connected Outerplanar Graphs 404

9.3.4 Vertices of Given Degree in Connected Outerplanar Graphs 406

9.4 Series-Parallel Graphs 408

9.4.1 The Degree Distribution of Series-Parallel Graphs 408

9.4.2 Vertices of Given Degree in Series-Parallel Networks 415

9.4.3 Vertices of Given Degree in 2-Connected Series-Parallel Graphs 416

9.4.4 Vertices of Given Degree in Connected Series-Parallel Graphs 419

9.5 All Planar Graphs 420

9.5.1 The Degree of a Rooted Vertex 421

9.5.2 Singular Expansions 425

9.5.3 Degree Distribution for Planar Graphs 429

9.5.4 Vertices of Degree 1 or 2 in Planar Graphs 433

Appendix 439

References 445

Index 455