Representabilidad de espacios métricos finitos

Question

Recientemente se han planteado un par de preguntas sobre los espacios métricos, lo que me ha hecho pensar un poco en los teoremas de representación de los espacios métricos finitos.

Supongamos que $X$ es un conjunto dotado de una métrica $d$ . Inicialmente había supuesto que debía haber un $n$ tal que $X$ se incrusta isométricamente en $\mathbb{R}^n$ pero el siguiente ejemplo muestra que esto no funciona del todo bien:

Tome por $X$ el conjunto de vértices de cualquier grafo, y sea $d(x,y)$ sea la longitud (en pasos) del camino más corto que une $x$ a $y$ . Entonces, para un camino mínimo que conecte $x$ a $y$ la trayectoria debe corresponder a una línea recta en $\mathbb{R}^n$ . Esto se debe a que $\mathbb{R}^n$ tiene la propiedad de que la igualdad en la desigualdad triangular implica colinealidad.

Tomemos un gráfico tal que $x$ y $y$ tienen $d(x,y) \geq 2$ y dos caminos mínimos entre ellos; un simple cuadrado antiguo servirá. Cada uno de los dos caminos mínimos debe asignarse a la misma línea en $\mathbb{R}^n$ por lo que el mapa no puede ser una isometría (ni siquiera una incrustación).

