- Series
- Combinatorics Seminar
- Time
- Friday, October 21, 2022 - 4:00pm for 1 hour (actually 50 minutes)
- Location
- Instructional Center 105
- Speaker
- Bhargav Narayanan – Rutgers University – https://sites.math.rutgers.edu/~narayanan/
- Organizer
- Anton Bernshteyn

This talk is part of the **Atlanta Combinatorics Colloquium**. Note the time (**4pm**) and location (**Instructional Center 105**).

It is easy to partition the vertices of any graph into two sets where each vertex has at least as many neighbours across as on its own side; take any maximal cut! Can we do the opposite? This is not possible in general, but Füredi conjectured in 1988 that it should nevertheless be possible on a random graph. I shall talk about our recent proof of Füredi's conjecture: with high probability, the random graph $G(n,1/2)$ on an even number of vertices admits a partition of its vertex set into two parts of equal size in which $n−o(n)$ vertices have more neighbours on their own side than across.