Select Page

Threshold phenomena in random structures

Sign in
BGSMath Course
From December 10, 2024
to December 19, 2024

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

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 10h to 13h

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.

CONTENT

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
Eduard-Adiel Dinu Universitatea Na?ionala de ?tiin?a ?i Tehnologie POLITEHNICA Bucure?ti
Teresa Pérez-Sala UPC
Gil Puig i Surroca Université Paris Dauphine
Joan Domingo Pasarin Universitat de Barcelona
Elitza Maneva Universitat Autònoma de Barcelona
Salim Boukfal Lazaar Universitat Autònoma de Barcelona
Guillem Perarnau Llobet Universitat Politècnica de Catalunya
Marc Noy Serrano Universitat Politècnica de Catalunya
Robin Simoens Universitat Politècnica de Catalunya
Tabriz Popatia Universitat Politècnica de Catalunya
Simeon Ball Universitat Politècnica de Catalunya
Patrick Morris Universitat Politècnica de Catalunya
Clément Requilé Universitat Politècnica de Catalunya
Oriol Serra Albó Universitat Politècnica de Catalunya
Richard Lang Universitat Politècnica de Catalunya
Sofiya Burova Universitat Politècnica de Catalunya
Miquel Ortega Universitat Politècnica de Catalunya
Jordi Castellví Foguet Universitat Politècnica de Catalunya
Izan Beltran Ferreiro Universitat Politècnica de Catalunya
Conrado Martínez Universitat Politècnica de Catalunya
Roger Lidón Ardanuy Universitat Politècnica de Catalunya
Luigi Bruzzese Universitat Politècnica de Catalunya
Nicolás Zhao Universitat Politècnica de Catalunya
Gaspar Lloret Gutiérrez-Colón Universitat Politècnica de Catalunya
Xi Chen Universitat Politècnica de Catalunya
Enric Ventura Universitat Politècnica de Catalunya
Richard Coll Josifov Universitat Politècnica de Catalunya
Xavier Povill Universitat Politècnica de Catalunya
Josep Fontana McNally Universitat Politècnica de Catalunya
Darío Martínez Ramírez Universitat Politècnica de Catalunya
Martí Planasdemunt Hospital Universitat Politècnica de Catalunya
Félix Moreno Peñarrubia Universitat Politècnica de Catalunya
Sina Forfang Universitat Politècnica de Catalunya
Vasily Apasov Universitat Politècnica de Catalunya
Víctor Villegas-Morral Universitat Politècnica de Catalunya
Marcel Fernandez Universitat Politècnica de Catalunya
Juan Jose Rue Perna Universitat Politècnica de Catalunya
Fayçal Afarsiou École centrale de Lyon
Amanda Montejano National Autonomous University of Mexico
Ewa Miklewska AGH University of Science and Technology
Pablo Nicolás Centre de Recerca Matemàtica
Alvaro Corral Centre de Recerca Matemàtica
 

For inquiries about this event please contact the Scientific Events Coordinator Ms. Núria Hernández at nhernandez@crm.cat​​