Sharp Bounds on the Number of Small Cuts

Abstract

Let $\lambda$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $\alpha>1$, we prove that there are $O(n^{\lceil2\alpha\rceil-1})$ cuts of size strictly below $\alpha\lambda$. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.