Matthew Kwan “Friendly bisections of random graphs” | Big Seminar

November 4, 2021
19.00 MSK (UTC +3)
Talk on Big Seminar

Matthew Kwan "Friendly bisections of random graphs"

Matthew Kwan from IST Austria will give the talk Friendly bisections of random graphs" on the labs' Big Seminar.

The talk will be held in zoom
Meeting ID: 279-059-822 zoom-link
Password: first 6 decimal places of $\pi$ after the decimal point

You can also write to Alexander Polyanskii ( or to Maksim Zhukovskii ( if you want to be added to mailing list.


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.

Watch the video:

Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.