On Perfectly Friendly Bisections of Random Graphs

Channel:

Simons Institute for the Theory of Computing

Subscribers:

68,600

Published on July 1, 2023 10:11:24 AM ● Video Link: https://www.youtube.com/watch?v=lKuaNBHEQXM

Duration: 56:40

409 views

6

Mehtaab Sawhney (MIT)
https://simons.berkeley.edu/talks/mehtaab-sawhney-mit-2023-06-30
Beyond the Boolean Cube

We prove that there exists a constant γ such that if G is drawn from G(n,1/2) then for any ε ＞0 with high probability G has a equipartition such that each vertex has (γ - ε )\sqrt{n} more neighbors in its own part than in the other part and with high probability no such partition exists for a separation of (γ + ε )\sqrt{n}. The talk will focus on the use on boolean functions tools to prove a certain vertex-isoperimetry expansion result tailored to transitive subsets of graphs and how this is used to boost a constant probability result to whp.
Joint w. Dor Minzer and Ashwin Sah