タイトスパン

計量幾何学において、計量空間Mの計量包（きょうりょくほう）あるいはタイトスパン（きょうりょくほう）は、 M を埋め込むことができる単射な計量空間である。ある意味では、 Mの点「間」にあるすべての点から成り、ユークリッド空間における点集合の凸包に類似している。タイトスパンは、Mの単射包あるいは超凸包とも呼ばれる。また、単射包とも呼ばれるが、代数学における加群の単射包と混同してはならない。後者は、計量空間ではなくR加群の圏に関して同様の説明が可能な概念である。

タイトスパンはIsbell (1964)によって初めて記述され、1960年代にHolsztyńskiによって研究・応用されました。その後、 Dress (1984)とChrobak & Larmore (1994)によって独立に再発見されました。この歴史についてはChepoi (1997)を参照してください。タイトスパンはT理論の中心的な構成の一つです。

意味

距離空間のタイトスパンは次のように定義できる。( X , d )を距離空間とし、T ( X )をX上の極値関数の集合とする。ここで、 X上の極値関数とは、 XからRへの関数fであって、

1. X の任意のx、yに対して、d ( x、y ) ≤ f ( x ) + f ( y ) であり、
2. Xの各xに対して、f(x) = sup{ d(x,y) - f(y):y in X } が成り立つ。^{[ 1 ] : 124}

特に（上記の性質1においてx = yとした場合）、すべてのxに対してf ( x ) ≥ 0 が成り立ちます。上記の最初の要件を解釈する一つの方法は、f が、ある新しい点からX内の点までの可能な距離の集合を定義し、それらの距離は ( X , d )の距離と共に三角不等式を満たす必要がある、というものです。2番目の要件は、これらの距離はどれも三角不等式に違反することなく縮めることはできない、というものです。

(X,d)のタイトスパンは計量空間(T(X),δ) であり、は ℓ ^∞ノルム によって誘導される計量に類似しています。 ( dが有界である場合、 δ はℓ ^∞ノルムによって誘導される計量によって誘導される部分空間計量です。dが有界でない場合は、X上のすべての極値関数は有界ではないため、 となります。 いずれにせよ、 T(X)の任意のf,gについて、差は に属し、つまり は有界であると言えます。) $${\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)}$

極値関数の同等の定義

最初の要件を満たすXからRへの関数fの場合、2 番目の要件の次のバージョンは同等です。

• X内の各xについて、f(x) = sup{ d(x,y) - f(y):y in X } です。
• fは前述の最初の要件に関して点ごとに最小である。つまり、XからRへの任意の関数gに対して、 Xのすべてのx,yに対してd(x,y) ≤ g(x) + g(y) が成り立つように、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が有限である場合、最初の要件を満たすXからRへの任意の関数fについて、2 番目の要件は、 X内の各xに対して、 f ( x ) + f ( y ) = d ( x , y )となるようなX内のyが存在するという条件と同等です。(の場合、両方の条件が真です。 の場合、上限が達成され、最初の要件は同等性を意味します。)${\displaystyle X=\emptyset ,}$ ${\displaystyle X\neq \emptyset ,}$
• |X|=2とし、 X={a,b}となるような異なる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)\}}$
• X上のすべての極値関数fはKatetovである: ^{[ 5 ] [ 6 ] : 第 2 節} f は最初の要件を満たし、または同値として、f は最初の要件を満たし、(は 1- Lipschitz )、または同値として、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上の離散計量とし、f​​ = {(a,1),(b,2)}とすると、 fはカテトフ関数であるが極限関数ではない。( fがカテトフ関数であることはほぼ明らかである。fが極限関数でないのは、この節の3番目の箇条書きの性質を満たしていないためである。)
• dが有界ならば、 T(X)のすべてのfも有界である。実際、T(X)のすべてのfに対して、(注) (上の節の3番目の同値な性質から導かれる。)${\displaystyle \|f\|_{\infty }\leq \|d\|_{\infty }.}$ ${\displaystyle d\in \ell ^{\infty }(X\times X).}$
• dが無限大であれば、T(X)内のすべてのfは無限大である。（最初の要件から従​​う。）
• ${\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)は等連続であることを示したので、Arzelà–Ascoli の定理によれば、 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 }}$
• 最初の要件を満たすXからRへの任意の関数gに対して、 T(X)にfが存在し、 f≤gが各点ごとに成り立つ。^{[ 2 ]：補題4.4}
• X上の任意の極値関数fに対して、^{[ 2 ]：命題4.6.1 [注5 ]}${\displaystyle \forall x\in X\quad f(x)=\sup\{|f(y)-d(x,y)|:y\in X\}.}$
• T(X)の任意のf,gについて、差は に属します。つまり、 は有界です。(上記の箇条書きを使用してください。)${\displaystyle g-f}$ ${\displaystyle \ell ^{\infty }(X)}$
• クラトフスキー写像^{[ 4 ] :125} は等長写像である。( X =∅のとき結果は明らかである。X≠∅のとき逆三角不等式から結果が導かれる。)${\displaystyle e:=((d(x,y))_{y\in X})_{x\in X}}$
• T(X)にfをおく。Xの任意のaに対して、f(a)=0ならばf=e(a) となる。^{[ 3 ]：補題5.1} （ Xの任意のxに対して、次が成り立つ。fの最小性（上の節の2番目の同等な特徴付け）と、最初の要件を満たすことから、次が成り立つ。）${\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}

超凸性特性

• (T(X),δ)と(T(X),δ)はともに超凸である。^{[ 2 ]：命題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)}$$
• 超凸でない任意のYについて。 ^{[ 2 ]：命題4.7.2} （「（T（X）、δ）は（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)}$$
• を超凸計量空間とし、を超凸とします。任意の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とし、 X={a,b,c}となるような異なる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} 参照)$${\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).}$

マンハッタン計量を持つ平面上の点の集合に連結された直交凸包がある場合、その凸包は点のタイトスパンと一致します。

• 図は、平面上の 16 点の集合Xを示しています。これらの点から有限距離空間を形成するために、マンハッタン距離( ℓ ¹距離 ) を使用します。^{[ 8 ]}図に示されている青い領域は直交凸包、つまり、z を頂点とする4 つの閉じた象限のそれぞれにXの点が含まれるような点zの集合です。このような点zは、タイト スパンの点に対応します。点zに対応する関数f ( x ) は、 f ( x ) = d ( z , x )です。この形式の関数は、マンハッタン距離の三角不等式により、マンハッタン距離平面の任意のzに対してタイト スパンのプロパティ 1 を満たします。タイト スパンのプロパティ 2 を示すために、 X内のある点x を考えます。 f ( x )+ f ( y )= d ( x , y )となるようなX内のy を見つけなければなりません。しかし、x がz を頂点とする4つの象限のいずれかにある場合、 y は反対の象限の任意の点とすることができるため、性質2も満たされます。逆に、タイトスパンの任意の点は、このようにしてこれらの点の直交凸包の点に対応することが示されます。ただし、マンハッタン計量を持つ高次元の点集合、および直交包が分離している平面点集合の場合、タイトスパンは直交凸包とは異なります。

Xが有限の場合のタイトスパンの寸法

上記の定義は、n ( ) 点の集合のタイトスパンT ( X ) を、 n次元の実ベクトル空間R ^Xに埋め込むものである。一方、T ( X )の次元を多面体複体とみなすと、Develin (2006) は、計量に関する適切な一般位置仮定のもとで、この定義はn /3 からn /2の間の次元を持つ空間につながることを示した。 ${\displaystyle n\in \mathbb {Z} _{\geq 0}}$

代替定義

ホルシュティンスキ (1968)は、その部分空間を対象とする計量空間の概念に基づく別の定義を提示した。彼は、バナッハ空間の入射的包絡線が、バナッハ空間の圏において（線型構造を忘れた後に）タイトスパンと一致することを証明した。この定理により、特定の問題を任意のバナッハ空間から C(X) の形のバナッハ空間（X はコンパクト空間）へと帰着させることができる。

Develin & Sturmfels (2004)は、有限計量空間のタイトスパンを、空間内の各点から他の各点までの距離ベクトルのトロピカル凸包として定義する別の方法を提案した。しかし、同年後半に彼らは、 Erratum Develin & Sturmfels (2004a)において、トロピカル凸包は常にタイトスパンを含むものの、必ずしもタイトスパンと一致するとは限らないことを認めた。

アプリケーション

• Dress、Huber、Moulton (2001) は、生物学的データから進化樹を再構築する際のタイトスパンの応用について説明しています。
• タイトスパンはKサーバー問題に対するいくつかのオンラインアルゴリズムで役割を果たしている。^{[ 9 ]}
• Sturmfels & Yu (2004)は、タイト スパンを使用して、最大 6 つのポイントでメトリック空間を分類します。
• Chepoi (1997)はタイトスパンを使用して、カットメトリックをより一般的な有限メトリック空間にパッキングすることに関する結果を証明しました。

