Math 262A
Topics in Combinatorics
Fall, 2000
Lecturer: Professor Fan Chung Graham
Time: MW 2:30-3:50pm
Place: APM 4218
This course is an introduction to
combinatorial probabilistic methods,
pioneered by Professor Paul Erdös.
We will cover both the classical approaches and modern tools.
Topics include the basic methods, random graphs, discrepancy,
large deviations, derandomization, the Janson inequality,
the Lovasz local lemma and its recent algorithmic implementations.
Many powerful techniques here are the basis for
further study in randomized algorithms, computational biology
and Internet computing.
We will use the neat (and small) book "Ten Lectures on the Probabilistic
Methods" by Joel Spencer, supplemented by a second book "The Probabilistic
Methods" by Noga Alon and Joel Spencer.
The midterm take home. (Please note a correction in the hint for Problem 2.)
Solutions for the midterm.
Solutions for the final.
Some exercises on large deviations.
A paper by Gowers that was mentioned in class.