New answers tagged

3

An $r$-regular expander should do it. The following is a simple observation that I first saw in Li (arXiv:2106.05513): if an $r$-regular graph has conductance $\phi$, then the smaller side $S$ of a minimum cut contains at most $|S| \leq 1/\phi$ vertices. Indeed, by definition of conductance we have that $|E(S,S^c)| \geq \phi r |S|$. Since this defines a ...


Top 50 recent answers are included