Spencer G22.3033-006 Random Graphs Tu 5-6:50 wwh 513
Special Topics: Random Graphs
Description: Equally appropriate titles would have been "Probabilistic
Combinatorics" or "The Probabilistic Method" or (personal favorite)
The Probabilistic Method is a lasting legacy of
the late Paul Erdos. For "Uncle Paul" the purpose was to prove
the existence of a graph, coloring, tournament, or other combinatorial
object. A random object would be described, and then one would
show that that object had the desired properties with positive probability.
Today we are very interested in algorithmic implementation, both
deterministically and with random algorithms. There is further great
interest (the official title) in the study of random discrete structures
(not just graphs, though that is the main one) for their own sake.
The course involves probability, Discrete Math, and algorithms.
Probability results include Chernoff Bounds, Martingales, the
Lovasz Local Lemma and the Janson Inequalities and will
be derived from scratch. Topics include: Ramsey Numbers, Continuous
Time Greedy Algorithms, Graph Coloring, Discrepancy, the Liar
Game and the Tenure Game.
Prerequisites: Only that elusive "mathematical maturity." This
topic takes from several areas but the material will be developed in
the course. An acquaintance with, say, variance (in probability) and/or
chromatic number (in graph theory) will be helpful but not mandatory.
Text: Noga Alon, Joel Spencer,
The Probabilistic Method, second edition
publisher: John Wiley, 2000
More Info: Contact Prof Spencer directly at
or check out his website:
and click on The Probabilistic Method under Topics.