**1. Polyhedral structure on **

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 is countable.

** 1.1. An approximation to **

Recall that the equality graph of an extremal function has vertex set and edge set

Define

For finite metric spaces, , but when is infinite, possibly is a proper subset of . Also need not be injective.

Proposition 1For all extremal function , and all , there exists with values in such that .

The strategy is to study , show that it is complete, and conclude that .

*Proof:* By rounding. Define as the largest function which is with values in . Then . Check that : since

and , .

Next idea is to decrease at some points where to make extremal. At other points, . By minimality of , there exists such that

so

so , i.e. .

Next assume that and . Then for all , so . So there is room to decrease at : define

and, at all other points, . still belongs to . As above, it follows that if , there exists such that . So .

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

** 1.2. The cells of **

Definition 2Call a graphadmissibleif there exists such that the equality graph of equals . For an admissible graph, define the affine subspaceand the convex subset

Note that .

Recall that if , , and , are connected by a path of length in , 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 contains an odd cycle, . Otherwise, there is one degree of freedom.

Definition 3Therankof an admissible graph is the number of even components of (i.e. connected components containing no odd cycle). If , then is a metric on .

Proposition 4Let be an admissible graph of finite rank . Then

- There exists an affine isometry such that is an -dimensional compact polytope.
- The interior of relative to its affine carrier is .
- The face structure of is the family of all with admissible and contains .

*Proof:* 1. Fix an extremal function such that . Exploit the fact that even components are bipartite. Fix representing the vertex sets of the even components. For every , there is a partition where a point belongs to iff there exists a path of odd length from to . If , , then . If belongs to an odd component, then thus . Define by

Identity (1) implies that

so is an isometry.

2. To describe , define constants

For , , so . This number belongs to the discrete set , so the is negative as well. If belongs to an odd cycle, set

If there are no odd cycles whatsoever, put . Otherwise, set

If , then for and , ,

**Claim**: is the set of all such that

So the number of faces of our polytope is atmost faces. I do not know if this upper bound is sometimes achieved.

*Proof:* of Claim.

so iff for all such pairs. And so on…

Thats all for the proof of Proposition 4.

Now suppose that is finite for all admissible graphs. It follows that is a polyhedral structure on , with a face of iff .

If is a vertex of , then , so . In particular, edges of have length in .

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

*Proof:* Suppose is an admissible graph of rank . Let be a representative of the only even cycle . Since is discretely geodesic, there exist , with such that and either or does not belong to . Let , . Then, by (1),

If , . Else , and it goes similarly. The bound is optimal, as seen from the suspension of a three point set with no edges.

** 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 .

The cone type trick applies to as well, and yields the upper bound . In fact, .

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, .