Probabilistic Methods in Combinatorics

Department: 
MATH
Course Number: 
7018
Hours - Lecture: 
3
Hours - Lab: 
0
Hours - Recitation: 
0
Hours - Total Credit: 
3
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.

Prerequisites: 

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