New sharp limits found on number of small graph cuts
Sharp Bounds on the Number of Small Cuts
Discrete Mathematics
Summary
This paper studies how many small 'cuts' can exist in a network where a cut is a way to split the network into parts by removing connections. The authors found exact upper bounds on the number of such small cuts depending on the network size and a size factor. They combined known techniques like splitting off and sampling to prove these tight limits. This helps in understanding the structure and complexity of networks better.
What this means in practice
- •For network engineers: Design network reliability checks that use exact bounds on the number of critical small cuts to optimize fault tolerance.
- •For graph algorithm developers: Use the sharp bounds on small cuts to improve algorithms for network partitioning and flow problems.
A theory result. No direct application yet.
Authors
Chao Xu, Mingdong Yang
Abstract
Let $λ$ be the minimum cut value of an $n$-vertex undirected multigraph. For every fixed $α>1$, we prove that there are $O(n^{\lceil2α\rceil-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.