Theory of Computing
-------------------
Title     : The Minimum Bisection in the Planted Bisection Model
Authors   : Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch
Volume    : 13
Number    : 8
Pages     : 1-22
URL       : https://theoryofcomputing.org/articles/v013a008

Abstract
--------

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 $+/- 1$). Any two vertices that
belong to the same class are linked by an edge with probability
$p_+$ and any two that belong to different classes with probability
$p_- < p_+$ independently. The planted bisection model has been
used extensively to benchmark graph partitioning algorithms. If 
$p_{+/-}=2d_{+/-}/n$ for numbers $0\leq d_- < d_+$ that remain fixed
as $n\to\infty$, then w.h.p. the "planted" bisection (the one used to
construct the graph) will not be a minimum bisection. In this paper we
derive an asymptotic formula for the minimum bisection width under the
assumption that $d_+ -d_- > c\sqrt{d_+ \ln d_+}$ for a
certain constant $c> 0$.


A preliminary version of this paper appeared in the
Proceedings of the 19th International Workshop on
Randomization and Computation (RANDOM 2015).