Esto nos da una obstrucción a la representabilidad: un espacio métrico finito no puede ser representable a menos que satisfaga la propiedad $d(x,y) = d(x,z) + d(z,y) \wedge d(x,y) = d(x,z') + d(z',y) \wedge d(x,z) = d(x,z') \implies z = z'$ . En el caso de los grafos, esto significa "caminos más cortos únicos"; no tengo claro si existe una caracterización rápida de este tipo en el caso general.

Pregunta nº 1: ¿Es éste el único obstáculo a la representabilidad?

En una dirección ligeramente diferente, se podría evitar el problema anterior tratando de representar los espacios métricos finitos en alguna superficie en lugar de $\mathbb{R}^n$ . Al menos en el caso de los grafos, esto funciona sustituyendo los puntos por pequeños discos y las aristas por cintas muy gruesas de longitud 1. Luego, al compactar todo el conjunto, se obtiene una superficie en la que el grafo se inserta isométricamente. Esto sugiere la respuesta a

Pregunta nº 2a: ¿Tiene todo espacio métrico finito una representación en una superficie?

es sí, siempre que la respuesta a

Pregunta nº 2b: ¿Tiene todo espacio métrico finito una escala global que incrusta $\epsilon$ -isométricamente en un gráfico?

también es sí. En $\epsilon$ es ocuparse de los espacios métricos finitos con distancias irracionales.

Por supuesto, también está la importante

Pregunta nº 0: ¿Hay algún lugar estándar donde debería haber buscado todo esto?

Answer 1

Dado que el artículo al que hace referencia Hagen Knaf ha sido publicado por Springer, es posible que no esté disponible para todos. La referencia (públicamente visible) en MathSciNet es: MR355836 .

Es un artículo muy corto (7 páginas) y el teorema principal es:

Teorema Un espacio métrico puede incrustarse en el espacio euclídeo n si y sólo si el espacio métrico es plano y de dimensión menor o igual que n.

Es evidente que hay que ampliar los términos "plano" y "dimensión". Para definirlos, Morgan considera símplices en el espacio métrico; es decir, un n-simplex es simplemente una (n+1)-tupla ordenada de elementos del espacio métrico. Dada una n-tupla, digamos $(x_0, \dots, x_n)$ Morgan define $D(x_0,\dots,x_n)$ es el determinante de la matriz cuya $(i,j)$ a entrada es

$$ \frac{1}{2}\left(d(x_0,x_i)^2 + d(x_0,x_j)^2 - d(x_i,x_j)^2\right) $$

Un espacio métrico es plano si ésta es positiva para todas las símplices. Si es plana, su dimensión (si existe) es el mayor n para el que existe un n-simplex con esta cantidad positiva.

El argumento (en una lectura rápida) es bastante astuto. En lugar de optar por una incrustación de una sola vez, Morgan define un mapa en $\mathbb{R}^n$ de la dimensión adecuada y, a continuación, utiliza ese mapa para definir un producto interno sobre $\mathbb{R}^n$ con respecto a la cual el mapa es una incrustación. El álgebra lineal estándar completa el argumento.

Ahora bien, la dimensión finita, en este sentido, es claramente muy fuerte. Básicamente dice que la métrica está controlada por n puntos. La condición de planitud dice que esos n puntos se incrustan correctamente (y presumiblemente descarta los ejemplos de la pregunta y la primera respuesta). Pero es de esperar, ya que la incrustación en el espacio euclídeo es una condición igualmente fuerte.

Answer 2

Respecto a la pregunta 1: Creo que la primera persona que caracterizó los espacios métricos finitos que se incrustan en algún espacio euclidiano fue Schoenberg, en

I.J. Schoenberg, Observaciones al artículo de Maurice Fréchet "On the axiomatic definition of a class of vectorially applicable distance spaces on Hilbert space", Anales de Matemáticas 36 (1935), 724--732.

Allí demuestra que un espacio métrico finito $\{a_0, \ldots, a_n\}$ puede incrustarse en algún espacio euclidiano si y sólo si la matriz $M = (d(a_i, a_j)^2)$ de distancias al cuadrado es condicionalmente semidefinida negativa Eso es, $$ \mathbf{x}^t M \mathbf{x} \leq 0 $$ siempre que $\mathbf{x} = (x_0, \ldots, x_n) \in \mathbb{R}^{n + 1}$ con $\sum x_i = 0$ .

De hecho, el resultado de Schoenberg es aún más nítido. Para un $(n + 1)$ -punto espacio $A$ como las anteriores, las siguientes son equivalentes:

• $A$ se incrusta isométricamente en el espacio de Hilbert $L^2$
• $A$ se incrusta isométricamente en $\mathbb{R}^n$
• la matriz $M$ de las distancias al cuadrado es condicionalmente semidefinida negativa.

Por cierto, Fréchet y Schoenberg también demostraron que cada espacio métrico finito se incrusta en $(\mathbb{R}^n, d_\infty)$ para algunos $n$ donde $d_\infty$ es la métrica procedente del $\infty$ -norm $\Vert\cdot\Vert_\infty$ . La prueba es bastante corta y dulce.

Answer 3

Para la pregunta 1: ¿Qué pasa con $K_{1,3}$ (un vértice conectado a 3 vértices) con la métrica del camino más corto?

Por lo demás, existe este teorema de Bourgain (1985, "On lipschtitz embedding of finite metric spaces in Hilbert space") que dice: Cualquier espacio métrico de n puntos puede incrustarse en $\ell_2$ con distorsión $O(\log n)$ .

Por último, "Low Distortion Embeddings of Finite Metric Spaces" (Piotr Indyk, Jiri Matousek) expone muchos de estos resultados, y luego hay más artículos aquí (incluido el artículo)

Answer 4

Hay una pregunta relacionada aquí (con una respuesta similar a la de Andrew --- responde a la pregunta nº 1).

Pregunta nº 2a: NO, digamos que tomamos 4 puntos p,x,y,z tales que |px|=|py|=|pz|=1 y $|xy|=|yz|=|zx|=2$ .

Pregunta #2b: SÍ, existe una incrustación trivial en un grafo métrico, que puede aproximarse arbitrariamente bien mediante un grafo con longitud fija de aristas.

Pregunta #0: Algunas preguntas relacionadas aparecen cuando uno juega con la definición de espacio de Alexandrov, revise también CAT(κ)-Espacios de Gromov: Construcción y concentración Enlace

Answer 5

El problema bajo qué condiciones un espacio métrico finito $(X,d)$ puede incrustarse isométricamente en el espacio euclidiano $\mathbb{R}^n$ se responde en el artículo

C.L. Morgan, EMBEDDING METRIC SPACES IN EUCLIDEAN SPACE, Journal of Geometry. Vol. 5/1 1974

La respuesta es demasiado técnica para escribirla aquí, pero si no recuerdo mal, el artículo se puede encontrar en la Web.