10
$\begingroup$

I have a family of possibly related questions. Let me start with an elementary one:

Question 1. Fix an integer $n$. For which collections of real numbers $a_{ij}$, $i, j = 1, \dots, n$, is it true that, for all trees $T$ and points $x_1, \dots, x_n$ in $T$, $$ \sum_{i<j} a_{ij} d(x_i, x_j)^2 > 0? \tag{1} $$

That is, I want to characterize the quadratic length inequalities that hold in trees.

A related fact (if you drop "quadratic") is that a set of distances $d_{ij}$ can be realized inside a tree iff the $d_{ij}$ satisfy $$ d_{ik} + d_{jl} \le \max(d_{ij} + d_{kl}, d_{il} + d_{jk}) $$ for all $i,j,k,l$. (If you take $j=l$ you recover the triangle inequality.)

But any quadratic relation as above will also hold for a product of trees (using the Euclidean-like product metric). In particular, it will also hold for Euclidean spaces. For Euclidean spaces, the inequality $(1)$ holds iff the matrix with off-diagonal entries $-a_{ij}$ and rows summing to $0$ is positive semi-definite. But not all such inequalities hold for trees.

Examples. For any points $x_1,\dots,x_4$ in a metric space, $ 2 d_{12}{}^2 + 2d_{13}{}^2 \ge d_{23}{}^2. $ This follows from the triangle inequality, and the corresponding matrix $$ \pmatrix{4&-2&-2\\-2&1&1\\-2&1&1} $$ is positive semi-definite. Likewise the four-point inequality $$ d_{13}{}^2 + d_{24}{}^2 \le d_{12}{}^2 + d_{23}{}^2 + d_{34}{}^2 + d_{14}{}^2 \tag{2} $$ is true in any tree. But the inequality $$ 3(d_{14}{}^2 + d_{24}{}^2 + d_{34}{}^2) \ge d_{12}{}^2 + d_{23}{}^2 + d_{13}{}^2 \tag{3} $$ is true for Euclidean spaces, but not for trees. (Take a tripod, where $x_4$ is the central point of the tripod and the other three points are on different branches.) The best such inequality that is true for trees is $$ 4(d_{14}{}^2 + d_{24}{}^2 + d_{34}{}^2) \ge d_{12}{}^2 + d_{23}{}^2 + d_{13}{}^2. \tag{4} $$

Given that any inequality satisfying $(1)$ will also hold for products of trees, it is natural to ask about CAT(0) spaces as well.

Question 2. Which inequalities of the form $(1)$ hold for CAT(0) spaces? More generally, what length inequalities characterize when a finite set of points can be embedded in a CAT(0) space?

You could also ask the questions in a dual form.

Question 3. Which squared pairwise distances occur between a finite subset of a CAT(0) space? (This is a convex subset of $\mathbb{R}^{n(n-1)/2}$.)

For all the questions, I'm looking for a "nice" description, along the lines of the positive semi-definite description for Euclidean spaces.

It's worth mentioning that Berg and Nikolaev [Geom. Dedicata (2008) 133:1995-218)] proved that inequality $(2)$ characterizes CAT(0) spaces among geodesic metric spaces. But that inequality is not enough to guarantee that even a set of 4 points is embeddable in a CAT(0) space.

Update: It appears that Question 2 is a known hard question. But it also appears that Question 1 and Question 2 are different, although the stated reference gives only the barest sketch of a proof; I'd like to see some explicit example. I'm also most interested in Question 1.

$\endgroup$
3
  • 1
    $\begingroup$ Do you have a full answer to question 1 for small values of $n$? is the set of solutions a polyhedral cone? What are its extremal rays? $\endgroup$
    – YCor
    Apr 22, 2014 at 15:04
  • $\begingroup$ I don't know a full answer to question 1 even for $n=4$, though possibly the answer is in a paper of Gromov (CAT(k)-Spaces: Construction and Concentration, Journal of Mathematical Sciences Vol. 119, 2004). It is a semi-algebraic set which is not polyhedral even for $n=3$, like the cone of positive semi-definite matrices. The extremal rays come from lengths on metric trees, almost by definition. $\endgroup$ Apr 22, 2014 at 20:52
  • $\begingroup$ Is there really no more detail here? It's hard for me to believe that no one has thought much about this. $\endgroup$ Apr 27, 2014 at 14:27

1 Answer 1

5
$\begingroup$

These are open questions, but there are some partial answers. Check section 7 in our Alexandrov meets Kirszbraun.

Postscript. More partial answers in our Bipolar comparison and you may also check Quest for 5-point condition a la Alexandrov and Trees meet octahedron comparison; the latter gives an intersting condition that holds in product of trees.

$\endgroup$
5
  • $\begingroup$ Thanks! In that paper, you comment that "the set of metrics which can be embedded in a product of trees and hyperbolic spaces admits a simple description". This seems like it answers my Question 1, but you don't seem to give the explicit answer; is it written anywhere? $\endgroup$ Apr 18, 2014 at 1:27
  • $\begingroup$ Close, but not the same. We ment something like that: mathoverflow.net/questions/7794/ (you will not need the consition on rank. For Lobachevsky space or sphere you need to use hyperbolic/spherical cosine rule instead.) $\endgroup$ Apr 18, 2014 at 2:03
  • $\begingroup$ I know how to characterize embeddings in Euclidean, hyperbolic, or spherical spaces (I mention the Euclidean case in my question), but I don't know how to characterize embeddings in products of such; can you explain a little? $\endgroup$ Apr 18, 2014 at 3:22
  • $\begingroup$ @Anton Petrunin : In the paper "quest for 5-point condition a la Alexandrov", for a three points $x_i$, define a matrix $f(v)=(Wv,v)$ where $W$ is a linear map on $\mathbb{R}^3$ : If $e_i$ is a canonical basis on $\mathbb{R}^3$, then $W(e_1+e_2+e_3)=0$ and $f(e_i-e_j)={\rm dist}\ (x_i,x_j)^2$. Then $W\geq 0$ i.e. positive definite iff $x_i$ satisfies the triangle inequality. How can we prove this ? (There is no hint) For me, direct computation is not easy. It is a direct computation ? $\endgroup$ Aug 12, 2018 at 2:33
  • 1
    $\begingroup$ @HeeKwonLee it should be $\mathbb{R}^2$, not $\mathbb{R}^3$. If $W>0$ then it defines a Euclidean metric on $\mathbb{R}^2$ and if $W\ge 0$ the metric might degenerate to a line or one-point set. In all the cases the triangle inequality holds. In the opposite direction if all triangle inequalities hold then you can embed the triple in the plane, therefore $W\ge 0$. $\endgroup$ Aug 12, 2018 at 2:58

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.