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
Seminar/Talk
Tags
Mathematics and CS Seminar, mathematical_seminar_ics
Host
Matthew Kwan
Contact
Url
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.