Spring 2016

Extremal Cuts of Sparse Random Graphs

Monday, May 2, 2016 4:00 pm4:45 pm PDT

Add to Calendar


Calvin Lab

The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless P=NP), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi graph of M=N d/2 edges, the leading correction to M/2 (the typical cut size), is P_* sqrt(N M/2). Here P_* is the ground state energy of the Sherrington-Kirkpatrick model, expressed analytically via Parisi's formula.
This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.
PDF icon Extremal Cuts of Sparse Random Graphs317.89 KB