Friendly bisections of random graphs
Matthew Kwan (Stanford University)
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.
computational geometrydiscrete mathematicscommutative algebracombinatorics
Audience: researchers in the topic
Copenhagen-Jerusalem Combinatorics Seminar
Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.
The password for the zoom room is 123456
Organizers: | Karim Adiprasito, Arina Voorhaar* |
*contact for this listing |