The Probabilistic Method and A Classical Result of Erdos

Sasha Fradkin, Princeton University
Fine Hall 214

The basic idea behind the 'probabilistic method' in combinatorics is as follows: in order to prove the existence of an object with a certain property, one defines an appropriate (non-empty) probability space and shows that a randomly chosen object from this space has the desired property with positive probability. This simple idea (with a few variations) has been applied to prove many beautiful and sometimes surprising results in combinatorics. I will mostly focus on just one such classical result, namely the theorem of Erdos showing that there exist graphs with arbitrarily large girth and arbitrarily large chromatic number. No previous knowledge of graph theory will be assumed.