Friendly bisections of random graphs

19.10.2021 16:00 - 17:30

Matthew Kwan (IST Austria)

Abstract: Resolving a conjecture of Füredi, we prove that almost every n-vertex graph admits a partition of its vertex set into two parts of equal size in which almost all vertices have more neighbours on their own side than across. Our proof involves some new techniques for studying processes driven by degree information in random graphs, which may be of general interest.

This is joint work with Asaf Ferber, Bhargav Narayanan, Ashwin Sah and Mehtaab Sawhney. 


P.S. Beim TU-Eingang wird die 3G-Regel kontrolliert!!! Bitte ein paar Minuten einplanen. 

M. Drmota
TU Wien, Zeichensaal 3, 7. Stock