Seminar Details

Consider a dense Erdos--Renyi random graph $G(n,p)$ with $p>0$ fixed. Can we partition the graph into two nonempty sets such that every vertex has more neighbors in its own set than in the other? Will a "greedy search" algorithm find such local MINCUTs or will it end up in one of the two trivial partitions $([n],\emptyset)$? We relate these two questions to the local energy minima of an Ising model on the random graph. While we leave open the question of whether/how many nontrivial local minima exist, one might expect that as in similar disordered systems, there are a rapidly diverging (in $n$) number of such local minima. We prove, however, that starting from a typical initial configuration, a dynamic search for local minima avoids all such local minima with high probability and quickly ends up in one of the two homogenous ground states (corresponding to the two trivial partitions).