Talk information

Date: Sunday, February 11, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Ilay Hoshen (TAU)
Title: Stability of large cuts in random graphs

Abstract:

We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If $1/n \ll p \le 1-\Omega(1)$, then, with high probability, 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 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 balanced cut hold simultaneously in all maximum cuts. We provide two example applications of this tool. In this talk, we show that maximum cuts in $ G_{n, p}$ typically partition the neighbourhood of every vertex into nearly equal parts; this resolves a conjecture of DeMarco and Kahn for all but a narrow range of densities $p$. We will also mention another application regarding sharp thresholds in Turán-type problems.

This is joint work with Wojciech Samotij and Maksim Zhukovskii.