Perfectly Balanced Partitions of Smoothed Graphs - Ben-Eliezer, Ido; Krivelevich, Michael (The Electronic Journal of Combinatorics, 2009)
For a graph G=(V,E) of even order, a partition (V_1,V_2) of the vertices is said to be perfectly balanced if |V_1|=|V_2| and the numbers of edges in the subgraphs induced by V_1 and V_2 are equal. For a base graph H define a random graph G(H,p) by turning every non-edge of H into an edge and every edge of H into a non-edge independently with probability p. We show that for any constant ε there is a constant α, such that for any even n and a graph H on n vertices that satisfies Δ(H)-δ(H) ≤ α n, a graph G distributed according to G(H,p), with εn ≤ p ≤ 1-εn, admits a perfectly balanced partition with probability exponentially close to 1. As a direct consequence we get that for every p, a random graph from G(n,p) admits a perfectly balanced partition with probability tending to 1.