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 18: Linearity of expectation. Part II

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: Harris 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"