MATH 585

Credit: 4 hours.

Techniques and applications of probabilistic methods in combinatorics. Draws applications from a variety of areas, but emphasizes theoretical aspects of random graphs, including connectivity, trees & cycles, planarity, and coloring problems. Techniques include the second moment method, Lovasz Local Lemma, martingales, Talgrand's Inequality, the Rodl Nibble, and Szemeredi's Regularity Lemma. Applications may come from discrete geometry, coding theory, algorithms & complexity, additive number theory, percolation, positional games, etc.

Prerequisite: MATH 580 or consent of instructor.