PreprintCC BY 4.0arXiv
Sharp Bounds on the Number of Small Cuts
Abstract
Let λ be the minimum cut value of an n-vertex undirected multigraph. For every fixed α>1, we prove that there are O(n⌈2α⌉−1) cuts of size strictly below αλ. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.
Related
- Sharp anticanonical volume bounds for Gorenstein Fano fourfold of Picard number one
- Yau's number-theoretic conjecture and sharp spectral bounds for quantum harmonic oscillators
- Sharp Typical Distance and Exponential Small-Ball Bounds in One-Step-Cliff Nielsen Geometry
- Simple Cuts, Simple Landscape: Dimension-Free Rank Bounds for Burer-Monteiro Factorizations via Rank-Width
- Sharp Probabilistic Normwise Backward Error Bounds for LU Factorization
BibTeX
@misc{xu2026sharp,
title = {{Sharp Bounds on the Number of Small Cuts}},
author = {Chao Xu and Mingdong Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10255},
eprint = {2609.10255},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10255},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp Bounds on the Number of Small Cuts
AU - Chao Xu
AU - Mingdong Yang
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10255
UR - https://arxiv.org/abs/2609.10255
AB - Let λ be the minimum cut value of an n-vertex undirected multigraph. For every fixed α>1, we prove that there are O(n^⌈2α⌉−1) cuts of size strictly below αλ. The exponent is sharp. The proof combines splitting off and sampling with a bound on the size of nested families of vertex sets.
ER -