The minimum bisection in the planted bisection model

Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang +1

In the planted bisection model a random graph $G(n,p_{+},p_{-})$ with $n$ vertices is created by partitioning the vertices randomly into two classes of equal size (up to $\pm 1$). Any…