- Series
- Combinatorics Seminar
- Time
- Friday, October 2, 2026 - 3:15pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- IIay Hoshen – Tel Aviv University – ilayhoshen@gmail.com – https://sites.google.com/view/ilay-hoshen
- Organizer
- Mehmet Akif Yildiz
We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If $1/n \ll p \leq 1-\Omega(1)$, then, with high probability, there is a set of $n - o(n)$ vertices that is partitioned in the same manner by all maximum cuts of $G_{n, p}$. Moreover, the analogous statement remains true when one replaces maximum cuts with nearly-maximum cuts.
We then demonstrate how one can use this statement as a tool for showing that certain properties of $G_{n, p}$ that hold in a fixed balanced cut hold simultaneously in all maximum cuts. We provide two example applications of this tool. In this talk, we show that maximum cuts in $G_{n, p}$ typically partition the neighbourhood of every vertex into nearly equal parts; this resolves a conjecture of DeMarco and Kahn for all but a narrow range of densities $p$. We will also mention another application regarding sharp thresholds in Turán type problems.
This is joint work with Wojciech Samotij and Maksim Zhukovskii.