On Perfectly Friendly Bisections of Random Graphs
summary
Proves a sharp threshold: there is a constant γ so G ~ G(n,1/2) with high probability has an equipartition where every vertex has at least (γ−ε)√n more neighbors inside than across, and with high probability no bisection meets (γ+ε)√n. Key steps: first/second moment counts using McKay–Wormald enumeration produce a constant-probability existence, a max-degree symmetric-difference metric measures needed local edits, and Boolean functions tools plus a vertex-isoperimetry for transitive subsets bootstrap constant probability to whp. Joint w. Dor Minzer and Ashwin Sah.
AI-written summary · about