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

Probablemente merezca la pena señalar que (a diferencia de lo que ocurre con $L_2$ ) cualquier espacio métrico finito puede incrustarse en un espacio de dimensión finita $L_\infty$ espacio sin distorsión. Basta con asignar cada uno de los $n$ puntos del espacio métrico al $n$ -vector dimensional de distancias de todos los puntos. (Para una construcción estrechamente relacionada, véase estrecho margen .)

Answer 2

Para la pregunta 0 :

Para la incrustación isométrica una referencia estándar es

Deza, M.; Laurent, M. (1997), Geometría de cortes y métricas, Algorithms and Combinatorics, 15, Springer, MR1460488, ISBN 354061611X

Para incrustaciones aproximadas una bella exposición del libro de Matouseks:

Conferencias sobre geometría discreta. Jiri Matousek. Año de publicación: 2002. ISBN:0387953744

Answer 3

Me limitaré a citar la introducción de Artículo de Johnson y Kambites "Matrices tropicales idempotentes y espacios métricos finitos" en dar una respuesta tramposa que explote la estructura tropical -en lugar de la habitual- de $\mathbb{R}$ :

"toda semimétrica finita sobre $n$ puntos se pueden incrustar en tropicales $n$ -espacio".

Aquí, una semimétrica es una función que satisface todos los axiomas de distancia excepto la simetría (por lo que, en particular, una métrica es también una semimétrica).