Probabilistic methods in combinatorics.

*(English)*Zbl 0308.05001
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