← 研踪 PaperTrailarXiv:2609.10255 · v2
Sharp Bounds on the Number of Small Cuts
首次提交 2026-09-09 22:40
版本更新 2026-11-11 12:51
雷达观测 2026-11-13 11:11
摘要
A $k$-cut of an undirected graph is a minimal edge set whose removal leaves at least $k$ connected components, and its cost is the sum of its edge costs. Write $λ_k$ for the minimum cost of a $k$-cut. For fixed $k\ge2$ and $α\ge1$, we show that in any $n$-vertex graph with $n\ge k$ and nonnegative edge costs, the number of $k$-cuts of cost strictly below $αλ_k$ is $O(n^{\lceilαk\rceil-1})$. This implies an $O(n^{\lfloorαk\rfloor})$ bound for $k$-cuts of cost at most $αλ_k$, sharpening the $O(n^{αk})$ bound of Gupta, Harris, Lee and Li. For $k=2$, our strict bound resolves a conjecture of Henzinger and Williamson and an open question of Karger. The exponent $\lceilαk\rceil-1$ is optimal for $k$-cuts for every $k\ge2$ and $α>1$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-11 12:51 · 最新观测版本
Sharp Bounds on the Number of Small Cuts
A $k$-cut of an undirected graph is a minimal edge set whose removal leaves at least $k$ connected components, and its cost is the sum of its edge costs. Write $λ_k$ for the minimum cost of a $k$-cut. For fixed $k\ge2$ and $α\ge1$, we show that in any $n$-vertex graph with $n\ge k$ and nonnegative edge costs, the number of $k$-cuts of cost strictly below $αλ_k$ is $O(n^{\lceilαk\rceil-1})$. This implies an $O(n^{\lfloorαk\rfloor})$ bound for $k$-cuts of cost at most $αλ_k$, sharpening the $O(n^{αk})$ bound of Gupta, Harris, Lee and Li. For $k=2$, our strict bound resolves a conjecture of Henzinger and Williamson and an open question of Karger. The exponent $\lceilαk\rceil-1$ is optimal for $k$-cuts for every $k\ge2$ and $α>1$.
查看此版本解读 →查看此版本原文 ↗