Perfectly balanced partitions of smoothed graphs (Q1028807)

Summary: 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 \(\epsilon\) there is a constant \(\alpha\), such that for any even \(n\) and a graph \(H\) on \(n\) vertices that satisfies \(\Delta(H)-\delta(H) \leq \alpha n\), a graph \(G\) distributed according to \(G(H,p)\), with \({\epsilon\over n} \leq p \leq 1-\frac{\epsilon}{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.