1-skeleton of CAT(0) cube complex is median graph

[latexpage]

I don't know why quicklatex breaks the whole site. You can view the pdf generated by obsidian 🙂

CAT(0)-complex-has-median-1-skeleton

This article just serves to record a proof I came up with of the classic (and very significant, see https://arxiv.org/abs/2309.02070) fact in the title. Whenever a result is cited (written in bold), it is from Farley's article.

Setup: Let X be a locally finite-dimensional CAT(0) cube complex, and let X^{(1)} be its 1-skeleton. We denote vertices by u,v,x,y,z \dots, edges by e, \dots, cubes by C, \dots, and hyperplanes by H,..., and half-spaces by \alpha,\dots

Lemma 0. Every interval
[x,y]\coloneqq{v:v\text{ lies on a geodesic from }x \text{ to }y }
is convex.
Proof. By Proposition 5.5 v\in [x,y] iff v lies in every half-space \alpha\supset{x,y }, so [x,y] is intersection of half-spaces. Half-spaces are convex by Proposition 5.5.

Lemma 1. If x,y are adjacent, then d(x,z)=d(y,z)\pm 1.

Proof. Immediately from the fact that d(x,z) is the same as number of half-spaces containing x but not z.

Lemma 2. For every non-empty convex A\subset X^{(1)} and vertex z, there is a unique \mathrm{proj}_{A}(z)\in A that minimizes the distance to z.

Proof. When z\in A this is trivial. Otherwise if there are x\ne y in A s.t. d(x,z)=d(y,z)=l, we claim by inducting on d(x,y) that there is v\in[x,y] s.t. d(v,z)<l:

When d(x,y)=1 the assumption is impossible by Lemma 1. So base case is d(x,y)=2. Let (x,u,y) be a geodesic. If d(u,z)<l we are done; if not, let H_{x} (H_{y} resp.) be the hyperplane crossing (x,u) ((y,u) resp.). Then x,u,y,z lie in the four quadrants formed by H_{x},H_{y}, as in the assumption of Lemma 5.4. Hence H_{x}\cap H_{y}\ne\emptyset. As (x,u,y) is a geodesic, H_{x}\ne H_{y}, so we can apply Proposition 5.7 to obtain a square C spanned by x,u,y, and let v be the remaining vertex. As v lies in the same quadrant as z, we have d(v,z)=l-1<l.

For general d(x,y)>2 we pick a geodesic (x,x',\dots,y',y). If d(x',z) or d(y',z) is l-1 then we are done. Otherwise d(x',z)=d(y',z)=l+1, so by inductive hypothesis there is v'\in[x',y'] s.t. d(v',z)\le l. If d(v',z)<l we are done, so assume d(v',z)=l, and apply inductive hypothesis to the pair x,v'.

Hence the vertex in A minimizing distance to z must be unique.

Theorem 3. For every non-empty convex A\subset X^{(1)} we have
d(z,x)=d(z,\mathrm{proj}_{A}(z))+d(\mathrm{proj}_{A}(z),x).
Proof. When z\in A this is trivial. Thus we assume z\notin A.

We claim by inducting on d(x,v) that if $v=\mathrm{proj}{[x,v]}(z)\ne z$, then
d(z,x)=d(z,v)+d(v,z).
Base case that d(x,v)=0 is trivial. For general d(x,v)>1, pick a geodesic (v,u,\dots,x), then
d(u,x)=d(v,x)-1\tag{1}.
By Lemma 2 we have d(z,u)\ge d(z,v)+1, while d(z,u)\le d(z,v)+d(v,u)=d(z,v)+1, so
d(z,u)=d(z,v)+1\tag{2}.
Now by Lemma 2 again $u=\mathrm{proj}{[x,u]}(z), so by inductive hypothesisd(z,x)=d(z,u)+d(u,x), so using equations (1) and (2) we getd(z,x)=d(z,v)+d(v,x).

Back to the original statement. Letv=\mathrm{proj}{A}(z); as[x,v]\subset A, we have\mathrm{proj}{[x,v]}(z)=v, sod(z,x)=d(z,v)+d(v,x).

Theorm 4. For everyx,y,z$, there is a unique median m\in [x,y]\cap [x,z]\cap [y,z], i.e. X^{(1)} is a median graph.

Proof. A median is exactly an element m\in [x,y] satisfying d(m,x)+d(m,z)=d(x,z) and d(m,y)+d(m,z)=d(y,z). We claim that a median m must be \mathrm{proj}_{[x,y]}(z).

By Theorem 3 we see that $\mathrm{proj}{[x,y]}(z)is indeed a median. Thus a medianm$ satisfies
2d(m,z)=d(x,z)+d(y,z)-d(x,y)=2d(\mathrm{proj}_{[x,y]}(z),z).
The result then follows from Lemma 2.