- 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.