A Phase Transition for the Metric Distortion of Percolation on the Hypercube
| dc.creator | Angel, Omer | |
| dc.creator | Benjamini, Itai | |
| dc.date | 2003-06-25 | |
| dc.date.accessioned | 2026-07-07T04:59:10Z | |
| dc.date.available | 2026-07-07T04:59:10Z | |
| dc.description | Let H_n be the hypercube {0,1}^n, and let H_{n,p} denote the same graph with Bernoulli bond percolation with parameter p=n^-α. It is shown that at α=1/2 there is a phase transition for the metric distortion between H_n and H_{n,p}. For α<1/2, asymptotically there is a map from H_n to H_{n,p} with constant distortion (depending only on α). For α>1/2 the distortion tends to infinity as a power of n. We indicate the similarity to the existence of a non-uniqueness phase in the context of infinite nonamenable graphs. | |
| dc.description | 11 pages | |
| dc.identifier | https://arxiv.org/abs/math/0306355 | |
| dc.identifier | http://arxiv.org/abs/math/0306355 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/67873 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 60C05, 05C80, 68R10 | |
| dc.title | A Phase Transition for the Metric Distortion of Percolation on the Hypercube | |
| dc.type | text |