2021/05/27 by Ferber, Asaf, Kwan, Matthew, Narayanan, Bhargav +2 · 3 citations
#05C80 (primary) #60C05 (secondary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2105.13337
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.