Espacio estrecho

Noción en geometría métrica

En geometría métrica , la envolvente métrica o espacio estrecho de un espacio métrico M es un espacio métrico inyectivo en el que M puede ser incluido. En cierto sentido, consiste en todos los puntos "entre" los puntos de M , análogo a la envoltura convexa de un conjunto de puntos en un espacio euclidiano . La envoltura estrecha también se conoce a veces como envoltura inyectiva o envoltura hiperconvexa de M. También se ha llamado envoltura inyectiva , pero no debe confundirse con la envoltura inyectiva de un módulo en álgebra , un concepto con una descripción similar relativa a la categoría de R -módulos en lugar de espacios métricos.

El tramo estrecho fue descrito por primera vez por Isbell (1964), y fue estudiado y aplicado por Holsztyński en la década de 1960. Más tarde fue redescubierto independientemente por Dress (1984) y Chrobak & Larmore (1994); véase Chepoi (1997) para esta historia. El tramo estrecho es una de las construcciones centrales de la teoría T.

Definición

El espacio métrico puede definirse de la siguiente manera. Sea ( X , d ) un espacio métrico y sea T ( X ) el conjunto de funciones extremales en X , donde decimos que una función extremal en X significa una función f de X a R tal que

1. Para cualquier x , y en X , d ( x , y ) ≤ f ( x ) + f ( y ), y
2. Para cada x en X , f(x) = sup{ d(x,y) - f(y):y en X }. ^{[1] : 124}

En particular (tomando x = y en la propiedad 1 anterior) f ( x ) ≥ 0 para todo x . Una forma de interpretar el primer requisito anterior es que f define un conjunto de distancias posibles desde algún nuevo punto hasta los puntos en X que deben satisfacer la desigualdad triangular junto con las distancias en ( X , d ). El segundo requisito establece que ninguna de estas distancias se puede reducir sin violar la desigualdad triangular.

El espacio estrecho de (X,d) es el espacio métrico (T(X),δ), donde es análogo a la métrica inducida por la norma ℓ ∞ . (Si d está acotado, entonces δ es la métrica del subespacio inducida por la métrica inducida por la norma ℓ ∞ . Si d no está acotado, entonces toda función extremal en X es ilimitada y, por lo tanto , Independientemente, será cierto que para cualquier f,g en T(X) , la diferencia pertenece a , es decir, está acotada). $${\displaystyle \delta =(\inf\{C\in \mathbb {R} _{\geq 0}:|g(x)-f(x)|\leq C{\text{ for all }}x\in X\})_{f,g\in T(X)}=(\|g-f\|_{\infty })_{f,g\in T(X)}}$$ ${\displaystyle T(X)\not \subseteq \ell ^{\infty }(X).}$ ${\displaystyle g-f}$ ${\displaystyle \ell ^{\infty }(X)}$

Definiciones equivalentes de funciones extremales

Para una función f de X a R que satisface el primer requisito, las siguientes versiones del segundo requisito son equivalentes:

• Para cada x en X , f(x) = sup{ d(x,y) - f(y):y en X }.
• f es mínima puntualmente con respecto al primer requisito mencionado anteriormente, es decir, para cualquier función g de X a R tal que d(x,y) ≤ g(x) + g(y) para todo x,y en X , si g≤f puntualmente, entonces f=g . ^{[2] : 93, Proposición 4.6.2  [Nota 1] [Nota 2] [3] : Lema 5.1}

Propiedades básicas y ejemplos

