The book is devoted to the study of classical combinatorial structures such as random graphs, permutations, and systems of random linear equations in finite fields. The author shows how the application of the generalized scheme of allocation in the study of random graphs and permutations reduces the combinatorial problems to classical problems of probability theory on the summation of independent random variables. He offers recent research by Russian mathematicians, including a discussion of equations containing an unknown permutation, and the first English-language presentation of techniques for solving systems of random linear equations in finite fields. These new results will interest specialists in combinatorics and probability theory and will also be useful to researchers in applied areas of probabilistic combinatorics such as communication theory, cryptology, and mathematical genetics.
Author(s): V. F. Kolchin
Year: 1998
Language: English
Pages: 268
Tags: Математика;Дискретная математика;Теория графов;
Cover......Page 1
Title......Page 6
Copyright......Page 7
CONTENTS ......Page 8
Preface ......Page 10
1.1 The probabilistic approach to enumerative combinatorial problems ......Page 14
1.2 The generalized scheme of allocation ......Page 27
1.3 Connectivity of graphs and the generalized scheme ......Page 35
1.4 Forests of nonrooted trees ......Page 43
1.5 Trees of given sizes in a random forest ......Page 55
1.6 Maximum size of trees in a random forest ......Page 61
1.7 Graphs with unicyclic components ......Page 71
1.8 Graphs with components of two types ......Page 83
1.9 Notes and references ......Page 99
2.1 Subcritical graphs ......Page 104
2.2 Critical graphs ......Page 110
2.3 Random graphs with independent edges ......Page 113
2.4 Nonequiprobable graphs ......Page 122
2.5 Notes and references ......Page 133
3.1 Rank of a matrix and critical sets ......Page 135
3.2 Matrices with independent elements ......Page 139
3.3 Rank of sparse matrices ......Page 148
3.4 Cycles and consistency of systems of random equations ......Page 156
3.5 Hypercycles and consistency of systems of random equations ......Page 169
3.6 Reconstructing the true solution ......Page 177
3.7 Notes and references ......Page 190
4.1 Random permutations and the generalized scheme of allocation ......Page 194
4.2 The number of cycles ......Page 196
4.3 Permutations with restrictions on cycle lengths ......Page 205
4.4 Notes and references ......Page 225
5.1 A quadratic equation ......Page 232
5.2 Equations of prime degree ......Page 238
5.3 Equations of compound degree ......Page 248
5.4 Notes and references ......Page 252
Bibliography ......Page 254
Index ......Page 264
