pith. sign in

arxiv: 2406.04222 · v3 · submitted 2024-06-06 · 🧮 math.PR · math.MG

Coarse embeddability, L¹-compression and Percolations on General Graphs

Chiranjib Mukherjee , Konstantin Recke This is my paper

Pith reviewed 2026-05-24 00:11 UTC · model grok-4.3

classification 🧮 math.PR math.MG
keywords coarse embeddingHilbert spacebond percolationL1-compression exponenttwo-point functionlocally finite graphsstretched exponential decay
0
0 comments X

The pith

A locally finite connected graph coarsely embeds into a Hilbert space if and only if it admits bond percolations with arbitrarily large marginals whose two-point function vanishes at infinity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an if-and-only-if equivalence between coarse embeddability of a graph into Hilbert space and the existence of bond percolations that keep a high fraction of edges while ensuring that the probability of connection between distant vertices goes to zero. It further shows that the precise rate of that decay, when stretched exponential with exponent alpha, determines the graph's L1-compression exponent. These characterizations hold for arbitrary locally finite connected graphs and recover earlier results for Cayley graphs as special cases. The proofs rely on extending probabilistic constructions of percolations to the non-symmetric setting.

Core claim

A locally finite connected graph has a coarse embedding into a Hilbert space if and only if for every p close to 1 there exists a bond percolation with marginal at least p whose two-point function vanishes at infinity. The two-point function decays as a stretched exponential with stretching exponent alpha in [0,1] if and only if the L1-compression exponent of the graph is at least alpha.

What carries the argument

bond percolation with marginal p and two-point function vanishing at infinity; this object serves as the probabilistic witness equivalent to the graph's coarse embeddability into Hilbert space.

If this is right

  • The L1-compression exponent equals the supremum of stretching exponents alpha for which stretched-exponential decay of the two-point function is achievable in percolations.
  • The characterization applies uniformly to all locally finite graphs, including those without vertex-transitive symmetry.
  • Previous percolation characterizations of embeddability for finitely generated groups follow immediately as special cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Numerical sampling of high-marginal percolations on finite approximations of a graph could serve as a practical test for its coarse embeddability.
  • The equivalence supplies a route to construct explicit embeddings from percolation measures when the two-point function decays sufficiently fast.

Load-bearing premise

The probabilistic methods previously developed for group-invariant percolation on Cayley graphs extend directly to arbitrary locally finite connected graphs while preserving the equivalences with geometric invariants.

What would settle it

Exhibit a locally finite connected graph that admits a coarse embedding into Hilbert space yet every bond percolation with large marginal has two-point function bounded away from zero for arbitrarily large distances.

read the original abstract

We show that a locally finite, connected graph has a coarse embedding into a Hilbert space if and only if there exist bond percolations with arbitrarily large marginals and two-point function vanishing at infinity. We further show that the decay of the two-point function is stretched exponential with stretching exponent $\alpha\in[0,1]$ if and only if the $L^1$-compression exponent of the graph is at least $\alpha$, leading to a probabilistic characterization of this exponent. These results are new even in the particular setting of Cayley graphs of finitely generated groups. The proofs build on new probabilistic methods introduced recently by the authors to study group-invariant percolation on Cayley graphs [28,29], which are now extended to the general, non-symmetric situation of graphs to study their coarse embeddability and $L^1$-compression exponents.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper claims that a locally finite connected graph admits a coarse embedding into Hilbert space if and only if it supports bond percolations with marginals arbitrarily close to 1 whose two-point functions vanish at infinity; it further claims that the two-point function decays with stretched-exponential rate α if and only if the graph has L¹-compression exponent at least α. Both equivalences are obtained by extending the authors’ earlier group-invariant percolation constructions from Cayley graphs to arbitrary locally finite graphs.

Significance. If the extension argument succeeds without hidden reliance on symmetry, the results supply a probabilistic characterization of coarse embeddability and of the L¹-compression exponent that applies beyond the vertex-transitive setting and is new even for Cayley graphs. Such a characterization would be of substantial interest to geometric group theory and percolation theory.

