Плотный пролет

В метрической геометрии метрическая оболочка или плотная оболочка метрического пространства M представляет собой инъективное метрическое пространство , в которое M может быть вложено. В некотором смысле он состоит из всех точек «между» точками M , аналогично выпуклой оболочке множества точек в евклидовом пространстве . иногда называют инъективной оболочкой или гипервыпуклой оболочкой M. Узкий промежуток также Его также называют инъективной оболочкой не следует путать с инъективной оболочкой модуля , но в алгебре , концепцией с аналогичным описанием относительно категории R , -модулей а не метрических пространств.

Узкий пролет был впервые описан Исбеллом (1964) , а также изучен и применен Хольштыньским в 1960-х годах. Позже он был независимо заново открыт Дрессом (1984) и Хробаком и Лармором (1994) ; см. в Chepoi (1997) эту историю . Узкий промежуток — одна из центральных конструкций Т-теории .

Определение

Плотность метрического пространства можно определить следующим образом. Пусть ( X , d ) — метрическое пространство, и пусть T ( X ) — множество экстремальных функций на X , где мы говорим, что экстремальная функция на X означает функцию f из X в R такую, что

1. Для любых x , y в X , d ( x , y ) ≤ f ( x ) + f ( y ), и
2. Для каждого x в X d(x,y) - f(x) = sup{ f(y):y в X }.

В частности (принимая x = y в свойстве 1 выше) f ( x ) ≥ 0 для всех x . Один из способов интерпретировать первое требование выше состоит в том, что f определяет набор возможных расстояний от некоторой новой точки до точек в X , которые должны удовлетворять неравенству треугольника вместе с расстояниями в ( X , d ). Второе требование гласит, что ни одно из этих расстояний нельзя уменьшить, не нарушив неравенство треугольника.

Плотная оболочка ( X ,d) — это метрическое пространство (T(X),δ), где

$$\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)}$$

аналогичен метрике, индуцированной ℓ ^∞ норма . (Если d ограничено, то δ — это метрика подпространства, индуцированная метрикой, индуцированной ℓ ^∞ норма . Если d не ограничено, то каждая экстремальная функция на X неограничена и поэтому $T(X)\not \subseteq \ell ^{\infty }(X).$ В любом случае, будет верно, что для любых f,g из T(X) разница $g-f$ принадлежит $\ell ^{\infty }(X)$, т. е. ограничен.)

Эквивалентные определения экстремальных функций

Для функции f от X до R , удовлетворяющей первому требованию, следующие версии второго требования эквивалентны:

• Для каждого x в X d(x,y) - f(x) = sup{ f(y):y в X }.
• f является поточечно минимальным относительно вышеупомянутого первого требования, т. е. для любой функции g из X в R такой, что d(x,y) ⩽ g(x) + g(y) для всех x,y в X , если g ≤f поточечно, тогда f=g .

Основные свойства и примеры

