Preface

Summary

Combinatorics played an important role in the development of probability theory and the two have continued to be closely related. Now probability theory, by offering new approaches to problems of discrete mathematics, is beginning to repay its debt to combinatorics. Among these new approaches, the methods of asymptotic analysis, which have been well developed in probability theory, can be used to solve certain complicated combinatorial problems.

If the uniform distribution is defined on the set of combinatorial structures in question, then the numerical characteristics of the structures can be regarded as random variables and analyzed by probabilistic methods. By using the probabilistic approach, we restrict our attention to “typical” structures that constitute the bulk of the set, excluding the small fraction with exceptional properties.

The probabilistic approach that is now widely used in combinatorics was first formulated by V. L. Goncharov, who applied it to S_n, the set of all permutations of degree n, and to the runs in random (0,1)-sequences. S. N. Bernstein, N. V. Smirnov, and V. E. Stepanov were among those who developed probabilistic combinatorics in Russia, building on the famous Russian school of probability founded by A. A. Markov, P. L. Lyapunov, A. Ya. Khinchin, and A. N. Kolmogorov.

This book is based on results obtained primarily by Russian mathematicians and presents results on random graphs, systems of random linear equations in GF(2), random permutations, and some simple equations involving permutations.