Probabilistic Methods in Combinatorics

Course Number: 
Hours - Lecture: 
Hours - Lab: 
Hours - Recitation: 
Hours - Total Credit: 
Typical Scheduling: 
Every Spring Semester

Applications of probabilistic techniques in discrete mathematics, including classical ideas using expectation and variance as well as modern tools, such as martingale and correlation inequalities.


MATH 4022 and MATH 6221 or consent of School

Course Text: 

At the level of Alon and Spencer, The Probabilistic Method (with an appendix of problems by Paul Erdos)

Topic Outline: 
  • The Basic Method - Examples from graph theory, combinatorics, and number theory of the use of the probabilistic method; the use of linearity of expectation
  • The Second Moment Method - The use of Markov and Chebyshev inequalities; examples from number theory and random graphs
  • The Lovasz Local Lemma - Applications in graph theory and computer science
  • Correlation Inequalities - The four functions theorem; FKG and XYZ inequalities
  • The Poisson Paradigm - Examples from random graphs; the use of martingales; Azuma's inequality, Telagrand's inequality; chromatic number of random graphs
  • Alterations - Ramsey numbers; packing and recoloring; the Rodl nibble (or the semi-random method)
  • Random Graphs - Clique number; chromatic number; branching processes; zero-one laws
  • Combinatorial Discrepancy Theory - Balancing lights; Spencer's six standard deviations result; Beck-Fiala theorem and the Komlos conjecture; linear and hereditary discrepancy
  • Derandomization - Conditional probabilities; limited independence of random variables
  • Optional Material
  • Combinatorial Geometry - Epsilon-nets and VC-dimension; additional topics
  • Codes and Games - Balancing vector game; coin-weighing problems