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.

  • $\begingroup$ @YCor: I made the question explicit. I hope this is precise enough now. $\endgroup$
    – ouimerci
    Jan 26, 2019 at 14:35
  • $\begingroup$ Chepoi-Hagen stable link: doi.org/10.1016/j.jctb.2013.04.003 $\endgroup$
    – YCor
    Jan 26, 2019 at 15:58

2 Answers 2


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.

  • $\begingroup$ 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 ? $\endgroup$
    – ouimerci
    Jan 26, 2019 at 15:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.