The number of minimum k -cuts: improving the Karger-Stein bound
Anupam Gupta, Euiwoong Lee, Jason Li · 2019
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.