The elements of many classical combinatorial structures can be naturally decomposed into components. Permutations can be decomposed into cycles, polynomials over a finite field into irreducible factors, mappings into connected components. In all of these examples, and in many more, there are strong similarities between the numbers of components of different sizes that are found in the decompositions of `typical' elements of large size. For instance, the total number of components grows logarithmically with the size of the element, and the size of the largest component is an appreciable fraction of the whole. This book explains the similarities in asymptotic behaviour as the result of two basic properties shared by the structures: the conditioning relation and the logarithmic condition. The discussion is conducted in the language of probability, enabling the theory to be developed under rather general and explicit conditions; for the finer conclusions, Stein's method emerges as the key ingredient. The book is thus of particular interest to graduate students and researchers in both combinatorics and probability theory.
Author(s): Richard Arratia, Simon Tavaré, A. D. Barbour
Series: EMS Monographs in Mathematics
Publisher: European Mathematical Society
Year: 2003
Language: English
Pages: 375
Contents......Page 9
0 Preface......Page 13
1.1 Random permutations and their cycles......Page 21
1.2 Random integers and their prime factors......Page 39
1.3 Contrasts between permutations and primes......Page 44
2 Decomposable Combinatorial Structures......Page 47
2.1 Some combinatorial examples......Page 48
2.2 Assemblies, multisets and selections......Page 57
2.3 The probabilistic perspective......Page 60
2.4 Refining and coloring......Page 65
2.5 Tilting......Page 70
3 Probabilistic Preliminaries......Page 77
3.1 Total variation and Wasserstein distances......Page 79
3.2 Rates of convergence......Page 80
3.3 Results for classical logarithmic structures......Page 82
3.4 Stein’s method......Page 85
4 The Ewens Sampling Formula: Methods......Page 89
4.1 Size-biasing......Page 90
4.2 The limiting random variable X_theta......Page 92
4.3 The limiting random variable X_θ^{(α)}......Page 97
4.4 Point probabilities for T_{bn}......Page 101
5 The Ewens Sampling Formula: Asymptotics......Page 107
5.1 Weak laws for small cycles......Page 108
5.2 The number of cycles......Page 112
5.3 The shortest cycles......Page 116
5.4 The ordered cycles......Page 118
5.5 The largest cycles......Page 120
5.6 The Erdös–Turán Law......Page 127
5.7 The Poisson–Dirichlet and GEM distributions......Page 129
6.1 Results for general logarithmic structures......Page 137
6.2 Verifying the local limit conditions......Page 150
6.3 Refinements and extensions......Page 159
7.1 Strategy......Page 161
7.2 Basic framework......Page 165
7.3 Working conditions......Page 167
7.4 Tilting......Page 172
7.5 d-fractions......Page 175
7.6 Illustrations......Page 176
7.7 Main theorems......Page 177
8.1 Functional central limit theorems......Page 183
8.2 Poisson–Dirichlet limits......Page 187
8.3 The number of components......Page 198
8.4 Erdös–Turán laws......Page 211
8.5 Additive function theory......Page 212
9.1 Stein’s method for T_{0m}(Z*)......Page 237
9.2 Stein’s method for P_θ......Page 242
9.3 Applying Stein’s method......Page 246
10.1 Bounds on individual probabilities......Page 251
10.2 Differences of point probabilities......Page 259
11.1 Comparison of L(T_{vm}(Z)) and L(T_{vm}(Z*))......Page 279
11.2 Comparing L(m^{−1}T_{vm}(Z*)) with P_θ......Page 289
11.3 Comparing L(m^{−1}T_{vm}(Z*)) with P_θ^{(α)}......Page 294
12.1 Local limit theorems for T_{vm}(Z)......Page 297
12.2 Comparison of T_{vm}(Z) with
T_{vm}(Z*): point probabilities......Page 300
12.3 Comparison with p_θ......Page 309
13.1 Proof of Theorem 7.6......Page 313
13.2 Proof of Theorem 7.7......Page 314
13.3 Proof of Theorem 7.8......Page 316
13.4 Proof of Theorem 7.9......Page 319
13.5 Proof of Theorem 7.10......Page 322
13.6 Proof of Theorem 7.11......Page 324
13.7 Proof of Theorem 7.12......Page 325
13.8 Proof of Theorem 7.13......Page 326
13.9 Proof of Theorem 7.14......Page 331
13.10 Proof of Theorem 8.10......Page 335
14 Technical Complements......Page 341
References......Page 351
Notation Index......Page 365
Author Index......Page 367
Subject Index......Page 371
