On Perfectly Friendly Bisections of Random Graphs

Explore a rigorous mathematical analysis of random graph partitioning in this 57-minute lecture by Mehtaab Sawhney from MIT. Delve into the proof of a constant γ's existence in G(n,1/2) graphs, demonstrating high-probability equipartitions where vertices have (γ - ε)\sqrt{n} more neighbors in their own part. Examine the application of Boolean function tools to prove vertex-isoperimetry expansion for transitive graph subsets, and understand how this boosts constant probability results to high probability. Gain insights into advanced graph theory concepts, including perfectly friendly bisections and their implications for random graph structures.

On Perfectly Friendly Bisections of Random Graphs