抽象単体複体

組合せ論において、抽象単体複体(ASC) は、抽象複体または単に複体と呼ばれることが多く、部分集合を取ることについて閉じている集合の族であり、すなわち、族内の集合のすべての部分集合は、族にも含まれる。これは、幾何学的概念である単体複体の純粋に組合せ論的な記述である。^[1]たとえば、2次元の単体複体では、族内の集合は三角形 (サイズ 3 の集合)、その辺 (サイズ 2 の集合)、およびその頂点 (サイズ 1 の集合) である。

マトロイドやグリードイドの文脈では、抽象単体複体は独立系とも呼ばれる。^[2]

抽象的な単体は、そのスタンレー・ライスナー環を形成することによって代数的に研究することができ、これにより組合せ論と可換代数の間に強力な関係が確立されます。

集合Sの空でない有限部分集合の集合Δ は集合族と呼ばれます。

集合族Δは、 Δ内のすべての集合Xとすべての空でない部分集合Y ⊆ Xに対して、集合YもΔに属する場合、抽象単体複体と呼ばれます。

Δに属する有限集合は複体の面と呼ばれ、面YはY ⊆ Xのとき別の面Xに属すると言われます。したがって、抽象単体複体の定義は、複体Δの面のすべての面はそれ自体がΔの面であると言い換えることができます。Δの頂点集合は、 V (Δ) = ∪Δ 、つまりΔのすべての面の和集合として定義されます。頂点集合の要素は複体の頂点と呼ばれます。 Δのすべての頂点vについて、集合 { v } は複体の面であり、複体のすべての面は頂点集合の有限部分集合です。

Δの最大の面(つまり、他の面の部分集合ではない面) は、複体の面と呼ばれます。Δの面 Xの次元は、 dim( X ) = | X | − 1と定義されます。つまり、1 つの要素からなる面は 0 次元、2 つの要素からなる面は 1 次元などです。複体dim(Δ)の次元は、その面の最大次元として定義されます。面の次元に有限の境界がない場合は、無限大になります。

複素数Δ は、面の数が有限である場合、または頂点集合が有限である場合に有限であると言われます。また、 Δ が有限次元（必ずしも有限である必要はない）であり、すべての面が同じ次元である場合、 Δ は純粋であると言われます。言い換えると、dim(Δ)が有限であり、すべての面が次元dim(Δ)の面に含まれる場合、 Δ は純粋です。

1 次元の抽象単体複体は、単純な 無向グラフと数学的に同等です。つまり、複体の頂点集合はグラフの頂点集合と見なすことができ、複体の 2 要素の面はグラフの無向辺に対応します。この見方では、複体の 1 要素の面は、接続辺を持たない孤立した頂点に対応します。

Δの部分複体は、 Lのすべての面がΔに属するような抽象単体複体Lです。つまり、L ⊆ Δであり、L は抽象単体複体です。 Δの単一の面のすべての部分集合で構成される部分複体は、しばしばΔの単体と呼ばれます。 (ただし、一部の著者は、非抽象 (幾何学的)単体複体の用語との類推により、面に対して「単体」という用語を使用したり、やや曖昧に、面と面に関連付けられた部分複体の両方に対して使用したりします。曖昧さを避けるため、この記事では抽象複体のコンテキストで面に対して「単体」という用語を使用しません)。

Δのdスケルトンは、 Δの次元が最大dであるすべての面からなるΔの部分複合体です。特に、1 スケルトンはΔの基礎グラフと呼ばれます。 Δの 0 スケルトンは頂点集合と同一視できますが、形式的にはまったく同じものではありません (頂点集合はすべての頂点の単一の集合ですが、 0 スケルトンは単一要素集合の族です)。

Δにおける面Yのリンクは、しばしばΔ/ Yまたはlk _Δ ( Y )と表記され、次のように定義される Δの部分複体である。

${\displaystyle \Delta /Y:=\{X\in \Delta \mid X\cap Y=\varnothing ,\,X\cup Y\in \Delta \}.}$

空集合のリンクはΔそのものであることに注意してください。

2つの抽象単体複体ΔとΓが与えられた場合、単体写像はΔの頂点をΓの頂点に写す関数 f であり 、 Δの任意の面Xに対して、像f  ( X )はΓの面であるという性質を持ちます。抽象単体複体を対象に、単体写像を射とするカテゴリ SCpx が存在します。これは、非抽象単体複体を使用して定義された適切なカテゴリと同等です。     

