- You are here:
- Home

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.

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