Stability of large cuts in random graphs
Organizer
Benjamin Sudakov
Speaker
Wojtek Samotij
Time
Tuesday, May 6, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
A cut in a graph $G$ is the set of edges that cross some partition of the vertices of $G$ into two sets and a maximum cut of $G$ is a cut with the largest size among all cuts. We will prove that the family of largest cuts in the binomial random graph $G_{n,p}$ exhibits the following stability property: If $1/n << p <= 1-\Omega(1)$, then, with probability $1-o(1)$, there is a set of $n-o(n)$ vertices that is partitioned in the same manner by all maximum cuts of $G_{n,p}$. Moreover, the analogous statement remains true when one replaces maximum cuts with nearly-maximum cuts. We will then demonstrate how one can use this statement as a tool for showing that certain properties of $G_{n,p}$ that hold in a fixed cut hold simultaneously in all maximum cuts.
This talk is based on a joint work with Ilay Hoshen (Tel Aviv University) and Maksim Zhukovskii (University of Sheffield).
This talk is based on a joint work with Ilay Hoshen (Tel Aviv University) and Maksim Zhukovskii (University of Sheffield).
Speaker Intro
Wojciech Samotij was born in Wrocław, Poland in 1983. After receiving MSc degrees in mathematics and in computer science from the University of Wrocław, he moved to the University of Illinois at Urbana-Champaign, where in 2010 he obtained his doctorate, advised by József Balogh. Samotij spent his postdoctoral years between Trinity College in Cambridge and Tel Aviv University, where he was appointed as a faculty member in 2014. He has worked at the School of Mathematical Sciences of Tel Aviv University ever since.