Random Mappings, 1986, 224 pp., ISBN 0-911575-16-2, $88.00
Presents basic results on random substitutions, graphs,
trees, forests, and mappings of finite sets generally, by the technique
pioneered by the author: by using the representation in terms of independent
random variables and exploiting the similarity to particle allocation schemes.
Of potential value in solving combinatorial problems of Computer Science.
Includes many results for the first time. Foreword by S.R.S. Varadhan.
TABLE OF CONTENTS
Foreword ..... ix
Preface ..... xi
CHAPTER 1. THE GENERAL SCHEME OF ALLOCATING PARTICLES
AND RANDOM MAPPINGS ..... 1
1.1. Probabilistic Approach to Enumerative Problems of Combinatorics ..... 3
1.2. The General Scheme of Allocation and Polynomial Distribution ..... 7
1.3. Reduction of Combinatorial Problem to the General Scheme of Allocation: Examples ..... 12
1.4. Local Limit Theorems ..... 15
1.5. Multiplicity of Vertices in a Random Mapping ..... 19
1.6. Connectivity of Graphs and the General Scheme of Allocation ..... 26
1.7. The General Scheme of Allocation and Random Substitutions ..... 35
1.8. Properties of the Logarithmic Distribution ..... 37
1.9. Cycles of a Random Substitution ..... 45
1.10. Linear Combinations of Lengths of Cycles ..... 50
1.11. Order of a Random Substitution ..... 59
1.12. Components of a Random Mapping and the General Scheme of Allocation ..... 72
1.13. The Order Sequence of Components of a Random Mapping ..... 80
1.14. Notes and References ..... 88
CHAPTER 2. BRANCHING PROCESSES AND RANDOM TREES ..... 95
2.1. Branching Processes ..... 97
2.2. Relationship of Branching Processes and Random Trees ..... 107
2.3. Limit Theorems for Conditional Distributions of a Critical Branching Process ..... 112
2.4. Conditional Distribution of the Moment of Extinction of a Critical Branching Process ..... 119
2.5. Limit Distributions of Characteristics of a Random Tree ..... 135
2.6. Notes and References ..... 143
CHAPTER 3. RANDOM FORESTS AND RANDOM MAPPINGS ..... 147
3.1. Relationship of Forests and Mappings ..... 149
3.2. Sizes of Trees in a Random Mapping ..... 154
3.3. Maximal Size of Trees in a Random Mapping ..... 165
3.4. Branching Processes and Random Forests ..... 171
3.5. Height of a Random Mapping ..... 177
3.6. Notes and References ..... 187
References ..... 199
Index ..... 205
Transliteration Table (Russian-English) ..... 207
List of OSI Publications (cont.) ..... 208