タイトスパン

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

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

距離空間のタイトスパンは次のように定義できる。 ( 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 です。上記の最初の要件を解釈する 1 つの方法は、f が、 ( X、d )の距離とともに三角不等式を満たす必要がある、ある新しい点からX内の点までの可能な距離の集合を定義するというものです。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はカテトフである: ^{[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 in X を}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 gf}$${\displaystyle \ell ^{\infty }(X)}$
• クラトフスキー写像^{[4] :125} は等長写像である。( X =∅のとき、結果は明らかである。X≠∅のとき、逆三角不等式は結果を暗示する。)${\displaystyle e:=((d(x,y))_{y\in X})_{x\in X}}$
• f をT(X)とする。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),δ)と両方とも超凸である。^{[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 も満たされます。逆に、タイト スパンのあらゆる点は、このようにしてこれらの点の直交凸包内の点に対応することが示されます。ただし、マンハッタン メトリックがより高い次元にある点集合、および分離した直交包を持つ平面点集合の場合、タイト スパンは直交凸包とは異なります。

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

距離空間の概念に基づく別の定義は、その部分空間に向けられたもので、Holsztyński (1968) によって記述されました。彼は、バナッハ空間の入射的なエンベロープが、バナッハ空間のカテゴリにおいて、(線形構造を忘れた後に) タイトスパンと一致することを証明しました。この定理により、特定の問題を任意のバナッハ空間から、X がコンパクト空間である形式 C(X) のバナッハ空間に還元できます。

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

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

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

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