Friendly bisections of random graphs

Ferber, Asaf; Kwan, Matthew; Narayanan, Bhargav; Sah, Ashwin; Sawhney, Mehtaab

doi:10.1090/cams/13

Friendly bisections of random graphs
HTML articles powered by AMS MathViewer

by Asaf Ferber, Matthew Kwan, Bhargav Narayanan, Ashwin Sah and Mehtaab Sawhney

Comm. Amer. Math. Soc. 2 (2022), 380-416

DOI: https://doi.org/10.1090/cams/13

Published electronically: December 20, 2022

HTML | PDF

Abstract:

Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph $\mathbb {G}(n,1/2)$ admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which $n-o(n)$ vertices have more neighbours in their own part as across. Our proof is constructive, and in the process, we develop a new method to study stochastic processes driven by degree information in random graphs; this involves combining enumeration techniques with an abstract second moment argument.

References

Louigi Addario-Berry, Luc Devroye, Gábor Lugosi, and Roberto I. Oliveira, Local optima of the Sherrington-Kirkpatrick Hamiltonian, J. Math. Phys. 60 (2019), no. 4, 043301, 13. MR 3940914, DOI 10.1063/1.5020662
R. Aharoni, E. C. Milner, and K. Prikry, Unfriendly partitions of a graph, J. Combin. Theory Ser. B 50 (1990), no. 1, 1–10. MR 1070461, DOI 10.1016/0095-8956(90)90092-E
Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei, Local max-cut in smoothed polynomial time, STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, pp. 429–437. MR 3678200, DOI 10.1145/3055399.3055402
Amir Ban and Nati Linial, Internal partitions of regular graphs, J. Graph Theory 83 (2016), no. 1, 5–18. MR 3529944, DOI 10.1002/jgt.21909
Alexander Barvinok and J. A. Hartigan, The number of graphs and a random graph with a given degree sequence, Random Structures Algorithms 42 (2013), no. 3, 301–348. MR 3039682, DOI 10.1002/rsa.20409
Tom Bohman, Alan Frieze, and Eyal Lubetzky, Random triangle removal, Adv. Math. 280 (2015), 379–438. MR 3350225, DOI 10.1016/j.aim.2015.04.015
Tom Bohman and Peter Keevash, The early evolution of the $H$-free process, Invent. Math. 181 (2010), no. 2, 291–336. MR 2657427, DOI 10.1007/s00222-010-0247-x
Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290, DOI 10.1007/978-1-4612-0619-4
B. Bollobás and A. D. Scott, Problems and results on judicious partitions, Random Structures Algorithms 21 (2002), no. 3-4, 414–430. Random structures and algorithms (Poznan, 2001). MR 1945378, DOI 10.1002/rsa.10062
E. Bolthausen, An estimate of the remainder in a combinatorial central limit theorem, Z. Wahrsch. Verw. Gebiete 66 (1984), no. 3, 379–386. MR 751577, DOI 10.1007/BF00533704
E. Rodney Canfield, Catherine Greenhill, and Brendan D. McKay, Asymptotic enumeration of dense 0-1 matrices with specified line sums, J. Combin. Theory Ser. A 115 (2008), no. 1, 32–66. MR 2378856, DOI 10.1016/j.jcta.2007.03.009
Xi Chen, Chenghao Guo, Emmanouil V. Vlatakis-Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang, Smoothed complexity of local Max-Cut and binary Max-CSP, STOC ’20—Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, [2020] ©2020, pp. 1052–1065. MR 4141821, DOI 10.1145/3357713.3384325
Asaf Ferber, Matthew Kwan, and Lisa Sauermann, Singularity of sparse random matrices: simple proofs, Combin. Probab. Comput. 31 (2022), no. 1, 21–28. MR 4356454, DOI 10.1017/s0963548321000146
Gonzalo Fiz Pontiveros, Simon Griffiths, and Robert Morris, The triangle-free process and the Ramsey number $R(3,k)$, Mem. Amer. Math. Soc. 263 (2020), no. 1274, v+125. MR 4073152, DOI 10.1090/memo/1274
Z. Füredi, Personal communication.
David Gamarnik, The overlap gap property: a topological barrier to optimizing over random structures, Proc. Natl. Acad. Sci. USA 118 (2021), no. 41.
David Gamarnik and Quan Li, On the max-cut of sparse random graphs, Random Structures Algorithms 52 (2018), no. 2, 219–262. MR 3758958, DOI 10.1002/rsa.20738
Michael U. Gerber and Daniel Kobler, Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000), no. 2, 283–291. Combinatorial optimization (Copenhagen, 1998). MR 1785664, DOI 10.1016/S0377-2217(99)00459-2
Reza Gheissari, Charles M. Newman, and Daniel L. Stein, Zero-temperature dynamics in the dilute Curie-Weiss model, J. Stat. Phys. 172 (2018), no. 4, 1009–1028. MR 3830296, DOI 10.1007/s10955-018-2087-9
B. Green, 100 open problems, Manuscript, Available on request.
Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
Matthew Kwan, Benny Sudakov, and Tuan Tran, Anticoncentration for subgraph statistics, J. Lond. Math. Soc. (2) 99 (2019), no. 3, 757–777. MR 3977889, DOI 10.1112/jlms.12192
A. Liebenau and N. Wormald, Asymptotic enumeration of digraphs and bipartite graphs by degree sequence, arXiv:2006.15797, 2020.
A. Liebenau and N. Wormald, Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, arXiv:1702.08373, 2017.
Nathan Linial and Sria Louis, Asymptotically almost every $2r$-regular graph has an internal partition, Graphs Combin. 36 (2020), no. 1, 41–50. MR 4054839, DOI 10.1007/s00373-019-02116-0
Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, European J. Combin. 11 (1990), no. 6, 565–580. MR 1078713, DOI 10.1016/S0195-6698(13)80042-X
Vojtěch Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78. MR 793489, DOI 10.1016/S0195-6698(85)80023-8
Ashwin Sah and Mehtaab Sawhney, Majority dynamics: the power of one, arXiv:2105.13301, 2021.
Khurram H. Shafique and Ronald D. Dutton, On satisfactory partitioning of graphs, Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002), 2002, pp. 183–194. MR 1980038
Saharon Shelah and E. C. Milner, Graphs with no unfriendly partitions, A tribute to Paul Erdős, Cambridge Univ. Press, Cambridge, 1990, pp. 373–384. MR 1117030, DOI 10.1177/016502549001300309
Eric Yilun Song, Reza Gheissari, Charles M. Newman, and Daniel L. Stein, Local minima in disordered mean-field ferromagnets, J. Stat. Phys. 180 (2020), no. 1-6, 576–596. MR 4131002, DOI 10.1007/s10955-019-02480-4
Joel Spencer, Asymptopia, Student Mathematical Library, vol. 71, American Mathematical Society, Providence, RI, 2014. With Laura Florescu. MR 3185739, DOI 10.1090/stml/071
Michael Stiebitz, Decomposing graphs under degree constraints, J. Graph Theory 23 (1996), no. 3, 321–324. MR 1413661, DOI 10.1002/(SICI)1097-0118(199611)23:3<321::AID-JGT12>3.3.CO;2-B
Terence Tao and Van H. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2010. Paperback edition [of MR2289012]. MR 2573797
Carsten Thomassen, Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory 7 (1983), no. 2, 165–167. MR 698697, DOI 10.1002/jgt.3190070204
L. Tran and V. Vu, Reaching a consensus on random networks: the power of few, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) (Dagstuhl, Germany), vol. 176, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 20:1–20:15.
Roman Vershynin, High-dimensional probability, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47, Cambridge University Press, Cambridge, 2018. An introduction with applications in data science; With a foreword by Sara van de Geer. MR 3837109, DOI 10.1017/9781108231596
Nicholas Wormald, Asymptotic enumeration of graphs with given degree sequence, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3245–3264. MR 3966531
A. M. Zubkov and A. A. Serov, A complete proof of universal inequalities for the distribution function of the binomial law, Theory Probab. Appl. 57 (2013), no. 3, 539–544. MR 3196787, DOI 10.1137/S0040585X97986138