Probabilistic methods in combinatorics. (English) Zbl 0308.05001

Erdős, Paul; Spencer, Joel

Budapest: Akademiai Kiado. 106 p. Ft 70.00 (1974).

One way to show the existence of an object with a property \(P\) is by construction. Another way is to show that the probability that objects in some set have property \(P\) is positive. For example, if the expected value of some integer-valued parameter \(f(x)\) is less than one, then it follows that there exists an object \(x\) for which \(f(x)=0\). The purely probabilistic aspects of such arguments are often fairly simple; but obtaining estimates for the probabilities involved may or may not be so simple. This “probabilistic method” is important because in many different problems it has yielded results that are as good or better than have been obtained by other methods. This monograph is a collection of such applications to, among other things, sets with property \(B\), subtournaments of a tournament, the chromatic number of a graph, asymmetric graphs, random graphs, Zarankiewicz’s problem, and problems related to theorems of Ramsey, van der Waerden, and Turán.

Reviewer: J.W.Moon

MSC:

05-XX	Combinatorics
60C05	Combinatorial probability
05A99	Enumerative combinatorics
05Cxx	Graph theory
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics