Counting minimal cutsets and $p_c<1$

Easo, Philip ; Severo, Franco  ; Tassion, Vincent

Forum of Mathematics, Pi, Tome 13 (2025) no. 1, p. e23

Résumé

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.

Détail

DOI : 10.1017/fmp.2025.10011

Bibliographie

[1] Babson, E. and Benjamini, I., ‘Cut sets and normed cohomology with applications to percolation’, Proc. Amer. Math. Soc. 127(2) (1999), 589–597.10.1090/S0002-9939-99-04995-3 Google Scholar | DOI

[2] Benjamini, I., ‘Coarse geometry and randomness’, Lecture Notes in Mathematics (École d’Été de Probabilités de Saint-Flour), vol. 2100, Springer (2013). Google Scholar

[3] Benjamini, I., Gurel-Gurevich, O., and Morris, B., ‘Linear cover time is exponentially unlikely’, Probab. Theory Relat. Fields 155 (2013), 451–461.10.1007/s00440-011-0403-2 Google Scholar | DOI

[4] Benjamini, I., Lyons, R., and Schramm, O., ‘Percolation perturbations in potential theory and random walks’, Random Walks and Discrete Potential Theory (Cortona, 1997), XXXIX (1999), 56–84. Google Scholar

[5] Benjamini, I. and Schramm, O., ‘Percolation beyond Zd , many questions and a few answers’, Electron. Commun. Probab. 1 (1996), no. 8, 71–82.10.1214/ECP.v1-978 Google Scholar | DOI

[6] Berestycki, N. and Powell, E., ‘Gaussian free field and Liouville quantum gravity’, Preprint, (Cambridge University Press (forthcoming)) (2024), available at . Google Scholar | arXiv

[7] Catlin, P., ‘Supereulerian graphs: A survey’, J. Graph Theory 16 (1992), 177–196.10.1002/jgt.3190160209 Google Scholar | DOI

[8] Contreras, D., Martineau, S., and Tassion, V., ‘Supercritical percolation on graphs of polynomial growth’, Duke Math. J. 173(4) (2024), 745–806.10.1215/00127094-2023-0032 Google Scholar | DOI

[9] Duminil-Copin, H., Goswami, S., Raoufi, A., Severo, F., and Yadin, A., ‘Existence of phase transition for percolation using the Gaussian free field’, Duke Math. J. 169(18) (2020), 3539–3563.10.1215/00127094-2020-0036 Google Scholar | DOI

[10] Dubroff, Q. and Kahn, J., ‘Linear cover time is exponentially unlikely’, Preprint (2021), available at . Google Scholar | arXiv

[11] Gromov, M., ‘Groups of polynomial growth and expanding maps’, Publ. Math. Inst. Hautes Études Sci. 53(1) (1981), 53–78.10.1007/BF02698687 Google Scholar | DOI

[12] Harris, T. E., ‘A lower bound for the critical probability in a certain percolation process’, Proc. Cambridge Philos. Soc. 56 (1960), 13–20.10.1017/S0305004100034241 Google Scholar | DOI

[13] Hermon, J. and Hutchcroft, T., ‘Supercritical percolation on nonamenable graphs: isoperimetry, analyticity, and exponential decay of the cluster size distribution’, Invent. Math. 224(2) (2021), 445–486.10.1007/s00222-020-01011-3 Google Scholar | DOI

[14] Hutchcroft, T., ‘Transience and anchored isoperimetric dimension of supercritical percolation clusters’, Electron. J. Probab. 28 (2023), 1–15.10.1214/23-EJP905 Google Scholar | DOI

[15] Hutchcroft, T. and Tointon, M., ‘Non-triviality of the phase transition for percolation on finite transitive graphs’, J. Eur. Math. Soc. 27(10) (2024), 4283–4346.10.4171/jems/1453 Google Scholar | DOI

[16] Lyons, R., Mann, A., Tessera, R., and Tointon, M., ‘Explicit universal minimal constants for polynomial growth of groups’, J. Group Theory 26(1) (2023), 29–53. Google Scholar

[17] Lyons, R. and Peres, Y., ‘Probability on Trees and Networks’, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 42 (Cambridge Univ. Press, New York, 2016). Google Scholar

[18] Panagiotis, C. and Severo, F., ‘Gap at 1 for the percolation threshold of Cayley graphs’, Ann. Inst. Henri Poincaré Probab. Stat. 59(3) (2023), 1248–1258.10.1214/22-AIHP1286 Google Scholar | DOI

[19] Peierls, R., ‘On Ising’s model of ferromagnetism’, Math. Proc. Cambridge Philos. Soc. 32 (1936), 477–481.10.1017/S0305004100019174 Google Scholar | DOI

[20] Pemantle, R. and Peres, Y., ‘On which graphs are all random walks in random environments transient?’, Random Discrete Structures (Minneapolis, MN, 1993), IMA Vol. Math. Appl. 76, Springer, New York (1996), 207–211.10.1007/978-1-4612-0719-1_14 Google Scholar | DOI

[21] Pete, G., ‘A note on percolation on Zd : isoperimetric profile via exponential cluster repulsion’, Electron. Commun. Probab. 13 (2008), 377–392.10.1214/ECP.v13-1390 Google Scholar | DOI

[22] Tessera, R. and Tointon, M., ‘Sharp relations between volume growth, isoperimetry and escape probability in vertex-transitive graphs’, Preprint (2020), available at . Google Scholar | arXiv

[23] Thomassen, C., ‘Isoperimetric inequalities and transient random walks on graphs’, Ann. Probab. 20(3) (1992), 1592–1600.10.1214/aop/1176989708 Google Scholar | DOI

[24] Timár, Á., ‘Cutsets in infinite graphs’, Combin. Probab. Comput. 16(1) (2007), 159–166.10.1017/S0963548306007838 Google Scholar | DOI

[25] Trofimov, V., ‘Graphs with polynomial growth’, Mat. Sb. (N.S.) 123(165)(3) (1984), 407–421. Google Scholar