  Given an edge-weighted graph, how many minimum $k$-cuts can it have? This is
a fundamental question in the intersection of algorithms, extremal
combinatorics, and graph theory. It is particularly interesting in that the
best known bounds are algorithmic: they stem from algorithms that compute the
minimum $k$-cut.
  In 1994, Karger and Stein obtained a randomized contraction algorithm that
finds a minimum $k$-cut in $O(n^{(2-o(1))k})$ time. It can also enumerate all
such $k$-cuts in the same running time, establishing a corresponding extremal
bound of $O(n^{(2-o(1))k})$. Since then, the algorithmic side of the minimum
$k$-cut problem has seen much progress, leading to a deterministic algorithm
based on a tree packing result of Thorup, which enumerates all minimum $k$-cuts
in the same asymptotic running time, and gives an alternate proof of the
$O(n^{(2-o(1))k})$ bound. However, beating the Karger--Stein bound, even for
computing a single minimum $k$-cut, has remained out of reach.
  In this paper, we give an algorithm to enumerate all minimum $k$-cuts in
$O(n^{(1.981+o(1))k})$ time, breaking the algorithmic and extremal barriers for
enumerating minimum $k$-cuts. To obtain our result, we combine ideas from both
the Karger--Stein and Thorup results, and draw a novel connection between
minimum $k$-cut and extremal set theory. In particular, we give and use tighter
bounds on the size of set systems with bounded dual VC-dimension, which may be
of independent interest.
