zbMATH — the first resource for mathematics

Ten lectures on the probabilistic method. (English) Zbl 0703.05046
CBMS-NSF Regional Conference Series in Applied Mathematics 52. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-213-0). vi, 78 p. (1987).
This monograph comes from the notes of a series of ten lectures given by Joel Spencer at the CBMS-NSF Conference on Probabilistic Methods in Combinatorics at Durango, Colorado in July of 1986. Quite naturally, the book has ten sections corresponding to each of the lectures. The author states “In writing this monograph I have attempted to remain close to the content, order and spirit of the lectures”. This objective was attained, for the writing style is informal and consistent with the causal form of the lectures. In some sections addendums are added to cover topics not touched upon in the lectures.
The first section introduces the probabilistic methods with some well chosen examples. Examples from classical Ramsey theory and ranks in tournaments are considered. The emphasis is placed on the method and not the technical details. Special care is taken to give the reader a feel for doing those calculations necessary to use the probabilistic method. This is the strength of this section. Crude approximations are used, and then followed by a more careful analysis. The second section continues with the same topics, but at a more sophisticated level. Deletion techniques and other refinements are introduced. These two sections are excellent reading for someone who is not familiar with probabilistic techniques, but is interested in learning something about them.
Various models for random graphs are introduced in the third section, and a more in depth treatment of random graphs is continued in section seven. The nature of classical graphical properties such as connectivity and planarity are discussed, and the threshold functions associated with these graphical properties are investigated.
In section four some algorithms and games - in particular the pusher and chooser game - are analyzed using probabilistic methods. The now fashionable topic discrepancy arises quite naturally in this process. The general topic of discrepancy is considered in sections five and nine, where various forms of discrepancy are introduced and the relationships between them investigated. The sections are laced with enlightening examples. Most of section nine is devoted to the Beck-Fiala theorem, which gives a bound on the discrepancy of a family of sets in terms of the maximal degree of the set system. The Gale-Berlekamp switching game is touched upon in section six, along with edge discrepancy and a revisiting of tournament ranking.
No series of lectures on probabilistic methods would be complete without considering the Lovasz Local Lemma. A nice treatment of these Lemma appears in section eight. This result, which is very useful in dealing with events in which there is minimal dependence, is applied to some classical problems in Ramsey theory - in particular to graphical Ramsey numbers and van der Waerden numbers.
The last section appropriately entitled “Six Standard Deviations Suffice” is devoted to a proof of the following result: If \(S_ 1,S_ 2,...,S_ n\subset [n]\), then there exists a \(\chi\) :[n]\(\to \{0,1\}\) such that \(| \chi (A_ i| <6n^{1/2}\), for all i.
Reviewer: R.Faudree

05C80 Random graphs (graph-theoretic aspects)