Description

The probabilistic method is a modern proof technique in combinatorics,  which is nonconstructive. Instead of constructing a combinatorial structure with the desired properties, instead it is shown that in an appropriate probability space of combinatorial structures, the desired properties hold with positive probability. This technique was popularized by Erdös in the 1940s and is still producing excellent (and often “best possible”) results today.
This proof technique is applicable to all aspects of combinatorics, and is used extensively in graph theory, designs, and enumeration. It is an excellent method for bounding combinatorial parameters such as chromatic number and Ramsey number, and also lends itself to the design of efficient algorithms for creating combinatorial objects.

Prerequirements

This graduate special topics course is designed for those students who have completed a graduate course in a combinatorial course such graph theory, combinatorial designs, or enumeration (Math-6340, Math-6341, or Math-6342).

References

• Noga Alon, Joel H. Spencer, 2000, The probabilistic method, Wiley.
• Joel H. Spencer, 1994, Ten lectures on the probablistic method, SIAM.
• Michael S. Molloy, Bruce A. Reed, 2002, Graph colouring and the probabilistic method, Springer.