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)
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 GAPCOMB–UPC group.
Previously, he was a postdoc at LaBRI–U. Bordeaux and IME–USP, 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.
| Name | Institution |
|---|---|
| Juan Jose Rue Perna | Universitat Politècnica de Catalunya |
| GUNVANT BIRAJDAR | Institute of Chemical Technology Mumbai |
| Elitza Maneva | Universitat Autònoma de Barcelona |
| Enric Ventura | Universitat Politècnica de Catalunya |
| Richard Coll Josifov | Universitat Politècnica de Catalunya |
| Joan Domingo Pasarin | Universitat de Barcelona |
| Xavier Povill | Universitat Politècnica de Catalunya |
| Josep Fontana McNally | Universitat Politècnica de Catalunya |
| 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 |
| Amanda Montejano | National Autonomous University of Mexico |
| 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 |
| Eduard-Adiel Dinu | Universitatea Na?ionala de ?tiin?a ?i Tehnologie POLITEHNICA Bucure?ti |
| Darío Martínez Ramírez | Universitat Politècnica de Catalunya |
| Ewa Miklewska | AGH University of Science and Technology |
| Martí Planasdemunt Hospital | Universitat Politècnica de Catalunya |
| Félix Moreno Peñarrubia | Universitat Politècnica de Catalunya |
 |
For inquiries about this event please contact the Scientific Events Coordinator Ms. Núria Hernández at nhernandez@crm.cat
|