• Для всех x в X , $0\leq f(x).$
• Для каждого x в X , $(d(x,y))_{y\in X}$ является экстремальным. (Доказательство: используйте симметрию и неравенство треугольника .)
• Если X конечно, то для любой функции f из X в R , которая удовлетворяет первому требованию, второе требование эквивалентно условию, что для каждого x в X существует y в X такой, что f ( x ) + f ( y ) знак равно d ( Икс , у ). (Если $X=\emptyset ,$ тогда оба условия верны. Если $X\neq \emptyset ,$ тогда супремум достигается, и первое требование влечет эквивалентность.)
• Скажем |X|=2 и выберите различные a, b такие, что X={a,b}. Затем $T(X)=\{f\in (\mathbb {R} _{\geq 0})^{X}:f(a)+f(b)=d(a,b)\}$ является выпуклой оболочкой {{(a,1),(b,0)},{(a,0),(b,1)}}. [Добавьте картинку. Надпись: Если X={0,1}, то $T(X)=\{v\in (\mathbb {R} _{\geq 0})^{2}:v_{0}+v_{1}=d(0,1)\}$ является выпуклой оболочкой {(0,1),(1,0)}. ]
• Каждая экстремальная функция f на X является катетовой : f удовлетворяет первому требованию и $\forall x,y\in X\quad f(x)\leq d(x,y)+f(y),$ или, что то же самое, f удовлетворяет первому требованию и $\forall x,y\in X\quad |f(y)-f(x)|\leq d(x,y)$ (является 1- липшицевым ), или, что то же самое, f удовлетворяет первому требованию и $\forall x\in X\quad \sup\{f(y)-d(x,y):y\in X\}=f(x).$
• Т(Х)⊆ С(Х) . (Липшицевы функции непрерывны.)
• T(X равнонепрерывно ) . (Следует из того, что каждая экстремальная функция на X является 1-липшицевой; см. Equicontinuity#Examples .)
• Не всякая функция Катетова на X является экстремальной. Например, пусть a , b различны, пусть X = {a,b}, пусть d = ([x≠y]) _{x,y в X —} дискретная метрика на X и пусть f = {(a,1 ),(б,2)}. Тогда f катетовская, но не экстремальная. (Почти сразу видно, что f — катетов. f не является экстремальным, поскольку не соответствует свойству, указанному в третьем пункте этого раздела.)
• Если d ограничено, то каждое f в T(X) ограничено. Фактически, для каждого f в T(X) , $\|f\|_{\infty }\leq \|d\|_{\infty }.$ (Примечание $d\in \ell ^{\infty }(X\times X).$) (Следует из третьего эквивалентного свойства в приведенном выше разделе.)
• Если d неограничено, то каждое f в T(X) неограничено. (Следует из первого требования.)
• $T(X)$ замкнуто в поточечных пределах. Для любого поточечно сходящегося $f\in (T(X))^{\omega },$ $\lim f\in T(X).$
• Если (X,d) компактен, то (T(X),δ) компактен. (Доказательство: из теоремы о крайних значениях следует, что d , будучи непрерывной как функция $X\times X\to \mathbb {R} ,$ ограничен, поэтому (см. предыдущий пункт) $T(X)\subseteq \{f\in C(X):\|f\|_{\infty }\leq \|d\|_{\infty }\}$ является ограниченным подмножеством C(X). Мы показали, что T(X) равностепенно непрерывен, поэтому из теоремы Арзела–Асколи следует, что T(X) компактен относительно . Однако предыдущий пункт подразумевает, что T(X) закрыт при $\ell ^{\infty }$ норма, поскольку $\ell ^{\infty }$ сходимость подразумевает поточечную сходимость. Таким образом, T(X) компактно.)
• Для любой функции g из X в R , удовлетворяющей первому требованию, существует f в T(X) такая, что f≤g поточечно.
• Для любой экстремальной f на X функции $\forall x\in X\quad f(x)=\sup\{|f(y)-d(x,y)|:y\in X\}.$
• Для любых f,g из T(X) разница $g-f$ принадлежит $\ell ^{\infty }(X)$, т. е. ограничен. (Используйте пункт выше.)
• Карта Куратовского $e:=((d(x,y))_{y\in X})_{x\in X}$ это изометрия . (Когда X =∅, результат очевиден. Когда X≠∅, обратное неравенство треугольника .) результат влечет за собой
• Пусть f в T(X) . Для любого a в X , если f(a)=0 , то f=e(a). (Для каждого x в X мы имеем $(e(a))(x)=d(a,x)\leq f(a)+f(x)=f(x).$ Из минимальности (вторая эквивалентная характеристика в разделе выше) f и того факта, что $e(a)$ удовлетворяет первому требованию, отсюда следует, что $f=e_{a}.$)
• (X,d) гиперболичен гиперболичен тогда и только тогда, когда (T(X),δ) .

Свойства гипервыпуклости

• (Т(Х),δ) и
  $$\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)$$
  оба гипервыпуклые .
• Для любого Y такого, что $\operatorname {range} e\subseteq Y\subsetneq X\cup (T(X)\setminus \operatorname {range} e),$
  $$\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)$$
  не является гипервыпуклым. (« (T(X),δ) — гипервыпуклая оболочка (X,d) .»)
• Позволять $(H,\varepsilon )$ — гипервыпуклое метрическое пространство с $X\subseteq H$ и $\varepsilon |_{X\times X}=\delta$. Если бы я со всем $X\subseteq I\subsetneq H,$ $(I,\varepsilon |_{I\times I})$ не является сверхвыпуклым, то $(H,\varepsilon )$ и (T(X),δ изометричны ) . («Каждая гипервыпуклая оболочка (X,d) изометрична (T(X),δ). »)

Примеры

• Скажем, |X|=3, выберите различные a, b, c такие, что X={a,b,c}, и пусть i=d(a,b), j=d(a,c), k=d( б, в). Затем
  $${\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}}$$
  где $x=2^{-1}(i+j-k,i+k-j,j+k-i).$ [Добавьте картинку. Подпись: Если X={0,1,2}, то T(X)=conv{(,,),(,,)} u conv{(,,),(,,)} u conv{(,, ),(,,)} имеет форму буквы Y.] (Ср. )

Если набор точек на плоскости с манхэттенской метрикой имеет связную ортогональную выпуклую оболочку , то эта оболочка совпадает с плотным пространством точек.

• На рисунке изображен набор X из 16 точек на плоскости; чтобы сформировать конечное метрическое пространство из этих точек, мы используем манхэттенское расстояние ( ℓ ¹ расстояние). Синяя область, показанная на рисунке, представляет собой выпуклую оболочку , набор точек z, таких, что каждый из четырех замкнутых квадрантов с z в качестве вершины содержит точку X. ортогональную Любая такая точка z соответствует точке узкого промежутка: функция f ( x ), соответствующая точке z, равна f ( x ) = d ( z , x ). Функция этого вида удовлетворяет свойству 1 узкой области для любого z в манхэттенской метрической плоскости согласно неравенству треугольника для манхэттенской метрики. Чтобы показать свойство 2 узкого промежутка, рассмотрим некоторую точку x в X ; мы должны найти y в X такой, что f ( x ) + f ( y ) = d ( x , y ). Но если x находится в одном из четырех квадрантов, имеющих z вершину , то за y можно взять любую точку в противоположном квадранте, поэтому свойство 2 также удовлетворяется. И наоборот, можно показать, что каждая точка узкого промежутка таким образом соответствует точке в ортогональной выпуклой оболочке этих точек. Однако для множеств точек с манхэттенской метрикой в ​​более высоких измерениях и для плоских множеств точек с несвязными ортогональными оболочками узкий промежуток отличается от ортогональной выпуклой оболочки.