さらに、カテゴリカルな観点からは、抽象単体複体Δの基底集合SとΔの頂点集合V (Δ) ⊆ Sの関係を強めることができます。抽象単体複体のカテゴリを定義する目的では、 V (Δ)に含まれないSの要素は無関係です。より正確には、SCpxは次のカテゴリと同等です。

• オブジェクトは、すべてのシングルトンを含む空でない有限部分集合Δのコレクションを備えた集合Sであり、 XがΔに含まれ、Y ⊆ Xが空でない場合、YもΔに属します。
• ( S , Δ)から( T , Γ)への射とは、 Δの任意の元の像がΓの元となるような関数f  : S → Tのことである。

任意の抽象単体複体 (ASC) Kに、その幾何学的実現と呼ばれる位相空間 を関連付けることができます。 を定義する方法はいくつかあります。 ${\displaystyle |K|}$${\displaystyle |K|}$

すべての幾何学的単体複体(GSC) は ASC を決定します: ^{[3] : 14} ASC の頂点は GSC の頂点であり、ASC の面は GSC の面の頂点集合です。たとえば、4 つの頂点 {1,2,3,4} を持つ GSC を考えます。ここで、最大面は {1,2,3} 間の三角形と {2,4} と {3,4} 間の線です。すると、対応する ASC には集合 {1,2,3}、{2,4}、{3,4}、およびそれらのすべての部分集合が含まれます。GSC はASC の幾何学的実現であると言えます。

すべての ASC には、幾何学的実現があります。これは、有限 ASC については簡単にわかります。^{[3] : 14}とします。 の頂点を の ( N-1 ) 次元単体の頂点と同一視します。GSC { conv (F): F は K の面である} を構築します。明らかに、この GSC に関連付けられた ASC はKと同一であるため、確かにKの幾何学的実現を構築しました。実際、ASC ははるかに少ない次元を使用して実現できます。ASC がd次元の場合 (つまり、 の単体の最大濃度がd +1 の場合)、 で幾何学的実現がありますが、 では幾何学的実現がない可能性があります。 ^{[3] : 16} 特別な場合d =1は、共通の頂点を除いて互いに交差しない直線のエッジである任意のグラフをにプロットできるが、任意のグラフをこのようににプロットできるわけではないというよく知られた事実に対応します。 ${\displaystyle N:=|V(K)|}$${\displaystyle V(K)}$${\displaystyle \mathbb {R} ^{N}}$${\displaystyle \mathbb {R} ^{2d+1}}$${\displaystyle \mathbb {R} ^{2d}}$ ${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}}$

K が標準的な組み合わせn単体である場合、 は自然にΔ ⁿ と同一視できます。 ${\displaystyle |K|}$

同じASCの2つの幾何学的実現は、異なる次元のユークリッド空間であっても同相である。^{[3] : 14}したがって、ASC Kが与えられたとき、Kの幾何学的実現について語ることができる。

構築は次のようになります。まず、2 つの条件を満たす 関数からなるのサブセットとして定義します。${\displaystyle |K|}$${\displaystyle [0,1]^{S}}$${\displaystyle t\colon S\to [0,1]}$

${\displaystyle \{s\in S:t_{s}>0\}\in K}$

${\displaystyle \sum _{s\in S}t_{s}=1}$

ここで、有限台を持つの元の集合を、A がSの有限部分集合上を範囲とするの直接の極限として考え、その直接の極限に誘導位相 を与えます。次に、部分空間位相を与えます。 ${\displaystyle [0,1]^{S}}$${\displaystyle [0,1]^{A}}$${\displaystyle |K|}$

あるいは、Kの面が対象で、その射が包含関係にあるカテゴリを で表すものとします。次に、Kの頂点集合上の全順序を選択し、から位相空間のカテゴリへの関数F を次のように定義します。K内の次元nの任意の面Xについて、F ( X ) = Δ ^{n を}標準のn単体とします。頂点集合上の順序は、Xの要素とΔ ⁿの頂点との間の一意な一対一指定し、通常の方法e ₀ < e ₁ < ... < e _nで順序付けられます。 Y ⊆ Xが次元m < nの面である場合、この一対一指定によってΔ ⁿの一意のm次元面が指定されます。F ( Y ) → F ( X )を、 Δ ⁿの特定の面としてのΔ ^mの一意のアフィン線型埋め込みとして定義し、頂点上の写像が順序を保存するようにします。 ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$

幾何学的実現は関数Fの余極限 として定義できる。より具体的には、分離和の商空間 である。${\displaystyle |K|}$${\displaystyle |K|}$

${\displaystyle \coprod _{X\in K}{F(X)}}$

同値関係によって、任意の包含Y ⊆ Xに対して、点y ∈ F ( Y )と写像F ( Y ) → F ( X )によるその像が同一視される。

1. V を濃度 n + 1の有限集合とします。頂点集合Vを持つ組み合わせn単体は、面がすべてVの空でない部分集合である ASC です(つまり、 Vのべき集合です)。V = S = {0, 1, ..., n } の場合、この ASC は標準組み合わせn単体 と呼ばれます。

2. G を無向グラフとします。Gのクリーク複合体は 、面がすべてGのクリーク(完全サブグラフ)であるASCです。Gの独立複合体は、面がすべてGの独立集合である ASC です(G の補グラフのクリーク複合体です)。クリーク複合体は、旗複合体の典型的な例です。旗複合体は、その 2 要素サブセットがすべてK の面であるすべての集合がKの面であるという特性を持つ複合体Kです。

3. H をハイパーグラフとする。HのマッチングはHの辺の集合であり、2 つの辺はすべて互いに素である。Hのマッチング複合体は、面がすべてHのマッチングである ASC である。これはHの線グラフの独立複合体である。

4. P を半順序集合（poset）とする。 Pの順序複体は、面がすべてP内の有限鎖である ASC である。そのホモロジー群とその他の位相不変量には、 poset Pに関する重要な情報が含まれている。

5. M を距離空間、δを実数とします。Vietoris - Rips 複体は、面が直径が最大δであるMの有限部分集合である ASC です。これは、ホモロジー理論、双曲群、画像処理、モバイル アドホック ネットワーキングに応用されています。これは、フラグ複体の別の例です。

6.を多項式環の平方自由単項式イデアル（つまり、変数の部分集合の積によって生成されるイデアル）とします。すると、 に含まれないの平方自由単項式の指数ベクトルは、写像 を介して抽象単体複体を決定します。実際、n頂点上の（空でない）抽象単体複体とSの平方自由単項式イデアルの間には一対一の関係があります。が単体複体に対応する平方自由イデアルである場合、その商はのスタンレー・ライスナー環として知られています。 ${\displaystyle I}$ ${\displaystyle S=K[x_{1},\dots ,x_{n}]}$${\displaystyle S}$${\displaystyle I}$${\displaystyle \mathbf {a} \in \{0,1\}^{n}\mapsto \{i\in [n]:a_{i}=1\}}$ ${\displaystyle I_{\Delta }}$${\displaystyle \Delta }$ ${\displaystyle S/I_{\Delta }}$${\displaystyle {\Delta }}$

7.位相空間の任意の開被覆 Cに対して、 Cの神経複体は、空でない交差を持つCのサブファミリーを含む抽象的な単体複体です。

最大n 個のラベル付き要素（つまり、サイズnの集合S上）上の抽象単体複体の数は、 n番目のデデキント数より 1 少ない。これらの数は非常に急速に増加し、 n ≤ 9の場合のみ知られています。デデキント数は次のとおりです（n = 0 から開始）。

1、2、5、19、167、7580、7828353、2414682040997、56130437228687557907787、286386577668298411128469151667598498812365（OEISのシーケンスA014466 ）。これは、 n集合の部分集合の空でない反連鎖の数に対応する。

頂点がちょうどn個のラベル付き要素である抽象単体複合体の数は、 n = 1 から始まるシーケンス「1、2、9、114、6894、7785062、2414627396434、56130437209370320359966、286386577668298410623295216696338374471993」（OEISのシーケンスA006126）で与えられます。これは、ラベル付きn集合の反鎖被覆の数に対応します。n集合の反鎖被覆と、最大面に関して記述されたn個の要素上の単体複合体との間には明確な一対一性があります。

ちょうどn 個のラベルなし要素上の抽象単体複体の数は、 n = 1 から始まるシーケンス「1、2、5、20、180、16143、489996795、1392195548399980210」( OEISのシーケンスA006602 ) で与えられます。

単体複素認識問題とは、有限のASCが与えられたとき、その幾何学的実現が与えられた幾何学的オブジェクトと同相であるかどうかを判断することである。この問題は、d ≥ 5の任意のd次元多様体に対して決定不可能である^。[4]

拡大特性または交換特性と呼ばれる追加の特性を持つ抽象単体複体はマトロイドを生成します。次の式は項間の関係を示しています。

ハイパーグラフ = 集合族 ⊃ 独立系 = 抽象単体複合体 ⊃ マトロイド。

• クラスカル・カトーナ定理
• 単体集合