Matthew Kwan "Friendly bisections of random graphs" | Big Seminar
VoteIt is our pleasure to share the Big Seminar talk "Friendly bisections of random graphs" by Matthew Kwan.
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.
Seminars schedule and archive are available here - http://combgeo.org/en/events/big-seminar.
About Combgeo Lab
We are the Laboratory of Combinatorial and Geometric Structures at MIPT. The lab aims to initiate collaboration and exchange between researchers who work on different topics in the fields of Combinatorics, Discrete and Computational Geometry, and Theoretical Сomputer Science.
0 Comments