## 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