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

Понятие в метрической геометрии.

В метрической геометрии метрическая оболочка или плотная оболочка метрического пространства 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 f ( x) = sup{ d(x,y) - f(y):y в X }. ^{[1] : 124}

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

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

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

нормой ℓ ∞dнормой ℓ ∞dXf gT(X) ${\displaystyle T(X)\not \subseteq \ell ^{\infty }(X).}$ ${\displaystyle g-f}$ ${\displaystyle \ell ^{\infty }(X)}$

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

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

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

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

• Для всех x в X , ${\displaystyle 0\leq f(x).}$
• Для каждого x в X экстремально . (Доказательство: используйте симметрию и неравенство треугольника .) ^{[Примечание 3]} ${\displaystyle (d(x,y))_{y\in X}}$
• Если X конечно, то для любой функции f из X в R , которая удовлетворяет первому требованию, второе требование эквивалентно условию, что для каждого x в X существует y в X такой, что f ( x ) + f ( y ) знак равно d ( Икс , у ). (Если то оба условия верны. Если то супремум достигается, и первое требование подразумевает эквивалентность.) ${\displaystyle X=\emptyset ,}$ ${\displaystyle X\neq \emptyset ,}$
• Скажем |X|=2 и выберите различные a, b такие, что X={a,b}. Тогда является выпуклой оболочкой {{(a,1),(b,0)},{(a,0),(b,1)}}. [Добавьте картинку. Подпись: Если X={0,1}, то это выпуклая оболочка {(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)\}}$
• Каждая экстремальная функция f на X является Катетовым : ^{[5] [6] : Раздел 2} f удовлетворяет первому требованию и или, что то же самое, f удовлетворяет первому требованию и (является 1- липшицевым ) или, что то же самое, f удовлетворяет первому требованию и ^{[ 2] : Доказательство предложения 4.6.1  [примечание 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 ) равнонепрерывно . (Следует из того, что каждая экстремальная функция на 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) , (Примечание ) (Следует из третьего эквивалентного свойства в предыдущем разделе.) ${\displaystyle \|f\|_{\infty }\leq \|d\|_{\infty }.}$ ${\displaystyle d\in \ell ^{\infty }(X\times X).}$
• Если d неограничено, то каждое f в T(X) неограничено. (Следует из первого требования.)
• ${\displaystyle T(X)}$замкнуто в поточечных пределах. Для любого поточечно сходящегося ${\displaystyle f\in (T(X))^{\omega },}$ ${\displaystyle \lim f\in T(X).}$
• Если (X,d) компактен, то (T(X),δ) компактен. ^{[7] [2] : Предложение 4.6.3} (Доказательство: из теоремы о крайних значениях следует, что d , будучи непрерывной, поскольку функция ограничена, поэтому (см. предыдущий пункт) является ограниченным подмножеством C(X). Мы показали T(X) равнонепрерывен, поэтому из теоремы Арзела–Асколи следует, что T(X) относительно компактен . Однако из предыдущего пункта следует, что T(X) замкнут по норме, поскольку сходимость влечет поточечную сходимость. Таким образом, T(X) компактен.) ${\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 }}$
• Для любой функции g из X в R , удовлетворяющей первому требованию, существует f в T(X) такая, что f≤g поточечно. ^{[2] : Лемма 4.4.}
• Для любой экстремальной функции f на X , ^{[2] : Предложение 4.6.1  [примечание 5]} ${\displaystyle \forall x\in X\quad f(x)=\sup\{|f(y)-d(x,y)|:y\in X\}.}$
• Для любого f,g ​​из T(X) разность принадлежит , т. е. ограничена. (Используйте пункт выше.) ${\displaystyle g-f}$ ${\displaystyle \ell ^{\infty }(X)}$
• Отображение Куратовского ^{[4] :125} является изометрией . (Когда X =∅, результат очевиден. Когда X≠∅, результат влечет за собой обратное неравенство треугольника .) ${\displaystyle e:=((d(x,y))_{y\in X})_{x\in X}}$
• Пусть f в T(X) . Для любого a в X , если f(a)=0 , то f=e(a). ^{[3] : Лемма 5.1} (Для каждого x в X мы имеем Из минимальности (вторая эквивалентная характеристика в предыдущем разделе) f и того факта, что удовлетворяет первому требованию, следует, что ) ${\displaystyle (e(a))(x)=d(a,x)\leq f(a)+f(x)=f(x).}$ ${\displaystyle e(a)}$ ${\displaystyle f=e_{a}.}$
• (X,d) гиперболичен тогда и только тогда, когда ( T(X),δ) гиперболичен. ^{[3] : Теорема 5.3.}

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