Размер узкого промежутка, когда X конечно

В приведенном выше определении содержится узкий диапазон T ( X ) набора из n ( $n\in \mathbb {Z} _{\geq 0}$) указывает на R ^Х , вещественное векторное пространство размерности n . С другой стороны, если мы рассмотрим размерность T ( X ) как многогранный комплекс , Девелин (2006) показал, что при подходящем общем предположении о метрике это определение приводит к пространству с размерностью от n /3 до н /2.

Альтернативные определения

Альтернативное определение, основанное на понятии метрического пространства, нацеленного на его подпространство, было описано Хольштыньским (1968) , который доказал, что инъективная оболочка банахова пространства в категории банаховых пространств совпадает (после забвения линейной структуры) с узкий пролет. Эта теорема позволяет свести некоторые задачи из произвольных банаховых пространств к банаховым пространствам вида C(X), где X — компакт.

Девелин и Штурмфельс (2004) попытались дать альтернативное определение узкого пространства конечного метрического пространства как тропической выпуклой оболочки векторов расстояний от каждой точки до каждой другой точки пространства. Однако позже в том же году они признали в Erratum Develin & Sturmfels (2004a) , что, хотя тропическая выпуклая оболочка всегда содержит узкий пролет, она может с ней не совпадать.

Приложения

• Дресс, Хубер и Моултон (2001) описывают применение узкого диапазона при реконструкции эволюционных деревьев на основе биологических данных.
• Узкий интервал играет роль в нескольких онлайн-алгоритмах решения проблемы K-сервера .
• Штурмфельс и Ю (2004) используют узкий диапазон для классификации метрических пространств по шести точкам.
• Чепой (1997) использует узкую промежуток для доказательства результатов об упаковке метрик сечения в более общие конечные метрические пространства.

См. также

• Вложение Куратовского — вложение любого метрического пространства в банахово пространство, определяемое аналогично отображению Куратовского.
• Инъективное метрическое пространство

Ссылки

• Чепой, Виктор (1997), « Подход AT _X к некоторым результатам по разрезам и метрикам», Advances in Applied Mathematics , 19 (4): 453–470, doi : 10.1006/aama.1997.0549 .
• Хробак, Марек ; Лармор, Лоуренс Л. (1994), «Щедрость помогает или 11-конкурентный алгоритм для трех серверов», Journal of Algorithms , 16 (2): 234–263, doi : 10.1006/jagm.1994.1011 , S2CID   15169525 .
• Девелин, Майк (2006), «Размеры узких промежутков», Annals of Combinatorics , 10 (1): 53–61, arXiv : math.CO/0407317 , doi : 10.1007/s00026-006-0273-y , S2CID   92984638 .
• Девелин, Майк ; Штурмфельс, Бернд (2004), «Тропическая выпуклость» (PDF) , Documenta Mathematica , 9 : 1–27, doi : 10.4171/dm/154 , S2CID   64471 .
• Девелин, Майк ; Штурмфельс, Бернд (2004a), «Ошибка в «тропической выпуклости» » (PDF) , Documenta Mathematica , 9 : 205–206, doi : 10.4171/dm/154 , S2CID   64471 .
• Дресс, Андреас В.М. (1984), «Деревья, плотные расширения метрических пространств и когомологическая размерность некоторых групп», Advance in Mathematics , 53 (3): 321–402, doi : 10.1016/0001-8708(84)90029 -Х .
• Платье, Андреас В.М .; Хубер, Коннектикут ; Моултон, В. (2001), «Метрические пространства в чистой и прикладной математике» (PDF) , Documenta Mathematica (Proceedings Quadratic Forms LSU): 121–139 .
• Холштыньский, Влодзимеж (1968), "Линеаризация изометрических вложений банаховых пространств. Метрические оболочки", Bull. акад. Полон. наук. , 16 : 189–193 .
• Исбелл, Дж. Р. (1964), «Шесть теорем об инъективных метрических пространствах», Комментарий. Математика. Хелв. , 39 : 65–76, doi : 10.1007/BF02566944 , S2CID   121857986 .
• Штурмфельс, Бернд ; Ю, Жозефина (2004), «Классификация шеститочечных метрик» , Электронный журнал комбинаторики , 11 : R44, arXiv : math.MG/0403147 , Bibcode : 2004math......3147S , doi : 10.37236/1797 , S2CID   6733896 .

Внешние ссылки

• Йосвиг, Майкл, Тугие пролеты .