Geometric, Algebraic and Probabilistic Combinatorics

Reading Seminar on Thresholds

Reading group that covers a new breakthrough in random discrete structures. We will cover related topics such as the switching lemma of Razborov and the Sunflower conjecture. We meet on Fridays at 11:00 in C3-005.

Thresholds 

Ever since the work of Erdős and Rényi pioneering the study of random graphs, one of the central themes of the subject has been to determine the location of the threshold for certain graph properties; the critical probability at which the property switches from being very unlikely to very likely. For many examples of interest, such as the appearance of (possibly spanning) subgraphs, one can obtain lower bounds on thresholds by running simple expectation calculations. In this reading seminar, we will discuss the recent solution of a surprising conjecture of Kahn and Kalai from 2006, that states that these expectation calculations are actually never far from the truth and that they differ from the true value of the threshold by at most a factor of log n. The conjecture is very general and has many important implications in the study of random graph thresholds. 

Until a couple of years ago this conjecture seemed far out of reach and it was not even clear whether one should try to prove it or try to find a counterexample. This makes the solution of this conjecture, posted by Park and Pham in March this year, a truly remarkable result and perhaps even more surprising is that their proof is only 5 pages and, by all accounts, a very elegant argument using no heavy machinery. Although this result came as a huge surprise in the community, it builds on the ideas of several big breakthroughs in recent years. Indeed, in 2019, Frankston, Kahn, Narayanan and Park posted the proof of a fractional version of the Kahn-Kalai conjecture, a weaker form of the conjecture that still has far-reaching implications. In turn, the proof in that paper (now in Annals) adopts ideas of another big breakthrough (also in Annals) to a seemingly unrelated problem known as the Erdős-Rado Sunflower problem. 

In this seminar, which is planned to start in September, we will dive into the proofs of these milestones in combinatorics (and some related results), learning the key technique which is common in all three and which is bound to have more applications.


Schedule of the sessions and lecture room:

  1. Tuesday October 11, 11:30-13:00: Introduction and motivation for seminar. (Patrick Morris) Video. Video (June)

  2. Friday November 4, 11:00-12:30: Switching Lemma [4]. (Ilario Bonacina) Video.

  3. Friday November 11, 11:00-12:30: Sunflowers 1 [3]. (Jordi Castellví)

  4. Friday November 18, 11:00-12:30: Sunflowers 2 [3]. (Miquel Ortega)

  5. Friday November 25, 11:00-12:30: Fractional 1 [2]. (Patrick Morris)

  6. Friday December 2, 11:00-12:30: Fractional 2 [2] (Irene Gil Fernández)

  7. Friday December 16, 11:00-12:30: Park-Pham Theorem [1] (Clément Requilé)

  8. Friday January 13, 2023, 11:00-12:30: Discussion Session on related results.

  9. Friday January 20, 2023, 11:00-12:30: Discussion Session on related results.


All lectures are in the C3-005 Room at Campus Nord (usual seminar room).

Talks will be prepared to be between 1 hour and 1 hour 15 mins with extra time at the end reserved for questions and discussion.

Stream link: Meet link


References:

  1. J. Park and H. Pham: A proof of the Kahn - Kalai Conjecture (https://arxiv.org/abs/2203.17207)
  2. K. Frankston, J. Kahn, B. Narayanan and J. Park: Thresholds versus fractional expectation-thresholds (https://arxiv.org/abs/1910.13433)
  3. R. Alweiss, S. Lovett, K. Wu, J. Zhang: Improved bounds for the sunflower lemma (https://arxiv.org/abs/1908.08483)
  4. A. Razborov: Bounded arithmetic and lower bounds in Boolean complexity. (http://people.cs.uchicago.edu/~razborov/files/bobo.pdf)

Expository references and lecture notes: