Tue, 26 Oct 2021
14:00
Virtual

Friendly bisections of random graphs

Ashwin Sah
(MIT)
Abstract

We introduce a new method for studying stochastic processes in random graphs controlled by degree information, involving combining enumeration techniques with an abstract second moment argument. We use it to constructively resolve a conjecture of Füredi from 1988: 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. This work is joint with Asaf Ferber, Matthew Kwan, Bhargav Narayanan, and Mehtaab Sawhney.

Further Information

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

Balancing expressiveness and inexpressiveness in view design
Benedikt, M Bourhis, P Jachiet, L Tsamoura, E ACM Transactions on Database Systems
Balancing expressiveness and inexpressiveness in view design
Benedikt, M Bourhis, P Jachiet, L Tsamoura, E ACM Transactions on Database Systems
Balancing expressiveness and inexpressiveness in view design
Benedikt, M Bourhis, P Jachiet, L Tsamoura, E ACM Transactions on Database Systems
Balancing expressiveness and inexpressiveness in view design
Benedikt, M Bourhis, P Jachiet, L Tsamoura, E ACM Transactions on Database Systems
Balancing expressiveness and inexpressiveness in view design
Benedikt, M Bourhis, P Jachiet, L Tsamoura, E ACM Transactions on Database Systems
Balancing expressiveness and inexpressiveness in view design
Benedikt, M Bourhis, P Jachiet, L Tsamoura, E ACM Transactions on Database Systems
Balancing expressiveness and inexpressiveness in view design
Benedikt, M Bourhis, P Jachiet, L Tsamoura, E ACM Transactions on Database Systems

"Historically, mathematics has been a largely male-dominated field, with women in mathematical academia consistently being underrepresented. A report in 2013 by the London Mathematical Society shows some progress has been made in increasing the participation of women in recent times, with the proportion of women pursuing an undergraduate degree in mathematics in the UK standing at around 42%.

Subscribe to