Notes of Urs Lang’s lecture nr 3


1. Polyhedral structure on {E(X)}


From now on, we concentrate on metric spaces whose metric is integer valued (a preparation for the case of finitely generated groups). For simplicity, assume that {X} is countable.


1.1. An approximation to {E(X)}


Recall that the equality graph of an extremal function {f} has vertex set {X} and edge set

\displaystyle  \begin{array}{rcl}  \mathcal{E}(f)=\{\{x,y\}\,;\, f(x)+f(y)=d(x,y)\}. \end{array}


\displaystyle  \begin{array}{rcl}  E'(X)=\{f\in\Delta(X)\,;\,\forall x,\,\exists y \textrm{ such that }\{x,y\}\in\mathcal{E}(f)\} \end{array}

For finite metric spaces, {E(X)=E'(X)}, but when {X} is infinite, possibly {E'(f)} is a proper subset of {E(X)}. Also {E'(f)} need not be injective.

Proposition 1 For all extremal function {f\in E(X)}, and all {m\in{\mathbb N}}, there exists {f'\in E'(X)} with values in {\frac{1}{m}{\mathbb Z}} such that {\|f-f'\|_{\infty}\leq\frac{1}{2m}}.


The strategy is to study {E'(X)}, show that it is complete, and conclude that {E'(X)=E(X)}.

Proof: By rounding. Define {f_0} as the largest function which is {\leq f+\frac{1}{2m}} with values in {\frac{1}{m}{\mathbb Z}}. Then {f_0 >f-\frac{1}{2m}}. Check that {f_0 \in\Delta(X)}: since

\displaystyle  \begin{array}{rcl}  f_0 (x) +f_0 (y)<f(x)+f(y)-\frac{1}{m}\geq d(x,y)-\frac{1}{m}, \end{array}

and {f_0 (x) +f_0 (y)\in\frac{1}{m}{\mathbb Z}}, {f_0 (x) +f_0 (y)\geq d(x,y)}.

Next idea is to decrease {f_0 (x)} at some points {x} where {f_0 (x)=f(x)+\frac{1}{2m}} to make {f_0} extremal. At other points, {f_0 (x)<f(x)+\frac{1}{2m}}. By minimality of {f}, there exists {y} such that

\displaystyle  \begin{array}{rcl}  d(x,y)-f(y)>f_0 (x)-\frac{1}{2m}, \end{array}


\displaystyle  \begin{array}{rcl}  f_0 (x) +f_0 (y) \leq f_0 (x) +f(y)+\frac{1}{2m}<d(x,y)+\frac{1}{m}, \end{array}

so {f_0 (x) +f_0 (y) \leq d(x,y)}, i.e. {\{x,y\}\in\mathcal{E}(f_0)}.

Next assume that {f_0 (x_1)=f(x)+\frac{1}{2m}} and {\{x,y\}\notin\mathcal{E}(f_0)}. Then {f_0 (x) +f_0 (y) > d(x,y)} for all {y}, so {f_0 (x_1) +f_0 (y) \leq d(x,y)+\frac{1}{m}}. So there is room to decrease {f_0} at {x_1}: define

\displaystyle  \begin{array}{rcl}  f_1 (x_1):=f_0 (x_1)-\frac{1}{m}=f(x_1)-\frac{1}{2m}, \end{array}

and, at all other points, {f_1 (y)=f_0 (y)}. {f_1} still belongs to {\Delta(X)}. As above, it follows that if {f_1(x)<f(x)+\frac{1}{2m}}, there exists {y} such that {\{x_1 ,y\}\in\mathcal{E}(f_1)}. So {x_1 \in\bigcup \mathcal{E}(f_1)}.

Iterate the procedure, eventually transfinitely, to get the required approximation. \Box


1.2. The cells of {\mathcal{E}'(X)}


Definition 2 Call a graph {G=(X,\mathcal{E})} admissible if there exists {f\in E'(X)} such that the equality graph {G(f)} of {f} equals {G}. For {G} an admissible graph, define the affine subspace

\displaystyle  \begin{array}{rcl}  H(G)=\{g\in {\mathbb R}^X \,;\,G(f) \textrm{ contains }G,\textrm{ i.e. }g(x)+g(y)=d(x,y)\,\forall\{x,y\}\in\mathcal{E}\} \end{array}

and the convex subset

\displaystyle  \begin{array}{rcl}  P(G):=\Delta(X)\cap H(G)=\{g\in H(G)\,;\,g(x)+g(y)\geq d(x,y)\,\forall\{x,y\}\notin\mathcal{E}\} \end{array}

Note that {f\in P(G(f))}.

Recall that if {g}, {h\in H(G)}, and {x}, {y} are connected by a path of length {L} in {G}, then g(y)-h(y)=(-1)^L (g(x)-h(x)). (we saw this during the informal description last time, but it follows readily from the definition). It follows that if {G} contains an odd cycle, {g=h}. Otherwise, there is one degree of freedom.

Definition 3 The rank {rk(G)} of an admissible graph is the number of even components of {G} (i.e. connected components containing no odd cycle). If {rk(G)<\infty}, then {\|g-h\|_{\infty}} is a metric on {H(G)}.


Proposition 4 Let {G} be an admissible graph of finite rank {rk(G)\geq 1}. Then

  1. There exists an affine isometry {I:H(G)\rightarrow\ell_{\infty}^{n}} such that {I(P(G))} is an {n}-dimensional compact polytope.
  2. The interior of {P(G)} relative to its affine carrier {H(G)} is {\{g\in E'(X)\,;\, G(g)=G\}}.
  3. The face structure of {P(G)} is the family of all {P(G')} with {G'} admissible and {G'} contains {G}.


Proof: 1. Fix an extremal function {f} such that {G=G(f)}. Exploit the fact that even components are bipartite. Fix {x_1 ,\ldots,x_n} representing the vertex sets {[x_1],\ldots,[x_n]} of the even components. For every {k}, there is a partition {[x_k]=[x_{k}]_{1} \cup [x_{k}]_{-1}} where a point {y} belongs to {[x_{k}]_{-1}} iff there exists a path of odd length from {x_k} to {y}. If {y\in[x_{k}]_{\sigma}}, {\sigma=\pm 1}, then {f(y)\in{\mathbb Z} +\sigma f(x_k)}. If {y} belongs to an odd component, then {f(y)\in{\mathbb Z}-f(y)} thus {f(y)\in\frac{1}{2}{\mathbb Z}}. Define {I:H(G)\rightarrow\ell_{\infty}^{n}} by

\displaystyle  \begin{array}{rcl}  I(g)=(g(x_1)-f(x_1),\ldots,g(x_n)-f(x_n)). \end{array}

Identity (1) implies that

\displaystyle  \begin{array}{rcl}  \|g-f\|_{\infty}=\|I(g)-I(f)\|_{\infty} \end{array}

so {I} is an isometry.

2. To describe {I(P(G))}, define constants

\displaystyle  \begin{array}{rcl}  C_{k,\sigma}=\sup\{\frac{d(x,y)-f(y)-f(y)}{2}\,;\,x,\,y\in[x_k]_{\sigma}\}. \end{array}

For {x}, {y\in [x_k]_{\sigma}}, {\{x,y\}\notin\mathcal{E}(f)} so {0>d(x,y)-f(y)-f(y)}. This number belongs to the discrete set {{\mathbb Z}-2\sigma f(x_k)}, so the {\sup} is negative as well. If {y} belongs to an odd cycle, set

\displaystyle  \begin{array}{rcl}  \tilde{C}_{k,\sigma}=\sup\{d(x,y)-f(y)-f(y)\,;\,x\in[x_k]_{\sigma},\,y\in\textrm{ odd cycle}\}. \end{array}

If there are no odd cycles whatsoever, put {\bar{C}_{k,\sigma}=C_{k,\sigma}}. Otherwise, set

\displaystyle  \begin{array}{rcl}  \bar{C}_{k,\sigma}=\max\{C_{k,\sigma},\tilde{C}_{k,\sigma}\}. \end{array}

If {n\geq 2}, then for {1\leq k,\ell\leq n} and {\sigma}, {\tau\in\pm 1},

\displaystyle  \begin{array}{rcl}  C^{\ell,\tau}_{k,\sigma}=.... \end{array}

Claim: {I(P(G))} is the set of all {f\in\ell_{\infty}^{n}} such that

\displaystyle  \begin{array}{rcl}  \sigma f_k &\geq& \bar{C}_{k,\sigma}\\ \sigma f_k +\tau f_{\ell}&\geq& C^{\ell,\tau}_{k,\sigma}.\\ \end{array}

So the number of faces of our polytope is atmost {2n+\begin{pmatrix}n\\ 2\end{pmatrix}=2n^2} faces. I do not know if this upper bound is sometimes achieved.

Proof: of Claim.

\displaystyle  \begin{array}{rcl}  2\sigma f_k = \end{array}

so {\sigma f_k \geq C_{k,\sigma}} iff {g(x)+g(y)\geq d(x,y)} for all such pairs. And so on… \Box

Thats all for the proof of Proposition 4. \Box

Now suppose that {rk(G)} is finite for all admissible graphs. It follows that {\mathcal{P}=\{P(G)\}_{G\,\mathrm{admissible}}} is a polyhedral structure on {E'(X)}, with {P(G')} a face of {P(G)} iff {G\subset G'}.

If {f\in E'(X)} is a vertex of {\mathcal{P}}, then {rk(G(f))=0}, so {f(X)\in\frac{1}{2}{\mathbb Z}}. In particular, edges of {\mathcal{P}} have length in {\frac{1}{2}{\mathbb Z}}.

Proposition 5 Suppose in addition that {X} is discretely geodesic, i.e. there is an isometric embedding of an integer interval joining any two points. Then every edge of {\mathcal{P}} has length at most {2} and for every {n}, {\mathcal{P}} has only finitely many isometry types of {n}-cells.


Proof: Suppose {G} is an admissible graph of rank {1}. Let {x_1} be a representative of the only even cycle {[x_1]}. Since {X} is discretely geodesic, there exist {x}, {y\in X} with {d(x,y)=1} such that {x\in[x_1]_1} and either {y\in[x_1]_{-1}} or {y} does not belong to {[x_1]}. Let {g}, {h\in P(G)}. Then, by (1),

\displaystyle  \begin{array}{rcl}  \|g-h\|_{\infty}=|g(x)-h(x)|. \end{array}

If {y\in[x_1]_{-1}}, {2|g(x)-h(x)|=|g(x)-h(x)-g(y)+h(y)|\leq 2}. Else {y\notin[x_1]}, and it goes similarly. The bound {2} is optimal, as seen from the suspension of a three point set with no edges. \Box


1.3. Why do we need such detailed information ?


To deal with hyperbolic groups. The fact that only finitely many configurations occur for cones types guarantees that admissible graphs have finite rank, and so {E'(X)=E(X)}.

The cone type trick applies to {{\mathbb Z}^n} as well, and yields the upper bound {rk(G)\leq 2^{n-1}}. In fact, {E({\mathbb Z}^n)=E(\ell_{1}^{n})=\ell_{\infty}^{2^{n-1}}}.

More generally, the injective hull of a Banach space is again a Banach space, but in an unobvious way. In case of polyhedral norms, one stays within finite dimensional Banach spaces, but not in general. For instance, {E(\ell_{2}^{n})=L_{\infty}({\mathbb N})}.



About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s