Ramsey properties of random graphs
Date:
Wednesday, November 8, 2023 13:00 - 14:15
Speaker:
Yuval Wigderson (ETH Zürich)
Location:
Mondi Seminar Room 3, Central Building
Series:
Mathematics and CS Seminar
Host:
Matthew Kwan
Contact:
Kaluza Vojtech
A basic result of probabilistic combinatorics, originally due to Erds and Rnyi, is the determination of the threshold at which the random graph G_{n,p} contains a triangle with high probability. But one can also ask more refined versions of this question, where we ask not just for one triangle but for many triangles which interact in complicated ways. For example, what is the threshold at which we can no longer partition G_{n,p} into two triangle-free subgraphs?
Such questions are the subject of Ramsey properties of random graphs, and a very general conjecture of Kohayakawa and Kreuter predicts an answer to all such questions. In this talk, I will discuss the history of these problems, and present recent progress which proves the KohayakawaKreuter conjecture in almost all cases.
Joint work with Eden Kuperwasser and Wojciech Samotij.