EUVIMEDEUVIMED entdecken
Crossref

Friendly bisections of random graphs

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

Communications of the American Mathematical Society · 2022

DOI: 10.1090/cams/13 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Communications of the American Mathematical Society, 2022. Verfasst von Asaf Ferber und 4 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 40 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph G ( n , 1 / 2 ) \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 ) 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.

Zitieren

APA

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

Vancouver

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

BibTeX
@article{Ferber2022,
  author = {Ferber, Asaf and Kwan, Matthew and Narayanan, Bhargav and Sah, Ashwin and Sawhney, Mehtaab},
  title = {Friendly bisections of random graphs},
  journal = {Communications of the American Mathematical Society},
  year = {2022},
  doi = {10.1090/cams/13}
}
Kostenlos starten →