ON PERFECTLY FRIENDLY BISECTIONS OF RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Minzer, Dor; Sah, Ashwin; Sawhney, Mehtaab
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/24-AOP1696
• 发表日期: 2024
• 页码: 2281-2341
• 关键词: local algorithms; asymptotic enumeration; BOOLEAN FUNCTIONS; sharp threshold; degree sequence; maximum degree; max-cut

摘要

We prove that there exists a constant gamma (crit) approximate to 0.17566 such that if G similar to G (n, 1/2), then for any epsilon > 0 with high probability G has a equipartition such that each vertex has (gamma( crit) - epsilon) root 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( crit) + epsilon) root 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 & uuml;redi from 1988 and, in particular, prove the existence of fully-friendly bisections in G (n, 1/2).