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
For finite metric spaces, , but when is infinite, possibly is a proper subset of . Also need not be injective.
Proposition 1 For 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 , 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 2 Call a graph admissible if there exists such that the equality graph of equals . For an admissible graph, define the affine subspace
and 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 3 The rank of an admissible graph is the number of even components of (i.e. connected components containing no odd cycle). If , then is a metric on .
- 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 5 Suppose 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, .