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^{\lceil 2\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.