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
DOI
Journal Article
| Published
| English
Author
Ferber, Asaf;
Kwan, Matthew AlanISTA 
;
Narayanan, Bhargav;
Sah, Ashwin;
Sawhney, Mehtaab
;
Narayanan, Bhargav;
Sah, Ashwin;
Sawhney, MehtaabDepartment
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
Date Published
2022-12-20
Journal Title
Communications of the 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
2
Issue
10
Page
380-416
ISSN
IST-REx-ID
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):
Main File(s)
File Name
2022_CommAMS_Ferber.pdf
335.96 KB
Access Level
Open Access
Date Uploaded
2024-07-12
MD5 Checksum
719861e76f5bce3d0362d8171daa26fc
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2105.13337
Google Scholar