Graph Theory and Combinatorics Seminar
Sep 8, 2026 1:00 - 2:00 pm
Henry Administration Building 143
- Sponsor
- Department of Mathematics
- Speaker
- Ilay Hoshen (Tel Aviv University)
- Contact
- Abhishek Dhawan
- adhawan2@illinois.edu
- Originating Calendar
- Mathematics Seminar Series: Combinatorics
- Title: Stability of large cuts in random graphsAbstract: We prove that the family of largest cuts in the binomial random graph exhibits the following stability property: If 1/n << p <= 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.