• (Т(Х),δ) и
  $${\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)}$$
  оба гипервыпуклые . ^{[2] : Предложение 4.7.1.}
• Для любого Y такого, что ${\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)}$$
  не является гипервыпуклым. ^{[2] : Предложение 4.7.2} (« (T(X),δ) — гипервыпуклая оболочка (X,d) .»)
• Пусть – гипервыпуклое метрическое пространство с и . Если для всех I с не является сверхвыпуклым, то и (T(X) , δ) изометричны . ^{[2] : Предложение 4.7.1} («Каждая гипервыпуклая оболочка (X,d) изометрична (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 )}$

Примеры

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

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

• На рисунке изображен набор X из 16 точек на плоскости; чтобы сформировать конечное метрическое пространство из этих точек, мы используем манхэттенское расстояние ( расстояние ℓ ¹ ). ^[8] Синяя область, показанная на рисунке, представляет собой ортогональную выпуклую оболочку , набор точек 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 ( ) точек в R ^X , вещественное векторное пространство размерности n . С другой стороны, если мы рассмотрим размерность T ( X ) как многогранный комплекс , Девелин (2006) показал, что при подходящем общем предположении о метрике это определение приводит к пространству с размерностью от n /3 до н /2. ${\displaystyle n\in \mathbb {Z} _{\geq 0}}$

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

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

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

Приложения

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

Смотрите также

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

Примечания

1. Платье, Хубер и Моултон (2001).
2. Хамси, Мохамед А .; Кирк, Уильям А. (2001). Введение в метрические пространства и теорию неподвижной точки . Уайли.
3. Платье abc, Андреас ; Хубер, Катарина Т .; Кулен, Якобус; Моултон, Винсент; Спилнер, Андреас (2012). Основы филогенетической комбинаторики . Издательство Кембриджского университета. ISBN 978-0-521-76832-0.
4. Хьюсон, Дэниел Х.; Рупп, Регула; Скорнавакка, Селин (2010). Филогенетические сети: концепции, алгоритмы и приложения . Издательство Кембриджского университета. ISBN 978-0-521-75596-2.
5. Деза, Мишель Мари ; Деза, Елена (2014). Энциклопедия расстояний (Третье изд.). Спрингер. п. 47. ИСБН 978-3-662-44341-5.
6. Меллерей, Жюльен (2008). «Некоторые геометрические и динамические свойства пространства Урысона». Топология и ее приложения . 155 (14): 1531–1560. дои : 10.1016/j.topol.2007.04.029 .
7. Беньямини, Йоав ; Линденштраусс, Йорам (2000). Геометрический нелинейный функциональный анализ . Американское математическое общество. п. 32. ISBN 978-0-8218-0835-1.
8. В двух измерениях Манхэттенское расстояние изометрично после вращения и масштабирования до расстояния ℓ ∞ , поэтому с этой метрикой плоскость сама по себе инъективна, но эта эквивалентность между ℓ ¹ и ℓ ^∞ не соблюдается в более высоких измерениях.
9. Хробак и Лармор (1994).

1. Хамси и Кирк используют это условие в своем определении.
2. Доказательство Хамси и Кирка показывает одно следствие эквивалентности условию, указанному выше. Другой вывод нетрудно показать.
3. То есть карта Куратовского. Карту Куратовского мы представим ниже. ${\displaystyle e(x)\in T(X).}$
4. Супремум достигается при y=x .
5. Супремум достигается при y=x .

Рекомендации

• Чепой, Виктор (1997), « Подход AT _X к некоторым результатам по разрезам и метрикам», « Достижения в области прикладной математики» , 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.

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

• Йосвиг, Михаэль, Узкие пролеты.