# Can all countable $CAT(0)$ cube complexes be isometrically embedded in $l^1(\mathbb{N},\mathbb{R})$?

In this paper (theorem 2), Chepoi & Hagen say

There exists an infinite $$CAT(0)$$ cube complex $$X$$ with constant maximum degree which cannot be isometrically embedded into a Cartesian product of a finite number of trees, i.e., the chromatic number of its crossing graph is infinite.

so that you can't hope to isometrically embed it in a $$\mathbb{R}^n$$ with $$l^1$$ metric. But what about $$l^1(\mathbb{N})$$:

Question 1: Under what conditions does a $$CAT(0)$$ cube complex, with the "polyhedral complex" metric induced by the $$l^1$$ metric on cubes, embed in $$l^1(\mathbb N)$$ ?

Question 2: Same question but only about embedding the $$0$$ skeleton of said complex.

My reason for the question is the following: It is known that the $$0$$-skeleton of a $$CAT(0)$$ cube complex is a median space, and intuitively it makes sense since it looks a lot like a nice subset of $$\mathbb{Z}^n$$ for some $$n$$ big enough, which is itself median. I'm therefore wondering if you could prove median-ness of this $$0$$-skeleton by embedding your complex in $$l^1(\mathbb{N})$$, and then arguing that the embedding is actually submedian, or whatever allows you to argue median-ness back for the skeleton.

EDIT: added the obvious "countable" condition. Then an obvious embedding would be to enumerate the vertices and send them to the "basis" of $$l^1$$ … I wonder if/where that would break.

• @YCor: I made the question explicit. I hope this is precise enough now. Jan 26, 2019 at 14:35
– YCor
Jan 26, 2019 at 15:58

All CAT(0) cube complexes $$C$$ with $$\ell^1$$-metric embed isometrically into $$\ell^1$$. If the set of vertices is countable, one can choose $$\ell^1$$ of a countable set.

Indeed, say that a subset $$B$$ of the vertex set $$V_C$$ of $$C$$ is (totally) convex if it contains vertices of all geodesic paths between any two elements of $$B$$. Call it $$B$$ "biconvex" if both $$B$$ and its complement in $$V_C$$ are convex. (It's usually called "halfspace" but I don't think it's a good choice of terminology.) Let $$\mathcal{B}$$ be the set of biconvex subset. For every oriented edge $$(x,y)$$, there exists a unique $$B=B_{x,y}\in\mathcal{B}$$ such that $$y\in B$$ and $$x\notin B$$ (namely $$B_{x,y}=\{z\in V_C:zy\le zx\}$$). It is known that all biconvex subsets have this form. This shows that the cardinal of $$\mathcal{B}$$ is bounded above by the cardinal of $$V_C$$ (if infinite).

An isometric embedding $$f$$ of $$C$$ into $$\ell^1(\mathcal{B})$$ consists in the following: for $$x\in C$$, let $$\mathcal{B}(x)$$ be the set of biconvex subsets containing $$x$$. Fix a vertex $$x_0$$; map $$x\in V_C$$ to $$f(x)=1_{\mathcal{B}(x)}-1_{\mathcal{B}(x_0)}$$. Here we endow $$\mathcal{B}$$ with the atomic measure for which singletons have measure $$1/2$$, so that $$f$$ is an isometric embedding: indeed for all $$x,y\in V_C$$, each of $$\mathcal{B}(x)\smallsetminus \mathcal{B}(y)$$ and $$\mathcal{B}(y)\smallsetminus \mathcal{B}(x)$$ have exactly $$xy$$ elements. It is not hard to check that $$f$$ has a canonical affine extension to cells.

• Mmh, that's a nice argument. I assume for vertices $x,y$, $xy$ means the distance from $x$ to $y$ ? Also, is that a standard kind of argument ? Jan 26, 2019 at 15:12
• Yes it's indeed standard. One reference is my survey arxiv.org/abs/1302.5982 : essentially Corollary 7C5 is the same. I'm not sure of an earliest reference: this was rather often done with unnecessary extra-assumptions such as finiteness assumptions on the complex, or equivariance with respect to a group action with some properties, etc.
– YCor
Jan 26, 2019 at 15:56

From the point of view of graph theory, it is well known that median graphs (i.e. one-skeleta of CAT(0) cube complexes) embeds isometrically in Hamming cubes. An approach I like uses restricted quotients, which have other nice applications.

Restricted quotients. Given a CAT(0) cube complex $$X$$ and a collection of hyperplanes $$\mathcal{J}$$, define the pseudo-metric $$d_\mathcal{J} : X^{(0)} \times X^{(0)} \to \mathbb{N}$$ as $$(x,y) \mapsto \text{number of hyperplanes in \mathcal{J} separating x,y.}$$ The restricted quotient $$X_\mathcal{J}$$ is the cube complex obtained by cubulating the wallspace $$(X, \mathcal{J})$$. Such a cube complex can be defined in many different ways, but the key point to keep in mind is that its vertex-set is the quotient of $$X^{(0)}$$ by the equivalence relation: $$x \sim_\mathcal{J} y$$ if $$d_\mathcal{J}(x,y)=0$$.

For instance, start from the dual graph $$\Gamma$$ of $$X \backslash \bigcup_{J\in \mathcal{J}} J$$, i.e. the graph whose vertices are the connected components of $$X \backslash \bigcup_{J\in \mathcal{J}} J$$ and whose edges link two components if they are separated by a unique hyperplane. Then $$X_\Gamma$$ coincides with the cube complex obtained from $$\Gamma$$ by filling in all the subgraphs isomorphic to one-skeleta of $$k$$-cubes with $$k$$-cubes for every $$k \geq 2$$.

There is clearly a surjective map $$\pi_\mathcal{J} : X \twoheadrightarrow X_\mathcal{J}$$ (obtained by sending each vertex of $$X$$ to the vertex of $$X_\mathcal{J}$$ corresponding to the component that contains $$x$$). Moreover, $$d_{X_\mathcal{J}}(\pi_\mathcal{J}(x),\pi_\mathcal{J}(y)) = d_\mathcal{J}(x,y) \text{ for all vertices x,y \in X.}$$ (Here, my cube complexes are endowed with $$\ell^1$$-metrics.)

Constructing embeddings. Because the distance in $$X$$ between any two vertices coincides with the number of hyperplanes that separate them, it follows that, for every partition $$\{ \mathcal{J}_i, \ i \in I\}$$ of the hyperplanes of $$X$$, then $$\bigoplus\limits_{i \in I} \pi_{\mathcal{J}_i} : X \to \bigoplus\limits_{i \in I} X_{\mathcal{J}_i}$$ is an isometric embedding of $$X$$ into a product of CAT(0) cube complexes (namely, the restricted quotients).

Application 1: If our partition is $$\{ \{J\}, \text{ J hyperplane}\}$$, then each restricted quotient is a single edge and one obtains an isometric embedding of $$X$$ into an infinite-dimensional cube $$[0,1]^I$$.

Application 2: Let $$\Delta X$$ denote the crossing graph of $$X$$, i.e. the graph whose vertices are the hyperplanes of $$X$$ and whose edges link two hyperplanes if they are transverse. Let $$\chi$$ denote the chromatic graph of $$\Delta X$$. By considering the partition of the hyperplanes of $$X$$ induced by a coloring of $$\Delta X$$ with $$\chi$$ colors, one obtains an isometric embedding of $$X$$ into a product of $$\chi$$ simplicial trees.