BGSMath Advanced course on Threshold Phenomena for Random Structures

Official webpage: https://www.crm.cat/bgsmath-threshold-phenomena-in-random-structures/

Randomness plays a vital role across many scientific disciplines, aiding in algorithm design, modelling, engineering, and, of course, mathematical proofs. Understanding the properties of typical random structures is crucial in order to use randomness effectively. This knowledge is particularly relevant in modern applications involving large and intricate systems like complex networks or particle models. Despite the simple description of some random structures, discerning their typical properties can be highly challenging, especially considering the complexity of the properties involved. Over the past few decades, different fields have developed powerful tools to tackle this challenge, ranging from Probabilistic Combinatorics to Algorithms and Statistical Physics. These tools vary in their applicability, with some tailored for specific contexts and others offering broader solutions.

In this course we will present the notion of threshold, a phenomenon consisting on a sudden behavioural change in the random structure produced by a small increase of the modelling parameter (temperature, energy, probability…). We will survey the most recent advances in the area as well as explore applications in other fields such as Physics, Sociology, Ecology, Statistics and Computer Science. The last part of the course will be devoted to covering three very recent breakthroughs in the area. 

1. the Kahn-Kalai conjecture, now Park-Pham theorem, asserting that thresholds can not differ too much from expected thresholds [10]. We plan to give a full proof of it.
   
   
2. The satisfiability conjecture, now the Ding-Sly-Sun theorem, that pins down the threshold for a random k-SAT formula being satisfiable [4]. The proof is this theorem is highly non-trivial, but we plan to do an overview on the topic and explain the main connections with (1).
   
   
3. The planted clique conjecture, on the statistical-computation gap of distinguishing the planted clique model from a binomial random graph.

The course is aimed at master and doctoral students, and at postdoctoral researchers in the areas of Mathematics, Computer Science and Physics, but is also open to all early career researchers and faculty in other areas that are interested in the fundamentals of threshold phenomena and its applications to different disciplines.

Lectures will take place in Room 101 at FME-UPC, Math building (10:00–13:00).

Below, there is a detailed summary of the contents of the course.

10th December: Introduction to thresholds with applications

• Threshold phenomenon and phase transitions.
• Stochastic models.
• The pp-measure on the Boolean lattice.
• Application in Physics: bond percolation on Z2\mathbb{Z}^2.
• Application in Epidemiology: spreading of infectious diseases and BGW trees.
• Application in Ecology: forest fires and site percolation.
• Application in Sociology: voting systems and random permutations.
• Coffee and cookies (circa 11:15–11:30).
• The Bollobás–Thomasson theorem on the existence of thresholds for monotone properties.
• Erdős–Rényi model G(n,p)G(n, p).
• Threshold location: the First and Second moment methods.
  • Example 1: Existence of isolated vertices and connectivity in G(n,p)G(n, p).
  • Example 2: Existence of triangles in G(n,p)G(n, p).
• Sharp and coarse thresholds — definitions.
  • Examples 1 and 2 — what is known (without proofs).

12th December: Zooming in on thresholds: sharp and coarse thresholds

• kk-SAT and satisfiability conjecture (teaser).
• Boolean functions, Influence, and examples.
• Margulis–Russo Lemma with proof.
• Example 2 revisited with MR lemma.
• Friedgut’s criterion to determine the sharpness/coarseness of a threshold — full version and working versions.
• Coffee and cookies (circa 11:30–11:45).
• Example 1 revisited via Friedgut’s criterion.
• Example 3: Shamir’s problem — perfect matchings in hypergraphs.
• Shamir’s problem via Friedgut’s criterion.
• Rational exponents for coarse thresholds.

17th December: Locating thresholds: the spread lemma

• Lower bound on thresholds with the First Moment.
• Recall example of triangles.
• Connectivity via spanning trees.
• Shamir’s Problem — perfect matchings in hypergraphs.
• Triangle with a pendent edge.
• Expectation thresholds.
• Coupon collector lower bounds.
• Ad hoc upper bounds on thresholds overview.
• Spread definition.
• Spread Lemma.
• Consequences of the Spread Lemma for the examples above.
• History of the Spread Lemma and (fractional) Kahn–Kalai conjecture.
• Coffee and cookies (circa 11:15–11:30).
• From binomial to random fixed-size sets.
• Minimal Fragments.
• Random bite lemma.
• Proof of the Spread Lemma from the random bite lemma.
• Proof of the random bite lemma.

19th December: Statistical and algorithmic barriers for thresholds

• Random kk-SAT problem.
• Satisfiability conjecture.
• Upper bound on the SAT threshold.
• Algorithmic approach toward the lower bound.
• Second moment approach to the lower bound.
• Pushing the second moment: NAESAT and weighted versions.
• Geometry of the space of solutions.
• Replica symmetry and correlations.
• Algorithmic barriers.
• Coffee and cookies (circa 11:20–11:40).
• Statistical problems on random structures.
• Planted clique model.
• Hypothesis test and risk.
• Detection threshold: detecting a planted clique.
• Estimation threshold: locating a planted clique.
• Spectral test and algorithms.