Stability of large cuts in random graphs

We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If 1/n p = 1- (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₍, ₏. 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₍, ₏ that hold in a fixed balanced cut hold simultaneously in all maximum cuts. We provide two example applications of this tool. First, we prove that maximum cuts in G₍, ₏ 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. Second, for all edge-critical, nonbipartite, and strictly 2-balanced graphs H, we prove a lower bound on the threshold density p above which every largest H-free subgraph of G₍, ₏ is ( (H) -1) -partite. Our lower bound exactly matches the upper bound on this threshold recently obtained by the first two authors.