The Probabilistic Method Part 1

Say you have a finite class of objects (e.g., graphs of a fixed size), and you wish to show that some property holds for at least one of them. A heuristic approach to this question is to consider whether a randomly chosen object is "likely enough" to have the property. In some cases, this heuristic leads to actual proofs.

This method (due largely to Paul Erdos) is best learned by example. In my talk, I will focus on applications to graph theory; a sequel later this semester will present a more eclectic range of applications. This talk will gleefully violate the maxim that a good math talk should include at most one proof.