MATH 594 - The Probabilistic Method in Combinatorics.  Winter 2021

Instructor:

Sergey Norin
 

Office hours:

Zoom, Wednesday, 1-2 PM and by appointment

Email:

snorine [at] gmail.com

Web:

http://www.math.mcgill.ca/~snorin

Lecture:

Time: Monday, Wednesday 10:05 -11:25 AM
Location: Zoom

Lecture notes:

  1. January 11: Introduction
  2. January 13: Introduction. Part II
  3. January 18: Linearity of expectation
  4. January 20: Linearity of expectation. Part II
  5. January 25: Alterations
  6. January 27: Second moment method
  7. February 1: Thresholds
  8. February 3: Existence of thresholds and Chernoff Bounds
  9. February 8: Chernoff bounds: Discrepancy and Hajos' conjecture
  10. February 10: Hadwiger's conjecture for random graphs
  11. February 15: Lovasz local lemma
  12. February 17: Applications of Lovasz local lemma
  13. February 22: Correlation inequalities
  14. February 24: Janson inequalities
  15. March 8: Second Janson inequality and applications
  16. March 10: Entropy
  17. March 15: Bregman and Sidorenko inequalities
  18. March 17: Blakey-Roy theorem and Shearer's lemma
  19. March 22: Entropy compression
  20. March 24: Entropy compression. Part II
  21. March 29: Dependent random choice
  22. >March 31: Hypergraph containers

Course outline:

The probabilistic method is one of the most widely used tools for tackling problems in discrete mathematics.
In this course we will cover the methodology and some of the more striking applications, primarily in graph theory.

The topics covered will include: 
  1. Basic method, alterations. Applications to extremal and coloring problems for hypergraphs.
  2. Linearity of expectation. Graphs of high girth and chromatic number. Crossing lemma.
  3. The second moment method. Properties of random graphs.
  4. Chernoff bounds. Density of graphs excluding a minor or a subdivision.
  5. Lovasz local lemma, its variants and applications.
  6. Correlation inequalities: The four functions theorem, FKG and Janson inequalities.
  7. Entropy. Shearer’s lemma. Number of independent sets in regular graphs. Sidorenko’s conjecture.
  8. Entropy compression. Applications to list and non-repetitive coloring.
  9. Dependent random choice. Applications to Turan and Ramsey-type problems.
  10. Hypergraph containers.
Readings:

There is no required text. The lectures will be in part based on:
  1. N. Alon and J. Spencer, "The Probabilistic Method"
  2. M. Molloy and B. Reed, "2. "Graph Colouring and The Probabilistic Method"
  3. Yufei Zhao "The Probabilistic Method. Course notes"