On Minimum Vertex Bisection of Random d-Regular Graphs

Minimum vertex bisection is a graph partitioning problem in which the aim is to find a partition of the vertices into two equal parts that minimizes the number of vertices in one partition set that has a neighbor in the other set. In this work we are interested in providing asymptotically almost surely upper bounds on the minimum vertex bisection of random d-regular graphs, for constant values of d. Our approach is based on analyzing a greedy algorithm by using the Differential Equations Method. In this way, we obtain the first known non trivial upper bounds for the vertex bisection number in random regular graphs. The numerical approximations of these theoretical bounds are compared with the emprical ones, and with the lower bounds from Kolesnik and Wormald: "Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs", SIAM J. on Disc. Math. 28(1), 553-575, 2014.