• Para todo x en X , ${\displaystyle 0\leq f(x).}$
• Para cada x en X , es extremal. (Demostración: utilice la simetría y la desigualdad triangular ). ^{[Nota 3]} ${\displaystyle (d(x,y))_{y\in X}}$
• Si X es finito, entonces para cualquier función f desde X hasta R que satisfaga el primer requisito, el segundo requisito es equivalente a la condición de que para cada x en X , existe y en X tal que f ( x ) + f ( y ) = d ( x , y ). (Si entonces ambas condiciones son verdaderas. Si entonces se logra el supremo, y el primer requisito implica la equivalencia.) ${\displaystyle X=\emptyset ,}$ ${\displaystyle X\neq \emptyset ,}$
• Digamos |X|=2, y escojamos a, b distintos tales que X={a,b}. Entonces es la envoltura convexa de {{(a,1),(b,0)},{(a,0),(b,1)}}. [Agregar una imagen. Leyenda: Si X={0,1}, entonces es la envoltura convexa de {(0,1),(1,0)}. ] ^{[4] : 124} ${\displaystyle T(X)=\{f\in (\mathbb {R} _{\geq 0})^{X}:f(a)+f(b)=d(a,b)\}}$ ${\displaystyle T(X)=\{v\in (\mathbb {R} _{\geq 0})^{2}:v_{0}+v_{1}=d(0,1)\}}$
• Toda función extrema f en X es Katetov : ^{[5] [6] : Sección 2} f satisface el primer requisito y o equivalentemente, f satisface el primer requisito y (es 1- Lipschitz ), o equivalentemente, f satisface el primer requisito y ^{[2] : Prueba de la Proposición 4.6.1  [Nota 4]} ${\displaystyle \forall x,y\in X\quad f(x)\leq d(x,y)+f(y),}$ ${\displaystyle \forall x,y\in X\quad |f(y)-f(x)|\leq d(x,y)}$ ${\displaystyle \forall x\in X\quad \sup\{f(y)-d(x,y):y\in X\}=f(x).}$
• T(X)⊆ C(X) . (Las funciones de Lipschitz son continuas).
• T(X) es equicontinua . (Se deduce de que toda función extremal en X es 1-Lipschitz; cf. Equicontinuidad#Ejemplos ).
• No todas las funciones de Katetov en X son extremales. Por ejemplo, sean a , b distintas, sea X = {a,b}, sea d = ([x≠y]) _{x,y en X} la métrica discreta en X , y sea f = {(a,1),(b,2)}. Entonces f es Katetov pero no extremal. (Es casi inmediato que f es Katetov. f no es extremal porque no cumple la propiedad del tercer punto de esta sección).
• Si d está acotado, entonces cada f en T(X) está acotado. De hecho, para cada f en T(X) , (Nota ) (Se deduce de la tercera propiedad equivalente en la sección anterior). ${\displaystyle \|f\|_{\infty }\leq \|d\|_{\infty }.}$ ${\displaystyle d\in \ell ^{\infty }(X\times X).}$
• Si d no tiene límites, entonces todo f en T(X) no tiene límites. (Se deduce del primer requisito).
• ${\displaystyle T(X)}$está cerrado bajo límites puntuales. Para cualquier convergente puntual ${\displaystyle f\in (T(X))^{\omega },}$ ${\displaystyle \lim f\in T(X).}$
• Si (X,d) es compacto, entonces (T(X),δ) es compacto. ^{[7] [2] : Proposición 4.6.3} (Demostración: El teorema de los valores extremos implica que d , al ser continua como función , está acotada, por lo que (véase el punto anterior) es un subconjunto acotado de C(X). Hemos demostrado que T(X) es equicontinuo, por lo que el teorema de Arzelà–Ascoli implica que T(X) es relativamente compacto . Sin embargo, el punto anterior implica que T(X) está cerrado bajo la norma, ya que la convergencia implica convergencia puntual. Por lo tanto, T(X) es compacto.) ${\displaystyle X\times X\to \mathbb {R} ,}$ ${\displaystyle T(X)\subseteq \{f\in C(X):\|f\|_{\infty }\leq \|d\|_{\infty }\}}$ ${\displaystyle \ell ^{\infty }}$ ${\displaystyle \ell ^{\infty }}$
• Para cualquier función g de X a R que satisfaga el primer requisito, existe f en T(X) tal que f≤g puntualmente. ^{[2] : Lema 4.4}
• Para cualquier función extrema f en X , ^{[2] : Proposición 4.6.1  [Nota 5]} ${\displaystyle \forall x\in X\quad f(x)=\sup\{|f(y)-d(x,y)|:y\in X\}.}$
• Para cualquier f,g en T(X) , la diferencia pertenece a , es decir, está acotada. (Use el punto anterior). ${\displaystyle g-f}$ ${\displaystyle \ell ^{\infty }(X)}$
• La función de Kuratowski ^{[4] : ​​125} es una isometría . (Cuando X = ∅, el resultado es obvio. Cuando X ≠ ∅, la desigualdad del triángulo inverso implica el resultado). ${\displaystyle e:=((d(x,y))_{y\in X})_{x\in X}}$
• Sea f en T(X) . Para cualquier a en X , si f(a)=0 , entonces f=e(a). ^{[3] : Lema 5.1} (Para cada x en X tenemos De la minimalidad (segunda caracterización equivalente en la sección anterior) de f y del hecho de que satisface el primer requisito se sigue que ) ${\displaystyle (e(a))(x)=d(a,x)\leq f(a)+f(x)=f(x).}$ ${\displaystyle e(a)}$ ${\displaystyle f=e_{a}.}$
• (X,d) es hiperbólico si y sólo si (T(X),δ) es hiperbólico. ^{[3] : Teorema 5.3}

Propiedades de hiperconvexidad

• (T(X),δ) y son ambos hiperconvexos . ^{[2] : Proposición 4.7.1} $${\displaystyle \left(X\cup (T(X)\setminus \operatorname {range} e),\delta _{(T(X)\setminus \operatorname {range} e)\times (T(X)\setminus \operatorname {range} e)}\cup (\delta (e(x),e(y)))_{x,y\in X}\cup (\delta (e(x),g))_{x\in X,g\in T(X)\setminus \operatorname {range} e}\cup (\delta (f,e(y))_{f\in T(X)\setminus \operatorname {range} e,y\in X}\right)}$$
• Para cualquier Y tal que no sea hiperconvexo. ^{[2] : Proposición 4.7.2} (" (T(X),δ) es una envoltura hiperconvexa de (X,d) .") ${\displaystyle \operatorname {range} e\subseteq Y\subsetneq X\cup (T(X)\setminus \operatorname {range} e),}$ $${\displaystyle \left(X\cup (Y\setminus \operatorname {range} e),\delta _{(Y\setminus \operatorname {range} e)\times (Y\setminus \operatorname {range} e)}\cup (\delta (e(x),e(y)))_{x,y\in X}\cup (\delta (e(x),g))_{x\in X,g\in Y\setminus \operatorname {range} e}\cup (\delta (f,e(y))_{f\in Y\setminus \operatorname {range} e,y\in X}\right)}$$
• Sea un espacio métrico hiperconvexo con y . Si para todo I con no es hiperconvexo, entonces y (T(X),δ) son isométricos . ^{[2] : Proposición 4.7.1} ("Toda envoltura hiperconvexa de (X,d) es isométrica con (T(X),δ). ") ${\displaystyle (H,\varepsilon )}$ ${\displaystyle X\subseteq H}$ ${\displaystyle \varepsilon |_{X\times X}=\delta }$ ${\displaystyle X\subseteq I\subsetneq H,}$ ${\displaystyle (I,\varepsilon |_{I\times I})}$ ${\displaystyle (H,\varepsilon )}$

Ejemplos

• Digamos |X|=3, escojamos a, b, c distintos tales que X={a,b,c}, y sea i=d(a,b), j=d(a,c), k=d(b,c). Entonces , donde [Agrega una imagen. Leyenda: Si X={0,1,2}, entonces T(X)=conv{(,,),(,,)} u conv{(,,),(,,)} u conv{(,,),(,,)} tiene la forma de la letra Y.] (Cf. ^{[4] : 124} ) $${\displaystyle {\begin{alignedat}{2}T(X)=&\{v\in (\mathbb {R} _{\geq 0})^{3}:1=v_{a}+v_{b},2=v_{a}+v_{c},3\leq v_{b}+v_{c}\\&\qquad \qquad \qquad {\text{or }}1=v_{a}+v_{b},2\leq v_{a}+v_{c},3=v_{b}+v_{c}\\&\qquad \qquad \qquad {\text{or }}1\leq v_{a}+v_{b},2=v_{a}+v_{c},3=v_{b}+v_{c}\}\\=&\{v\in (\mathbb {R} _{\geq 0})^{3}:v_{a}\leq {\frac {(i+j)-k}{2}},v_{b}=i-v_{a},v_{c}=j-v_{a}\\&\qquad \qquad \qquad {\text{or }}v_{a}=i-v_{b},v_{b}\leq {\frac {(i+k)-j}{2}},v_{c}=k-v_{b}\\&\qquad \qquad \qquad {\text{or }}v_{a}=j-v_{c},v_{b}=k-v_{c},v_{c}\leq {\frac {(j+k)-i}{2}}\}\\=&\left\{(t,i-t,j-t):t\in \left[0,i\land j\land {\frac {(i+j)-k}{2}}\right]\right\}\\&\cup \left\{(i-t,t,k-t):t\in \left[0,i\land k\land {\frac {(i+k)-j}{2}}\right]\right\}\\&\cup \left\{(j-t,k-t,t):t\in \left[0,j\land k\land {\frac {(j+k)-i}{2}}\right]\right\}\\=&\left\{(t,i-t,j-t):t\in \left[0,{\frac {(i+j)-k}{2}}\right]\right\}\\&\cup \left\{(i-t,t,k-t):t\in \left[0,{\frac {(i+k)-j}{2}}\right]\right\}\\&\cup \left\{(j-t,k-t,t):t\in \left[0,{\frac {(j+k)-i}{2}}\right]\right\}\\=&\operatorname {conv} \{(0,i,j),x\}\cup \operatorname {conv} \{(i,0,k),x\}\cup \operatorname {conv} \{(j,k,0),x\},\end{alignedat}}}$$ ${\displaystyle x=2^{-1}(i+j-k,i+k-j,j+k-i).}$

Si un conjunto de puntos en el plano, con la métrica de Manhattan , tiene una envoltura convexa ortogonal conexa , entonces esa envoltura coincide con el espacio estrecho de los puntos.

• La figura muestra un conjunto X de 16 puntos en el plano; para formar un espacio métrico finito a partir de estos puntos, usamos la distancia de Manhattan ( distancia ℓ ¹ ). ^[8] La región azul que se muestra en la figura es la envoltura convexa ortogonal , el conjunto de puntos z tales que cada uno de los cuatro cuadrantes cerrados con z como vértice contiene un punto de X. Cualquier punto z corresponde a un punto del lapso estrecho: la función f ( x ) correspondiente a un punto z es f ( x ) = d ( z , x ). Una función de esta forma satisface la propiedad 1 del lapso estrecho para cualquier z en el plano métrico de Manhattan, por la desigualdad triangular para la métrica de Manhattan. Para mostrar la propiedad 2 del lapso estrecho, considere algún punto x en X ; debemos encontrar y en X tal que f ( x )+ f ( y )= d ( x , y ). Pero si x está en uno de los cuatro cuadrantes que tienen a z como vértice, y puede tomarse como cualquier punto en el cuadrante opuesto, por lo que también se satisface la propiedad 2. A la inversa, se puede demostrar que cada punto del lapso estrecho corresponde de esta manera a un punto en la envoltura convexa ortogonal de estos puntos. Sin embargo, para conjuntos de puntos con la métrica de Manhattan en dimensiones superiores, y para conjuntos de puntos planos con envolturas ortogonales desconectadas, el lapso estrecho difiere de la envoltura convexa ortogonal.

Dimensión del tramo estrecho cuandoincógnitaes finito

La definición anterior incorpora el espacio estrecho T ( X ) de un conjunto de n ( ) puntos en R ^X , un espacio vectorial real de dimensión n . Por otra parte, si consideramos la dimensión de T ( X ) como un complejo poliédrico , Develin (2006) demostró que, con un supuesto de posición general adecuado en la métrica, esta definición conduce a un espacio con dimensión entre n /3 y n /2. ${\displaystyle n\in \mathbb {Z} _{\geq 0}}$

Definiciones alternativas

Una definición alternativa basada en la noción de espacio métrico orientado a su subespacio fue descrita por Holsztyński (1968), quien demostró que la envolvente inyectiva de un espacio de Banach, en la categoría de espacios de Banach, coincide (después de olvidar la estructura lineal) con el espacio cerrado. Este teorema permite reducir ciertos problemas de espacios de Banach arbitrarios a espacios de Banach de la forma C(X), donde X es un espacio compacto.

Develin y Sturmfels (2004) intentaron proporcionar una definición alternativa del lapso estrecho de un espacio métrico finito como la envoltura convexa tropical de los vectores de distancias desde cada punto a cada otro punto en el espacio. Sin embargo, más tarde ese mismo año reconocieron en una Erratum Develin y Sturmfels (2004a) que, si bien la envoltura convexa tropical siempre contiene el lapso estrecho, puede no coincidir con él.

Aplicaciones

• Dress, Huber y Moulton (2001) describen aplicaciones del span ajustado en la reconstrucción de árboles evolutivos a partir de datos biológicos.
• El lapso estrecho cumple una función en varios algoritmos en línea para el problema del servidor K. ^[9]
• Sturmfels y Yu (2004) utilizan el lapso estrecho para clasificar espacios métricos en hasta seis puntos.
• Chepoi (1997) utiliza el lapso estrecho para demostrar resultados sobre el empaquetamiento de métricas de corte en espacios métricos finitos más generales.

Véase también

• Incorporación de Kuratowski , una incorporación de cualquier espacio métrico en un espacio de Banach definido de manera similar al mapa de Kuratowski
• Espacio métrico inyectivo

Notas

1. Vestido, Huber y Moulton (2001).
2. Khamsi, Mohamed A. ; Kirk, William A. (2001). Introducción a los espacios métricos y la teoría del punto fijo . Wiley.
3. Dress, Andreas ; Huber, Katharina T. ; Koolen, Jacobus; Moulton, Vincent; Spillner, Andreas (2012). Combinatoria filogenética básica . Cambridge University Press. ISBN 978-0-521-76832-0.
4. Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine (2010). Redes filogenéticas: conceptos, algoritmos y aplicaciones . Cambridge University Press. ISBN 978-0-521-75596-2.
5. Deza, Michel Marie ; Deza, Elena (2014). Enciclopedia de distancias (tercera edición). Springer. pág. 47. ISBN 978-3-662-44341-5.
6. Melleray, Julien (2008). "Algunas propiedades geométricas y dinámicas del espacio de Urysohn". Topología y sus aplicaciones . 155 (14): 1531–1560. doi : 10.1016/j.topol.2007.04.029 .
7. Benyamini, Yoav ; Lindenstrauss, Joram (2000). Análisis funcional no lineal geométrico . American Mathematical Society. pág. 32. ISBN 978-0-8218-0835-1.
8. En dos dimensiones, la distancia de Manhattan es isométrica después de la rotación y la escala a la distancia ℓ ∞ , por lo que con esta métrica el plano en sí es inyectivo, pero esta equivalencia entre ℓ ¹ y ℓ ^∞ no se cumple en dimensiones superiores.
9. Chrobak y Larmore (1994).

1. Khamsi y Kirk utilizan esta condición en su definición.
2. La prueba de Khamsi y Kirk muestra una implicación de la equivalencia con la condición inmediatamente anterior. La otra implicación no es difícil de demostrar.
3. Es decir, el mapa de Kuratowski A continuación presentaremos el mapa de Kuratowski. ${\displaystyle e(x)\in T(X).}$
4. El supremo se consigue con y=x .
5. El supremo se consigue con y=x .

Referencias

• Chepoi, Victor (1997), "Un enfoque TX para algunos resultados sobre cortes y métricas", Advances in Applied Mathematics , 19 (4): 453–470, _doi : 10.1006 /aama.1997.0549.
• Chrobak, Marek ; Larmore, Lawrence L. (1994), "La generosidad ayuda o un algoritmo 11-competitivo para tres servidores", Journal of Algorithms , 16 (2): 234–263, doi :10.1006/jagm.1994.1011, S2CID  15169525.
• Develin, Mike (2006), "Dimensiones de tramos estrechos", Annals of Combinatorics , 10 (1): 53–61, arXiv : math.CO/0407317 , doi :10.1007/s00026-006-0273-y, S2CID  92984638.
• Develin, Mike ; Sturmfels, Bernd (2004), "Convexidad tropical" (PDF) , Documenta Mathematica , 9 : 1–27, doi :10.4171/dm/154, S2CID  64471.
• Develin, Mike ; Sturmfels, Bernd (2004a), "Fe de erratas para "Convexidad tropical"" (PDF) , Documenta Mathematica , 9 : 205–206, doi :10.4171/dm/154, S2CID  64471.
• Dress, Andreas WM (1984), "Árboles, extensiones estrechas de espacios métricos y la dimensión cohomológica de ciertos grupos", Advances in Mathematics , 53 (3): 321–402, doi : 10.1016/0001-8708(84)90029-X.
• Dress, Andreas WM ; Huber, KT ; Moulton, V. (2001), "Espacios métricos en matemáticas puras y aplicadas" (PDF) , Documenta Mathematica (Proceedings Quadratic Forms LSU): 121–139.
• Holsztyński, Włodzimierz (1968), "Linealización de incrustaciones isométricas de espacios de Banach. Envolventes métricos", Bull. Acad. Polon. Sci. , 16 : 189–193.
• Isbell, JR (1964), "Seis teoremas sobre espacios métricos inyectivos", Comment. Math. Helv. , 39 : 65–76, doi :10.1007/BF02566944, S2CID  121857986.
• Sturmfels, Bernd ; Yu, Josephine (2004), "Clasificación de métricas de seis puntos", The Electronic Journal of Combinatorics , 11 : R44, arXiv : math.MG/0403147 , Bibcode :2004math......3147S, doi :10.37236/1797, S2CID  6733896.

Enlaces externos

• Joswig, Michael, Tramos estrechos.