Paul Erdős and the Probabilistic Method

The Probabilistic Method is one of the most significant contributions of Paul Erdős. Indeed, Paul himself said, during his 80th birthday conference in Keszthely, Hungary, that he believes the method will live long after him. This has been the only time I have heard him making any comment about the significance and impact of his work. He has always been more interested in discussing new problems and results than in trying to assess their long time expected merits. The method is a powerful technique with numerous applications in Combinatorics, Graph theory, Additive Number Theory and Geometry. The basic idea is very simple: Trying to prove that a structure with certain desired properties exists, one defines an appropriate probability space of structures and then shows that the desired properties hold in this space with positive probability. The amazing fact is that this simple reasoning can lead to highly nontrivial results. The results and tools are far too numerous to cover in a few pages, and my aim here is only to give a glimpse of the topic by describing a few examples of questions and results that illustrate the method. All of these have been initiated by Erdős, motivated by his questions and results. The fact that there is still an intensive ongoing work on all illustrates the influence and long term impact of his work. More material on the subject can be found in the books [6], [8], [23], [26]