北京雁栖湖应用数学研究院

本杰明·苏达科夫

Wojtek Samotij

2025年05月06日 17:05 至 18:15

Online

Zoom 787 662 9899 (BIMSA)

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).

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.