
























Resolving a conjecture of Füredi from 1988, we prove that with high probability, the random graph $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 at least as many neighbours in their own part as across. The engine of our proof is 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。