On perfectly friendly bisections of random graphs
Dor Minzer, Ashwin Sah, Mehtaab S. Sawhney · The Annals of Probability · 2024
We prove that there exists a constant γcrit≈0.17566 such that if G∼G(n,1/2), then for any ε>0 with high probability G has a equipartition such that each vertex has (γcrit−ε)n more neighbors in its own part than in the other part and with high probability no such partition exists for a separation of (γ crit+ε)n. The proof involves a number of tools ranging from isoperimetric results on vertex-transitive sets of graphs coming from Boolean functions, switchings, enumeration of graphs with a given degree sequence, and the second moment method. Our results substantially strengthen recent work of Ferber, Kwan, Narayanan, and the last two authors on a conjecture of Füredi from 1988 and, in particular, prove the existence of fully-friendly bisections in G(n,1/2).