Let \(C_{n}\) be the \(n\) -dimensional hypercube (hence \(|V(C_{n})| = 2^n\)). Let \(\{ (X_{n}, d_{n})\}\) be a sequence of finite graphs with the standard graph metric.
Then there exists some wall metric \(d_{w}\) on \(X\) such that \((X,d)\) is coarsely equivalent to \((X, d_{w})\) if and only if \((X,d)\) is coarsely embeddable into a coarse disjoint union of hypercubes.
Some notation:
- \(A\sim_{c.eq.} B\) means \(A\) is coarsely equivalent to \(B\).
- \(A\sim_{c.em.} B\) means \(A\) is coarsely embeddable into \(B\).
If there exists a wall metric on \(X\) such that \((X,d) \sim_{c.eq.} (X, d_{w})\) then, by Deza Proposition~4.2.2 \((X,d) \sim_{c.em.} (\tilde{C},d)\) since for each \(n \in \mathbb{N}\), \((X_{n}, d_{w})\) is isometrically embeddable into \((C_{m})\) for some \(m \in \mathbb{N}\).
Outline of the proof of the second implication: By assumption, \((X,d)\sim_{c.em.} (C,d)\). We use the embedding map \(f:X \to C\) and the fact that each hypercube embeds isometrically into \(\ell^1\) to create a set of walls on \(X_{n}\) such that for all \(x,y \in X_{n}\), \(d_{w}(x, y) = d_{C}(f(x), f(y))\). How this is achieved: By embedding \(f(X_{n})\) into \(\ell^1\) we get vectors of a fixed length \(m\) with binary entries. Then we create \(m\) subsets of \(S_{k} \subseteq V(X_{n})\) by selecting all vertices \(x \in X_{n}\) whose \(k^{th}\) coordinate in the \(\ell^1\) embedding of \(f(x)\) is \(1\).
Let \((X,d)\sim_{c.em.} (C,d)\) where \(C\) is a coarse disjoint union of a sequence \(\{ (C_{n},d_{n}) \}_{n \in \mathbb{N}}\) of hypercubes each equipped with the standard graph metric. Note that in this notation, \(n\) is not necessarily the dimension of the hypercube.
Let \(f\) be the embedding map from \(X\) to \(C\). Let \(Y_{n}:= f(X_{n}) \subseteq C_{n}\) and \(Y = \bigsqcup_{n \in \mathbb{N}} Y_{n}\). Then \((X,d)\sim_{c.eq.} (Y,d)\).
All \(y \in Y\) can be represented by a vector \((y_{1}, y_{2},\ldots,y_{m})\) whose entries are in \(\{ 0,1 \}\) for some \(m \in \mathbb{N}\) dependent on \(n\). If \(x, y \in Y_{n}\) then, by Deza Proposition 4.2.4, \[ \left\| (x_{1}, x_{2},\ldots,x_{m})-(y_{1}, y_{2},\ldots,y_{m})\right\|_{1} = d_{Y}(x,y). \]
Let \(N_{n}\) be the number of vertices in the cube \(C_{n}\). For each \(n \in \mathbb{N}\) and \(i \in \{ 1,2,\ldots,N_{n} \}\) define \[ S^n_{i} = \{ x : x \in X_{n}, f(x)_{i} = 1 \} \] where \(f(x)_{i}\) is the \(i^{th}\) coordinate of the vector which is the \(\ell^1\) embedding of \(f(x)\).
Each \(S^n_{i}\) defines a wall on \(X_{n}:\) \[ w^n_{i} = \{(u,v) : (u,v) \in E(X_{n}), u \in S^n_{i}, v \not\in S^n_{i}\}. \]
If \(x,y \in X_{n}\), \(d_{w}(x,y) = |\{ S^n_{i} : f(u) \in S^n_{i}, f(v) \not\in S^n_{i} \} | = d_{Y}(f(x), f(y))\). Define \(d_{w}(X_{i}, X_{j}) = d_{C}(X_{i}, X_{j})\).
If \(\rho_{-}, \rho_{+}\) are the coarse embedding functions for \(f\) then
\begin{align*} & \rho_{-}(d_X (x,y)) \leq d_{Y}(f(x), f(y)) \leq \rho_{+}(d_X (x,y)) & \text{ by assumption.} \\ & \rho_{-}(d_X (x,y)) \leq d_{w}(x, y) \leq \rho_{+}(d_X (x,y)) & \text{ by above.}\\ \end{align*}