On Perfectly Friendly Bisections of Random Graphs

Abstract

We prove that there exists a constant ${\gamma }_{\mathrm{crit}}\approx .17566$ such that if $G\sim \mathbb{G}(n,1/2)$ then for any $\epsilon >0$ with high probability $G$ has a equipartition such that each vertex has $({\gamma }_{\mathrm{crit}}-\epsilon )\sqrt{n}$ more neighbors in its own part than in the other part and with high probability no such partition exists for a separation of $({\gamma }_{\mathrm{crit}}+\epsilon )\sqrt{n}$. The proof involves a number of tools ranging from isoperimetric results on vertex-transitive sets of graphs coming from Boolean functions, switchings, degree enumeration formulas, 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 $\mathbb{G}(n,1/2)$

51 pages