Stability of large cuts in random graphs

Zoom Link

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 (https://arxiv.org/abs/2402.14620) with Ilay Hoshen (Tel Aviv University) and Maksim Zhukovskii (University of Sheffield).

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.