A phase transition for the metric distortion of percolation on the hypercube (Q949756)

The metric distortion between the hypercube \(H_n\) and its random subgraphs are investigated. Let \(H_{n,p}\) be a graph that one gets by keeping each edge of \(H_n\) with probability \(p\), independently of each other. It was shown by \textit{M.~Ajtai, J.~Komlos} and \textit{E.~Szemerédi} [Combinatorica 2, 1-7 (1982; Zbl 0489.05053)] that for \(p=a/n\) if \(a<1\) then all connected components of \(H_{n,p}\) have size \(poly(n)\), while if \(a>1\) there is a giant component of both size and diameter \(\theta(n)\) with probability tending to 1. \textit{Hastad et al} [Proc. of the 19th ACM Symp. on Theory of Comp. 274-284 (1987)] showed that for constant \(p\) the distortion between \(H_n\) and \(H_{n,p}\) is constant with probability tending to 1. They define the distortion of a map \(f\) between two metric spaces \((X,d_X)\), \((Y,d_Y)\) as \(D(f)=D_+(f)/D_-(f)\), where \[ \begin{aligned} D_+(f) &= 1 \vee \left(\sup_{a, b \in X} d_Y\left(f(a), f(b)/d_X(a, b)\right)\right),\\ D_-(f)&=\inf_{a, b \in X} \left(1 \vee d_Y\left(f(a), f(b)\right)\right)/d_X(a, b)).\end{aligned} \] The distortion between the spaces \(X,Y\) is \(D(X,Y)=\inf_{f:X \rightarrow Y}D(f)\). Then in Theorem 1 they prove the following: Fix \(\alpha\in [0,1]\), and let \(p=n^{-\alpha}\). If \(\alpha<1/2\), then there is some constant \(c=c(\alpha)\) such that \(\text{Pr}(D(H_n,H_{n,p})<c) \longrightarrow 1\), when \(n\rightarrow\infty\). If \(\alpha>1/2\), then there is some constant \(\beta=\beta(\alpha)\) such that \(\text{Pr}(D(H_n,H_{n,p})< n^{\beta}) \longrightarrow 1\), when \(n\rightarrow\infty\).