ACO Seminar - Yuval Widgerson

— 4:00pm

Location:
In Person - Wean Hall 8220

Speaker:
YUVAL WIDGERSON, Junior Fellow, Department of Mathematics, ETH Zürich
https://n.ethz.ch/~ywigderson/


Graph decompositions, Ramsey theory, and random graphs

A basic result of probabilistic combinatorics, originally due to Erdös and Rényi, is the determination of the threshold at which the random graph Gn,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 Gn,p into two triangle-free subgraphs? 

In this talk, I will discuss the proof of the Kohayakawa–Kreuter conjecture, which gives a general answer to all such questions. Rather surprisingly, a key step of the proof is a purely deterministic graph decomposition statement, closely related to classical results such as Nash-Williams' tree decomposition theorem, whose proof uses techniques from combinatorial optimization and structural graph theory. 

Based on joint works with Micha Christoph, Eden Kuperwasser, Anders Martinsson, Wojciech Samotij, and Raphael Steiner.

Event Website:
https://aco.math.cmu.edu/abs-24-25/oct31.html


Add event to Google
Add event to iCal