Coarse embeddability, $L^1$-compression and Percolations on General Graphs

Chiranjib Mukherjee; Konstantin Recke

Coarse embeddability, $L^1$-compression and Percolations on General Graphs

T0 review · 1 major / 0 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict The paper gives if-and-only-if links between coarse embeddability into Hilbert space (and the L1-compression exponent) and the existence/decay of bond percolations on arbitrary locally finite graphs, extending the authors' earlier invariant-percolation work. read the letter →

arxiv 2406.04222 v3 submitted 2024-06-06 math.PR math.MG

Chiranjib Mukherjee , Konstantin Recke This is my paper · ORCID

classification math.PRmath.MG

keywords coarseembeddingHilbertspacebondpercolationL1-compressionexponenttwo-pointfunctionlocallyfinitegraphsstretchedexponentialdecay

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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.

Watch

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main point is that a locally finite connected graph coarsely embeds into Hilbert space precisely when there are bond percolations with marginals approaching 1 whose two-point function vanishes at infinity, and the decay rate of that function characterizes the L1-compression exponent. These equivalences are stated to be new even for Cayley graphs, so the work supplies a probabilistic translation of two standard geometric invariants. That is the concrete advance. The proofs adapt the authors' recent group-invariant percolation techniques to the non-symmetric setting, which is the step that makes the claims apply to general graphs rather than just vertex-transitive ones. If that adaptation is carried through without tacitly relying on left-invariance to control marginals or correlations, the equivalences are logically strong and could let people import percolation tools into coarse geometry questions. The soft spot is exactly the extension step flagged in the stress test. Without symmetry, the usual constructions via invariant random subgraphs or factors of IID are unavailable, so the paper must supply a different argument that still produces the required decay from the embedding (or vice versa). The abstract asserts the extension succeeds, but the details of how the two-point function is controlled on non-transitive graphs are the part that needs checking; a gap there would make the equivalences fail for graphs that are not vertex-transitive. The rest of the paper appears to build cleanly on the cited prior works without circularity or invented entities. This is for readers in coarse geometry and geometric group theory who already follow percolation methods. It is worth sending to a serious referee because the claimed equivalences are sharp, the topic is central, and the probabilistic reformulation is not a routine restatement of existing results.

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)

[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

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 · score 2.0 of 10

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.

Assumptions & free parameters 0 free parameters · 1 assumptions · 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.

assumptions (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.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Coarse embeddability, $L^1$-compression and Percolations on General Graphs." pith.science (2026). https://pith.science/paper/2406.04222

@misc{pith2026240604222,
  author       = {Pith},
  title        = {Pith review of: Coarse embeddability, $L^1$-compression and Percolations on General Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2406.04222}},
  note         = {Machine review of arXiv:2406.04222}
}

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

[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]

and Lyons, R

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

work page 2007
[3]

and Finn-Sell, M

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

work page 2019
[4]

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

work page 2004
[5]

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

work page 2008
[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]

and Schramm, O

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

work page 2001
[8]

and Zheng, T

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

work page 2021

Show all 34 references

[9]

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

2008
[10]

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

2010
[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

2004
[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

2012
[13]

and Laurent, M

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

1997
[14]

and Hutchcroft, T

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

2024
[15]

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

2021
[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

2004
[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

2015
[18]

and Jonasson, J

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

2006
[19]

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

2024
[20]

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

2014
[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

2017
[22]

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

2013
[23]

and Peres, Y

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

2016
[24]

and Schramm, O

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

1999
[25]

and Recke, K

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

2022
[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

2023
[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

2008
[28]

and Peres, Y

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

2011
[29]

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

2022
[30]

and Steger, T

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

1998
[31]

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

2003
[32]

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

2022
[33]

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

2009
[34]

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

2000

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.

[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). Soﬁc boundaries of groups and coarse geometry of soﬁc approximations. Groups Geom. Dyn. 13 191–234

work page 2019

[4] [4]

Alon, N., Benjamini, I., Stacey, A. (2004). Percolation on ﬁnite 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 ﬁnite 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 ﬁnitely generated groups. Ann. of Math. 193 1-105

work page 2021