On Perfectly Friendly Bisections of Random Graphs

arXiv2305.03543MaRDI QIDQ6435500FDOQ6435500

Mehtaab Sawhney, Ashwin Sah, Dor Minzer

Publication date: 5 May 2023

Abstract: We prove that there exists a constant

g a m m a_{m a t h r m c r i t} a p p r o x .17566

such that if

G s i m m a t h b b G (n, 1 / 2)

then for any

v a r e p s i l o n > 0

with high probability

G

has a equipartition such that each vertex has

(g a m m a_{m a t h r m c r i t} - v a r e p s i l o n) s q r t n

more neighbors in its own part than in the other part and with high probability no such partition exists for a separation of

(g a m m a_{m a t h r m c r i t} + v a r e p s i l o n) s q r t 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"uredi from 1988 and in particular prove the existence of fully-friendly bisections in

m a t h b b G (n, 1 / 2)

This page was built for publication: On Perfectly Friendly Bisections of Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435500)