Friendly bisections of random graphs

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

Friendly bisections of random graphs

Ferber A, Kwan MA, Narayanan B, Sah A, Sawhney M. 2022. Friendly bisections of random graphs. Communications of the American Mathematical Society. 2(10), 380–416.

Download

2022_CommAMS_Ferber.pdf 335.96 KB [Published Version]

DOI

10.1090/cams/13

Journal Article | Published | English

Author

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

Corresponding author has ISTA affiliation

Department

Kwan Group

Abstract

Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph 𝔾(𝑛, 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 𝑛 − 𝑜(𝑛) 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.

Publishing Year

2022

Date Published

2022-12-20

Journal Title

Communications of the American Mathematical Society

Publisher

American Mathematical Society

Acknowledgement

We thank the referees for extensive comments which helped improve the paper substantially. The first author was supported in part by NSF grants DMS-1954395 and DMS-1953799. The second author was supported by NSF grant DMS-1953990. The third author was supported by NSF grant DMS180052. The fourth and fifth authors were both supported by NSF Graduate Research Fellowship Program DGE-1745302.

Volume

Issue

Page

380-416

ISSN

2692-3688

IST-REx-ID

17077

Cite this

Ferber A, Kwan MA, Narayanan B, Sah A, Sawhney M. Friendly bisections of random graphs. Communications of the American Mathematical Society. 2022;2(10):380-416. doi:10.1090/cams/13

Ferber, A., Kwan, M. A., Narayanan, B., Sah, A., & Sawhney, M. (2022). Friendly bisections of random graphs. Communications of the American Mathematical Society. American Mathematical Society. https://doi.org/10.1090/cams/13

Ferber, Asaf, Matthew Alan Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawhney. “Friendly Bisections of Random Graphs.” Communications of the American Mathematical Society. American Mathematical Society, 2022. https://doi.org/10.1090/cams/13.

A. Ferber, M. A. Kwan, B. Narayanan, A. Sah, and M. Sawhney, “Friendly bisections of random graphs,” Communications of the American Mathematical Society, vol. 2, no. 10. American Mathematical Society, pp. 380–416, 2022.

Ferber A, Kwan MA, Narayanan B, Sah A, Sawhney M. 2022. Friendly bisections of random graphs. Communications of the American Mathematical Society. 2(10), 380–416.

Ferber, Asaf, et al. “Friendly Bisections of Random Graphs.” Communications of the American Mathematical Society, vol. 2, no. 10, American Mathematical Society, 2022, pp. 380–416, doi:10.1090/cams/13.

All files available under the following license(s):

Creative Commons Attribution 3.0 Unported (CC BY 3.0):