Abstract
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