Abstract:

We prove that the family of largest cuts in the binomial random graph exhibits the following stability property:
If 1/n << p < 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 Tura'n-type problems.
This is joint work with Wojciech Samotij and Maksim Zhukovskii.