Talks

Spring 2016

# Extremal Cuts of Sparse Random Graphs

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

Speaker:

Location:

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.

Attachment | Size |
---|---|

Extremal Cuts of Sparse Random Graphs | 317.89 KB |