Extremal subgraphs of random graphs

We prove that there is a constant c > 0, such that whenever p ≥ n ‐ c , with probability tending to 1 when n goes to infinity, every maximum triangle‐free subgraph of the random graph G n , p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M ≫ n and M ≤ $(\matrix{ n \cr 2 \cr } )$ /2, is “nearly unique”. More precisely, given a maximum cut C of G n , M , we can obtain all maximum cuts by moving at most \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*}\end{document} vertices between the parts of C . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012