Lesson 1

The probabilistic method is a powerful method in discrete mathematics, whose essence, very roughly, is as follows: to prove that an object with a certain property exists, we show that a randomly chosen object has the given property with nonzero probability. This results in a non-constructive existence proof: we establish the existence of the object without explicitly constructing it. Many important and beautiful results in this field were obtained by Paul Erdős.