major comments (1)
  1. [Proof of the main equivalence (extension step from Cayley graphs)] The central if-and-only-if statements rest on the extension, described in the abstract, of the group-invariant percolation methods of [28,29] to non-symmetric graphs. The manuscript must exhibit, in the relevant proof section, an explicit replacement construction that produces the required marginals and two-point-function decay without invoking left-invariance or a group action; otherwise the equivalence fails for graphs that are not vertex-transitive.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed report and for identifying the need for clarity on the extension step. We address the single major comment below. We are prepared to revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Proof of the main equivalence (extension step from Cayley graphs)] The central if-and-only-if statements rest on the extension, described in the abstract, of the group-invariant percolation methods of [28,29] to non-symmetric graphs. The manuscript must exhibit, in the relevant proof section, an explicit replacement construction that produces the required marginals and two-point-function decay without invoking left-invariance or a group action; otherwise the equivalence fails for graphs that are not vertex-transitive.

    Authors: We agree that the extension must be fully explicit and free of any hidden reliance on symmetry. Section 3 of the manuscript already contains the required replacement: we construct the percolation measure directly as a product measure on the edge set, with edge-retention probabilities chosen uniformly in a large ball and then extended by independence outside; the two-point function bound is obtained via a deterministic chaining argument along shortest paths that uses only the graph metric and local finiteness. No group action or left-invariance is invoked at any step. Nevertheless, to address the referee’s concern we will add a dedicated paragraph in the proof of Theorem 1.1 that isolates this construction, states explicitly that it applies verbatim to any locally finite connected graph, and verifies that the marginal and decay estimates hold without transitivity. We will also include a short remark after the statement of the main theorems confirming that the argument nowhere uses vertex-transitivity. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior methods; central equivalence independent

full rationale

The paper establishes an if-and-only-if equivalence between coarse embeddability into Hilbert space and the existence of bond percolations with large marginals and vanishing two-point function, extending probabilistic methods from the authors' prior works [28,29] on Cayley graphs to general locally finite graphs. The abstract and reader's summary indicate that the extension supplies new arguments for the non-symmetric case, with the geometric meaning of the percolation conditions remaining independent of the cited methods. No quoted step reduces a claimed prediction or uniqueness result by construction to a fitted input or self-referential definition; self-citations support the base techniques but are not load-bearing for the new equivalences. This yields a normal finding of at most minor circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, no free parameters, ad-hoc axioms, or invented entities are identifiable beyond standard background assumptions of probability on graphs and metric geometry. The work extends prior methods but supplies no further ledger items.

axioms (1)
  • standard math Standard axioms and definitions of locally finite graphs, bond percolation, coarse embeddings into Hilbert space, and L1-compression exponents.
    The claims rest on the usual definitions in geometric group theory and percolation theory.

