Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 308.05001
Autor: Erdös, Paul; Spencer, Joel
Title: Probabilistic methods in combinatorics. (In English)
Source: Budapest: Akademiai Kiado. 106 p. Ft 70.00 (1974).
Review: 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, asyummetric graphs, random graphs, Zarankiewicz's problem, and problems related to theorems of Ramsey, van der Waerden, and Turán.
Reviewer: J.W.Moon
Classif.: * 05-XX Combinatorics
60C05 Combinatorial probability
05A99 Classical combinatorial problems
05Cxx Graph theory
05-02 Research monographs (combinatorics)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag