Тесный промежуток

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

В метрической геометрии метрическая оболочка или плотная оболочка метрического пространства 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),δ), где аналогично метрике, индуцированной нормой . (Если d ограничено, то δ — метрика подпространства, индуцированная метрикой, индуцированной нормой . Если d не ограничено, то каждая экстремальная функция на X неограничена и поэтому Независимо от этого будет верно, что для любых f,g в T(X) разность принадлежит , т. е. ограничена.) δ = ( инф { С Р 0 : | г ( х ) ф ( х ) | С  для всех  х Х } ) ф , г Т ( Х ) = ( г ф ) ф , г Т ( Х ) {\displaystyle \delta =(\inf\{C\in \mathbb {R} _{\geq 0}:|g(x)-f(x)|\leq C{\text{ для всех }}x\in X\})_{f,g\in T(X)}=(\|gf\|_{\infty })_{f,g\in T(X)}} Т ( Х ) ( Х ) . {\displaystyle T(X)\not \subseteq \ell ^{\infty }(X).} г ф {\displaystyle gf} ( Х ) {\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 , 0 ф ( х ) . {\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 ( x , y ). (Если , то оба условия верны. Если , то супремум достигается, и первое требование подразумевает эквивалентность.) Х = , {\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  Т ( Х ) = { ф ( Р 0 ) Х : ф ( а ) + ф ( б ) = г ( а , б ) } {\displaystyle T(X)=\{f\in (\mathbb {R} _{\geq 0})^{X}:f(a)+f(b)=d(a,b)\}} Т ( Х ) = { в ( Р 0 ) 2 : в 0 + в 1 = г ( 0 , 1 ) } {\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)⊆ C(X) . (Липшицевы функции непрерывны.)
  • T(X) равностепенно непрерывна . (Следует из того, что каждая экстремальная функция на X является 1-липшицевой; см. Равностепеннонепрерывность#Примеры .)
  • Не каждая функция Катетова на X является экстремальной. Например, пусть a , b различны, пусть X = {a,b}, пусть d = ([x≠y]) x,y в Xдискретная метрика на X , и пусть f = {(a,1),(b,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 Т(Х)} замкнуто относительно точечных пределов. Для любого точечно сходящегося ф ( Т ( Х ) ) ω , {\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 gf} ( Х ) {\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 е(а)} ф = е а . {\displaystyle f=e_{a}.}
  • (X,d) является гиперболическим тогда и только тогда, когда (T(X),δ) является гиперболическим. [3] : Теорема 5.3 

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

  • (T(X),δ) и оба являются гипервыпуклыми . [2] : Предложение 4.7.1  ( Х ( Т ( Х ) диапазон е ) , δ ( Т ( Х ) диапазон е ) × ( Т ( Х ) диапазон е ) ( δ ( е ( х ) , е ( у ) ) ) х , у Х ( δ ( е ( х ) , г ) ) х Х , г Т ( Х ) диапазон е ( δ ( ф , е ( у ) ) ф Т ( Х ) диапазон е , у Х ) {\displaystyle \left(X\cup (T(X)\setminus \operatorname {диапазон} e),\delta _{(T(X)\setminus \operatorname {диапазон} e)\times (T(X)\setminus \operatorname {диапазон} 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 {диапазон} e}\cup (\delta (f,e(y))_{f\in T(X)\setminus \operatorname {диапазон} e,y\in X}\right)}
  • Для любого Y такого, что не является гипервыпуклым. [2] : Предложение 4.7.2 (T(X),δ) является гипервыпуклой оболочкой (X,d) ».) диапазон е И Х ( Т ( Х ) диапазон е ) , {\displaystyle \operatorname {диапазон} e\subseteq Y\subsetneq X\cup (T(X)\setminus \operatorname {диапазон} e),} ( Х ( И диапазон е ) , δ ( И диапазон е ) × ( И диапазон е ) ( δ ( е ( х ) , е ( у ) ) ) х , у Х ( δ ( е ( х ) , г ) ) х Х , г И диапазон е ( δ ( ф , е ( у ) ) ф И диапазон е , у Х ) {\displaystyle \left(X\cup (Y\setminus \operatorname {диапазон} e),\delta _{(Y\setminus \operatorname {диапазон} e)\times (Y\setminus \operatorname {диапазон} e)}\cup (\delta (e(x),e(y)))_{x,y\in X}\cup (\delta (e(x),g))_{x\in X,g\in Y\setminus \operatorname {диапазон} e}\cup (\delta (f,e(y))_{f\in Y\setminus \operatorname {диапазон} e,y\in X}\right)}
  • Пусть — гипервыпуклое метрическое пространство с и . Если для всех 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(b,c). Тогда где [Добавьте рисунок. Подпись: Если X={0,1,2}, то T(X)=conv{(,,),(,,)} u conv{(,,),(,,)} u conv{(,,),(,,)} имеет форму буквы Y.] (Ср. [4] : 124  ) Т ( Х ) = { в ( Р 0 ) 3 : 1 = в а + в б , 2 = в а + в с , 3 в б + в с или  1 = в а + в б , 2 в а + в с , 3 = в б + в с или  1 в а + в б , 2 = в а + в с , 3 = в б + в с } = { в ( Р 0 ) 3 : в а ( я + дж ) к 2 , в б = я в а , в с = дж в а или  в а = я в б , в б ( я + к ) дж 2 , в с = к в б или  в а = дж в с , в б = к в с , в с ( дж + к ) я 2 } = { ( т , я т , дж т ) : т [ 0 , я дж ( я + дж ) к 2 ] } { ( я т , т , к т ) : т [ 0 , я к ( я + к ) дж 2 ] } { ( дж т , к т , т ) : т [ 0 , дж к ( дж + к ) я 2 ] } = { ( т , я т , дж т ) : т [ 0 , ( я + дж ) к 2 ] } { ( я т , т , к т ) : т [ 0 , ( я + к ) дж 2 ] } { ( дж т , к т , т ) : т [ 0 , ( дж + к ) я 2 ] } = конв { ( 0 , я , дж ) , х } конв { ( я , 0 , к ) , х } конв { ( дж , к , 0 ) , х } , {\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 = 2 1 ( i + j k , i + k j , j + k i ) . {\displaystyle x=2^{-1}(i+j-k,i+k-j,j+k-i).}
Если множество точек на плоскости с манхэттенской метрикой имеет связную ортогональную выпуклую оболочку , то эта оболочка совпадает с плотной оболочкой точек.
  • На рисунке показано множество X из 16 точек на плоскости; чтобы сформировать конечное метрическое пространство из этих точек, мы используем манхэттенское расстояние ( расстояние 1 ). [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 также выполняется. Обратно, можно показать, что каждая точка плотного промежутка соответствует таким образом точке в ортогональной выпуклой оболочке этих точек. Однако для множеств точек с манхэттенской метрикой в ​​более высоких размерностях и для плоских множеств точек с несвязными ортогональными оболочками плотный промежуток отличается от ортогональной выпуклой оболочки.

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

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

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

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

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

Приложения

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

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

Примечания

  1. ^ Дресс, Хубер и Молтон (2001).
  2. ^ abcdefgh Khamsi, Mohamed A. ; Kirk, William A. (2001). Введение в метрические пространства и теорию неподвижных точек . Wiley.
  3. ^ abc Dress, Andreas ; Huber, Katharina T. ; Koolen, Jacobus; Moulton, Vincent; Spillner, Andreas (2012). Basic Philogenetic Combinatorics . Cambridge University Press. ISBN 978-0-521-76832-0.
  4. ^ abc Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine (2010). Филогенетические сети: концепции, алгоритмы и приложения . Cambridge University Press. ISBN 978-0-521-75596-2.
  5. ^ Деза, Мишель Мари ; Деза, Елена (2014). Энциклопедия расстояний (третье изд.). Springer. стр. 47. ISBN 978-3-662-44341-5.
  6. ^ Меллерей, Жюльен (2008). «Некоторые геометрические и динамические свойства пространства Урысона». Топология и ее приложения . 155 (14): 1531–1560. doi : 10.1016/j.topol.2007.04.029 .
  7. ^ Беньямини, Йоав ; Линденштраус, Йорам (2000). Геометрический нелинейный функциональный анализ . Американское математическое общество. стр. 32. ISBN 978-0-8218-0835-1.
  8. ^ В двух измерениях манхэттенское расстояние изометрично после поворота и масштабирования до расстояния , поэтому с этой метрикой плоскость сама по себе инъективна, но эта эквивалентность между 1 и не выполняется в более высоких измерениях.
  9. ^ Хробак и Лармор (1994).
  1. ^ Хамси и Кирк используют это условие в своем определении.
  2. ^ Доказательство Хамси и Кирка показывает одно следствие эквивалентности условию, приведенному выше. Другое следствие нетрудно показать.
  3. ^ То есть, карта Куратовского. Ниже мы представим карту Куратовского. e ( x ) T ( X ) . {\displaystyle e(x)\in T(X).}
  4. ^ Супремум достигается при y=x .
  5. ^ Супремум достигается при y=x .

Ссылки

  • Чепой, Виктор (1997), «Подход A T X к некоторым результатам по разрезам и метрикам», Успехи в прикладной математике , 19 (4): 453–470, doi : 10.1006/aama.1997.0549.
  • Chrobak, Marek ; Larmore, Lawrence L. (1994), «Щедрость помогает или 11-конкурентный алгоритм для трех серверов», Журнал алгоритмов , 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), «Деревья, плотные расширения метрических пространств и когомологическая размерность некоторых групп», Advances in Mathematics , 53 (3): 321–402, doi : 10.1016/0001-8708(84)90029-X.
  • Дресс, Андреас В.М.; Хубер , К.Т .; Молтон, В. (2001), «Метрические пространства в чистой и прикладной математике» (PDF) , Documenta Mathematica (Труды по квадратичным формам LSU): 121–139.
  • Хольштынский, Влодзимеж (1968), «Линеаризация изометрических вложений банаховых пространств. Метрические оболочки», Bull. Acad. Polon. Sci. , 16 : 189–193.
  • Isbell, JR (1964), «Шесть теорем об инъективных метрических пространствах», Comment. Math. Helv. , 39 : 65–76, doi : 10.1007/BF02566944, S2CID  121857986.
  • Sturmfels, Bernd ; Yu, Josephine (2004), "Классификация шеститочечных метрик", The Electronic Journal of Combinatorics , 11 : R44, arXiv : math.MG/0403147 , Bibcode : 2004math......3147S, doi : 10.37236/1797, S2CID  6733896.
  • Йосвиг, Майкл, Узкие промежутки.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Tight_span&oldid=1251269070"