Select Page

# Threshold phenomena in random structures

BGSMath Course
From December 09, 2024
to December 20, 2024

Sessions: December 10-12-17-19 from 9h to 12h

Venue: Facultat de Matemàtiques i Estadística at UPC.

Room: 101

Registration deadline 03 / 12 / 2024
SCHEDULE

Period: December 10, 12, 17 and 19.
Time Schedule: From 9h to 12h

Classroom: Room 101 – Facultat de Matemàtiques i Estadística (FME-UPC)

Introduction

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 Sociology, Biology, Statistics and Computer Science. The last part of the course will be devoted to covering two 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).

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.

Organisers | Speakers

### Patrick Morris

##### UPC

Patrick Morris is currently a postdoctoral researcher in the GAPCOMB group at Universitat Politècnica de Catalunya (UPC) in Barcelona, hosted by Prof. Guillem Perarnau and funded by a Walter Benjamin fellowship from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation).

He completed his PhD in 2021 in the Combinatorics and Graph Theory group of the Mathematics department at the Freie Universität Berlin, under the supervision of Prof. Tibor Szabó.  He also did a Master’s in the same group and before that a 4 year Msci at the University of Bristol. You can see here his (perhaps outdated) CV.

### Tássio Naia dos Santos

##### CRM

Tássio Naia dos Santos is a María de Maetzu fellow at the Centre de Reserca Matemática, working with Perarnau, Guillem and the GAPCOMBUPC group.

Previously, he was a postdoc at LaBRIU. Bordeaux and IMEUSP, working with Marthe Bonamy and Yoshiharu Kohayakawa.

He received his PhD from the University of Birmingham, in 2018, where his supervisors were Richard Mycroft and Deryk Osthus.

He is interested in Combinatorics, Probability and Algorithms.

### Guillem Perarnau

##### UPC-CRM

Guillem Perarnau did his bachelor, master and PhD at Universitat Politècnica de Catalunya (UPC), advised by Oriol Serra. From 2013 to 2015 he had the pleasure to be a CARP Postdoc Fellow at McGill University, working with Bruce Reed and Louigi Addario-Berry. From 2016 to 2019 he was a Lecturer in the Combinatorics, Probability and Algorithms group at the University of Birmingham. Since 2019 he is an Associate Professor in GAPCOMB at UPC. He is affiliated to CRM and to IMTech, and to BGSMath.

His main research interests are in Probabilistic and Extremal Combinatorics, Random Combinatorial Structures, Discrete Stochastical Processes and the analysis of Randomized Algorithms.

Currently, he is coPI of the CONTREWA grant, coordinator and PI of the Spanish Discrete and Algorithmic Mathematics Network and he participates in the RandNET MSCA Exchange Programme.

## Sessions:

Lecture 1: Introduction to thresholds. First examples. Lecturer: TN
Lecture 2: Applications to Statistical Physics, Combinatorics, Algorithms and Complexity, Social Choice Theory, Coding Theory, and Statistics. We will follow the recent survey of Perkins [11]. Lecturer: PM/GP
Lecture 3: Proof and context of the Kahn-Kalai Conjecture [8] (now, Park-Pham Theorem [10]). Lecturer: PM
Lecture 4: Overview of the Satisfiability conjecture and its proof.[4]. Lecturer: GP

Recommended prerequisites:
1. Basic notions from Discrete probability.
2. Sections 4.4 and 10 of [1] give some background on thresholds in random graphs.
3. The Quanta article [2] gives a nice exposition outlining aspects of the recent breakthrough result [10] which will be the subject of Lecture 3.

##### REFERENCES

[1] N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, 2016.
[2] Jordana Cepelewicz. Elegant Six-Page Proof Reveals the Emergence of Random Structure. Quanta Magazine, 2022. https://www.quantamagazine.org/elegant-six-page-proof-reveals-the-emergence-of-random-structure-20220425/
[3] A. Coja-Oghlan and K. Panagiotou. The asymptotic k-sat threshold. Advances in Mathematics, 100(288):985–1068, 2016.
[4] J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k. Annals of Mathematics, 196(1):1–388, 2022.
[5] H. Duminil-Copin. Sharp threshold phenomena in statistical physics. Japanese Journal of Mathematics, 14:1–25, 2019.
[6] K. Frankston, J. Kahn, B. Narayanan, and J. Park. Thresholds versus fractional expectation thresholds. Annals of Mathematics, 194(2):475–495, 2021.
[7] E. Friedgut. Sharp thresholds of graph properties, and the k-SAT problem. Journal of the American mathematical Society, 12(4):1017–1054. Appendix by J. Bourgain, 1999.
[8] J. Kahn and G. Kalai. Thresholds and expectation thresholds. Combinatorics, Probability and Computing, 16(3):495–502, 2007.
[9] J. Park. Threshold phenomena for random discrete structures. arXiv preprint arXiv:2306.13823, 2023.
[10] J. Park and H. Pham. A proof of the Kahn–Kalai conjecture. Journal of the American Mathematical Society, 37(1), 235–243, 2024.
[11] W. Perkins. Searching for (sharp) thresholds in random structures: where are we now? To appear in Proceedings of the Current Events Bulletin at the Joint Mathematics Meetings, 2024. arXiv preprint arXiv:2401.01800.
[12] M. Talagrand. Are many small sets explicitly small? In Proceedings of the forty-second ACM symposium on Theory of computing, pages 13–36, 2010.

LIST OF PARTICIPANTS
Name Institution
GUNVANT BIRAJDAR Institute of Chemical Technology Mumbai
Juan Jose Rue Perna Universitat Politècnica de Catalunya