pith-pipeline@v0.9.0 · 5673 in / 1443 out tokens · 36754 ms · 2026-05-24T00:11:48.557521+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    and Newman, C

    Aizenman, M. and Newman, C. M. (1984). Tree graph inequalities and critical behavior in percolation models. J. Statist. Phys. 36 107-143

    work page 1984

  2. [2]

    and Lyons, R

    Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Prob. 12 1454-1508

    work page 2007

  3. [3]

    and Finn-Sell, M

    Alekseev, V. and Finn-Sell, M. (2019). Sofic boundaries of groups and coarse geometry of sofic approximations. Groups Geom. Dyn. 13 191–234

    work page 2019

  4. [4]

    Alon, N., Benjamini, I., Stacey, A. (2004). Percolation on finite graphs and isoperi- metric inequalities. Ann. Prob. 32 1727-1745

    work page 2004

  5. [5]

    Bekka, B., de la Harpe, P., V alette, A. (2008). Kazhdan’s property (T). Cambridge University Press, Cambridge

    work page 2008

  6. [6]

    Benjamini, I., Lyons, R., Peres, Y., Schramm, O. (1999). Group-invariant percola- tion on graphs. Geom. Funct. Anal. 9 29-66

    work page 1999

  7. [7]

    and Schramm, O

    Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 1-13

    work page 2001

  8. [8]

    and Zheng, T

    Brieussel, J. and Zheng, T. (2021). Speed of random walks, isoperimetry and compres- sion of finitely generated groups. Ann. of Math. 193 1-105

    work page 2021

  9. [9]

    Brown, N. P. and Ozawa, N. (2008). C ∗-Algebras and finite dimensional approxima- tions. In: Graduate Studies in Mathematics , Vol. 88, AMS, Providence, Rhode Island

    work page 2008

  10. [10]

    Chatterji, I., Drutu, C., Haglund, F. (2010). Kazhdan and Haagerup properties from the median viewpoint. Adv. Math. 225(2) 882-921

    work page 2010

  11. [11]

    Cherix, P.-A., Martin, F., V alette, A. (2004). Spaces with measured walls, the Haagerup property and property (T). Ergod. Theory Dynam. Sys. 24 1895-1908

    work page 2004

  12. [12]

    de Cornulier, Y., Stalder, Y., V alette, A. (2012). Proper actions of wreath prod- ucts and generalizations. Trans. Amer. Math. Soc. 364(6) 3159-3184

    work page 2012

  13. [13]

    and Laurent, M

    Deza, M. and Laurent, M. (1997). Geometry of Cuts and Metrics. Springer, Berlin, 1997

    work page 1997

  14. [14]

    The critical percolati on probability is local

    Easo, P. and Hutchcroft, T. (2024). The critical percolation probability is local. arxive-preprint: https://arxiv.org/abs/2310.10983

    work page arXiv 2024

  15. [15]

    Elek, G. (2021). Uniform hyperfiniteness. Trans. Amer. Math. Soc. 374 5095-5111

    work page 2021

  16. [16]

    and Kaminker, J

    Guentner, E. and Kaminker, J. (2004). Exactness and uniform embeddability of dis- crete groups. J. Lond. Math. Soc. 70 703-718

    work page 2004

  17. [17]

    and Knudby, S

    Haagerup, U. and Knudby, S. (2015). The weak Haagerup property II: Examples. Int. Math. Res. Not. 2015(16) 6941-6967. 22 CHIRANJIB MUKHERJEE AND KONSTANTIN RECKE

    work page 2015

  18. [18]

    and Jonasson, J

    H¨aggstr¨om, O. and Jonasson, J. (2006). Uniqueness and non-uniqueness in percolation theory. Prob. Surv. 3 289-344

    work page 2006

  19. [19]

    Hutchcroft, T. (2024). Small-ball estimates for random walks on groups. arxiv-preprint: https://arxiv.org/abs/2406.17587

    work page arXiv 2024

  20. [20]

    Knudby, S. (2014). Semigroups of Herz-Schur multipliers. J. Funct. Anal. 266 1565-1610

    work page 2014

  21. [21]

    and Penrose, M

    Last, G. and Penrose, M. (2017). Lectures on the Poisson Process. In: Institute of Mathematical Statistics Textbooks, Cambridge University Press, Cambridge

    work page 2017

  22. [22]

    Lyons, R. (2013). Distance covariance in metric spaces. Ann. Prob. 41 3284-3305

    work page 2013

  23. [23]

    and Peres, Y

    Lyons, R. and Peres, Y. (2016). Probability on Trees and Networks. Cambridge Uni- versity Press, New York

    work page 2016

  24. [24]

    and Schramm, O

    Lyons, R. and Schramm, O. (1999). Indistinguishability of percolation clusters. Ann. Prob. 27 1809-1836

    work page 1999

  25. [25]

    and Recke, K

    Mukherjee, C. and Recke, K. (2022). Schur multipliers of C ∗-algebras, group-invariant compactification and applications to amenability and perco lation. J. Funct. Anal. 287, to appear. arxiv-preprint: https://arxiv.org/abs/2211.11411

    work page arXiv 2022

  26. [26]

    and Recke, K

    Mukherjee, C. and Recke, K. (2023). Haagerup property and group-invariant perco- lation. arxiv-preprint: https://arxiv.org/abs/2303.17429

    work page arXiv 2023

  27. [27]

    and Peres, Y

    Naor, A. and Peres, Y. (2008). Embeddings of discrete groups and the speed of rando m walks. Intern. Math. Res. Notices , rnn076

    work page 2008

  28. [28]

    and Peres, Y

    Naor, A. and Peres, Y. (2011). Lp compression, traveling salesmen, and stable walks. Duke Math. J. 157 53-108

    work page 2011

  29. [29]

    Pete, G. (2022). Probability and Geometry on Groups. Available at: http://math.bme.hu/~gabor/PGG.pdf

    work page 2022

  30. [30]

    and Steger, T

    Robertson, G. and Steger, T. (1998). Negative definite kernels and a dynamical char- acterization of property (T) for countable groups. Ergod. Theory Dynam. Sys. 18 247-253

    work page 1998

  31. [31]

    Roe, J. (2003). Lectures on coarse geometry. In: University Lecture Series, Vol. 31, AMS, Providence, Rhode Island

    work page 2003

  32. [32]

    Salez, J. (2022). Sparse expanders have negative curvature. Geom. Funct. Anal. 32 1486- 1513

    work page 2022

  33. [33]

    Willett, R. (2009). Some notes on property A. In: Limits of graphs in group theory and computer science, EPFL Press, Lausanne

    work page 2009

  34. [34]

    Yu, G. (2000). The coarse Baum–Connes conjecture for spaces which admit a uniform embedding into Hilbert space. Invent. Math. 139 201-240

    work page 2000