**Proceedings of Symposia in Applied Mathematics**

Volume: 44;
1991;
196 pp;
Hardcover

MSC: Primary 05; 68; 60;
Secondary 52

**Print ISBN: 978-0-8218-5500-3
Product Code: PSAPM/44**

List Price: $58.00

AMS Member Price: $46.40

MAA Member Price: $52.20

**Electronic ISBN: 978-0-8218-9259-6
Product Code: PSAPM/44.E**

List Price: $54.00

AMS Member Price: $43.20

MAA Member Price: $48.60

# Probabilistic Combinatorics and Its Applications

Share this page *Edited by *
*Béla Bollobás*

Probabilistic methods have become a vital tool in the
arsenal of every combinatorialist. The theory of random graphs is still
a prime area for the use of probabilistic methods, and, over the
years, these methods have also proved of paramount importance in
many associated areas such as the design and analysis of
computer algorithms. In recent years, probabilistic combinatorics has
undergone revolutionary changes as the result of the appearance of some
exciting new techniques such as martingale inequalities, discrete
isoperimetric inequalities, Fourier analysis on groups, eigenvalue
techniques, branching processes, and rapidly mixing Markov chains. The
aim of this volume is to review briefly the classical results in the
theory of random graphs and to present several of the important
recent developments in probabilistic combinatorics, together with
some applications.

The first paper contains a brief introduction to the theory of random
graphs. The second paper reviews explicit constructions of random-like
graphs and discusses graphs having a variety of useful properties.
Isoperimetric inequalities, of paramount importance in probabilistic
combinatorics, are covered in the third paper. The chromatic number of
random graphs is presented in the fourth paper, together with a
beautiful inequality due to Janson and the important and powerful
Stein-Chen method for Poisson approximation. The aim of the fifth paper
is to present a number of powerful new methods for proving that a Markov
chain is “rapidly mixing” and to survey various related
questions, while the sixth paper looks at the same topic in a very
different context. For the random walk on the cube, the convergence to
the stable distribution is best analyzed through Fourier analysis; the
final paper examines this topic and proceeds to several more
sophisticated applications. Open problems can be found throughout each
paper.

# Table of Contents

## Probabilistic Combinatorics and Its Applications

- Table of Contents xi12 free
- Preface xiii14 free
- Random Graphs 118 free
- Constructing Random-Like Graphs 2138
- Discrete Isoperimetric Inequalities 5774
- Random Graphs Revisited 8198
- Rapidly Mixing Markov Chains 99116
- Computing the Volume of Convex Bodies: A Case Where Randomness Provably Helps 123140
- Finite Fourier Methods: Access to Tools 171188
- Index 195212