Mehtaab Sawhney, Columbia University

Abstract

We prove that if G~G(n,1/2) then with high probability there exists a equipartition such that each vertex has more neighbors across the partition than within their own part. The proof involves tools ranging from isoperimetric results on vertex transitive graphs to switchings to degree enumeration formulas and the second moment method. 

Based on joint work with Dor Minzer and Ashwin Sah.

See: https://sites.google.com/view/rutgersdmseminar