Nov 8, 2023
Ramsey properties of random graphs
Date: November 8, 2023 |
1:00 pm –
2:15 pm
Speaker:
Yuval Wigderson, ETH Zürich
Location: Mondi Seminar Room 3, Central Building
Language:
English
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.
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.