参照

• クラトフスキー埋め込みは、クラトフスキー写像と同様に定義されたバナッハ空間への任意の距離空間の埋め込みである。
• 単射距離空間

注記

1. ドレス、フーバー＆モールトン（2001）。
2. Khamsi, Mohamed A. ; Kirk, William A. (2001).計量空間と不動点理論入門. Wiley.
3. ドレス, アンドレアス;フーバー, カタリーナ・T.;クーレン, ヤコブス; モールトン, ヴィンセント; スピルナー, アンドレアス (2012). 『基礎系統学的組合せ論』 ケンブリッジ大学出版局. ISBN 978-0-521-76832-0。
4. ダニエル・H・ヒューソン、レギュラ・ラップ、セリーヌ・スコルナヴァッカ（2010年）『系統発生ネットワーク：概念、アルゴリズム、応用』ケンブリッジ大学出版局、ISBN 978-0-521-75596-2。
5. Deza, Michel Marie ; Deza, Elena (2014). 『距離百科事典（第3版）』 Springer. p. 47. ISBN 978-3-662-44341-5。
6. Melleray, Julien (2008). 「ウリゾーン空間の幾何学的および動的性質」 .トポロジーとその応用. 155 (14): 1531– 1560. doi : 10.1016/j.topol.2007.04.029 .
7. ベニャミニ、ヨアブ、リンデンシュトラウス、ジョラム(2000).幾何学的非線形関数解析. アメリカ数学会. p. 32. ISBN 978-0-8218-0835-1。
8. 2次元では、マンハッタン距離は回転およびℓ ^∞距離へのスケーリング後に等長になるため、この測定基準では平面自体は単射ですが、 ℓ ¹とℓ ^∞の間のこの同値性は高次元では保持されません。
9. Chrobak & Larmore (1994) .

1. KhamsiとKirkはこの条件を定義に使用しています。
2. カムシとカークの証明は、この同値性の1つの含意を上記の条件と示している。もう1つの含意は示すのが難しくない。
3. すなわち、クラトフスキー写像以下ではクラトフスキー写像を紹介します。${\displaystyle e(x)\in T(X).}$
4. y=xのとき最大値が達成されます。
5. y=xのとき最大値が達成されます。

参考文献

• Chepoi, Victor (1997)、「カットとメトリクスに関するいくつかの結果へのTXアプローチ」、応用数学の進歩、19 (4): 453– 470、doi : 10.1006/ _{aama.1997.0549}。
• Chrobak, Marek ; Larmore, Lawrence L. (1994)、「寛大さは3つのサーバーのための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 。
• マイク・デベリン; Sturmfels、Bernd (2004)、「Tropical convexity」(PDF)、Documenta Mathematica、9 : 1–27、doi : 10.4171/dm/154、S2CID  64471。
• マイク・デベリン; Sturmfels、Bernd (2004a)、「「Tropico Convexity」の正誤表」（PDF） , Documenta Mathematica , 9 : 205– 206, doi : 10.4171/dm/154 , S2CID  64471。
• ドレス、アンドレアス・WM（1984）、「木、距離空間のタイト拡張、および特定の群のコホモロジー次元」、数学の進歩、53（3）：321-402、doi：10.1016/0001-8708（84）90029-X。
• ドレス、アンドレアス・WM ;フーバー、KT ; モールトン、V. (2001)、「純粋数学と応用数学における計量空間」(PDF)、ドクメンタ・マテマティカ、ドクメンタ・マテマティカ・シリーズ、2 (Proceedings Quadratic Forms LSU): 121– 139、doi : 10.4171/dms/2/5、ISBN 978-3-98547-042-6。
• Holsztyński, Włodzimierz (1968)、「バナッハ空間の等長埋め込みの線形化。計量包絡線。」Bull. Acad. Polon. Sci.、16 : 189– 193。
• イズベル, JR (1964)、「単射距離空間に関する6つの定理」、Comment. Math. Helv.、39 : 65– 76、doi : 10.1007/BF02566944、S2CID  121857986。
• Sturmfels, Bernd ; Yu, Josephine (2004)、「6点計量の分類」、The Electronic Journal of Combinatorics、11 : R44、arXiv : math.MG/0403147、Bibcode : 2004math......3147S、doi : 10.37236 /1797、S2CID 6733896 。

外部リンク

• ヨスウィグ、マイケル、タイトスパン。