CSC 2427, Topics in Graph Theory:  The Probabilistic Method.

The probabilistic method is one of the most important proof techniques 
in combinatorics.
Generally speaking, it involves novel applications of probability theory to prove
theorems which, on the surface, do not appear to have anything to do with
probability.  This method was pioneered by Erdos in the 1940's when
he proved the existence of graphs with certain properties by showing that
a randomly constructed graph would have those properties with positive 
probability.  

This course will provide an introduction to the basic tools of the
probabilistic method, including: the first moment method, the second moment
method, the Lovasz Local Lemma, concentration bounds and the semi-random method,
along with algorithmic aspects of these tools. We will also present
some of the more important applications of the technique.

Prerequisite:  
A basic background in graph theory, such as that provided by CSC 2410.

Grading Scheme:  

Assignments - 50% 
Project (format to be announced) - 50%