CaltechAUTHORS
Published October 14, 2025 | Version Published
Journal Article Open

Counting minimal cutsets and p_c < 1

Creators

  • 1. ROR icon California Institute of Technology
  • 2. ROR icon University of Lyon System
  • 3. ROR icon ETH Zurich

Abstract

We prove two results concerning percolation on general graphs. We establish the converse of the classical Peierls argument: if the critical parameter for (uniform) percolation satisfies p_c < 1, then the number of minimal cutsets of size n separating a given vertex from infinity is bounded above exponentially in n. This resolves a conjecture of Babson and Benjamini from 1999. We prove that p_c < 1 for every uniformly transient graph. This solves a problem raised by Duminil-Copin, Goswami, Raoufi, Severo, and Yadin, and provides a new proof that p_c < 1 for every transitive graph of superlinear growth.

Copyright and License

© The Author(s), 2025. Published by Cambridge University Press. This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.

Acknowledgement

We are very grateful to Benny Sudakov for telling us about Karger’s algorithm from computer science. This seed is what prompted us to investigate probabilistic approaches to bounding the number of minimal cutsets, ultimately leading to the present work. We thank Itai Benjamini for bringing the 𝜅(𝐺)<∞ question to our attention in the first place. We would also like to thank the anonymous referees for their useful comments on an earlier version of this paper.

Funding

PE is grateful for the hospitality provided by ETH Zurich during this project. This project was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 851565). FS was supported by the ERC grant Vortex (No 101043450).

Files

counting-minimal-cutsets-and-dollarpcless1dollar.pdf

Files (335.0 kB)

Additional details

Related works

Is new version of
Discussion Paper: arXiv:2412.04539 (arXiv)

Funding

European Research Council
851565
European Research Council
101043450

Dates

Accepted
2025-07-31

Caltech Custom Metadata

Caltech groups
Division of Physics, Mathematics and Astronomy (PMA)
Publication Status
Published