独立コンプレックス

グラフの独立複体は、グラフの独立集合を記述する数学的オブジェクトです。正式には、無向グラフGの独立複体はI( G ) と表記され、Gの独立集合の頂点の集合によって形成される抽象的な単体複体(つまり、部分集合を取る操作に関して閉じた有限集合の族)です。独立集合の任意の部分集合はそれ自体が独立集合であるため、 I( G ) は確かに部分集合を取る操作に関して閉じています。

グラフ内のすべての独立集合は、その補グラフ内のクリークであり、その逆もまた同様です。したがって、グラフの独立複体は、その補グラフのクリーク複体に等しく、その逆もまた同様です。

グラフG = ( V , E )の性質と独立複体I( G )のホモロジー群との関係を研究した著者は数人いる。^[1] 特に、Gの支配集合に関連するいくつかの性質は、I( G )のいくつかの縮小ホモロジー群が自明であることを保証する。

1. G の全 支配数はと表記され、Gの全支配集合( V のすべての頂点がSの頂点に隣接するような集合S )の最小濃度です。 のとき です。[ ^2]${\displaystyle \gamma _{0}(G)}$${\displaystyle \gamma _{0}(G)>k}$${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

2. G におけるVの部分集合Aの全支配数 は、 Aのすべての頂点がSの頂点に隣接するような集合Sの最小濃度です。G の独立支配数 は、 G内のすべての独立集合Aにおける の最大値です。 の とき、 です。^{[1] [3]}${\displaystyle \gamma _{0}(G,A)}$${\displaystyle i\gamma (G)}$${\displaystyle \gamma _{0}(G,A)}$${\displaystyle i\gamma (G)>k}$${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

3. Gの支配数（ ）は、 G の支配集合（ V \ S のすべての頂点がSの頂点に隣接するような集合S ）の最小濃度です。 に注意してください。 G が弦グラフである場合、となります。^[4]${\displaystyle \gamma (G)}$${\displaystyle \gamma _{0}(G)\geq \gamma (G)}$${\displaystyle \gamma (G)>k}$${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

4. Gの誘導マッチング数はと表記され、 Gの誘導マッチング（部分集合内の任意の 2 つの頂点を接続するすべての辺を含むマッチング）の最大濃度です。Vの部分集合Aが存在して となる場合、 となります。^[5] これは、上記の性質 1 と 2 の両方を一般化したものです。 ${\displaystyle \mu (G)}$${\displaystyle \gamma _{0}(G,A)>k+\min[k,\mu (G[A])]}$${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

5. G の非支配独立複体I'( G ) は、 Gの支配集合ではない独立集合の抽象単体複体です。明らかに I'( G ) は I( G )に含まれます。包含写像を で表します。Gが弦グラフの場合、誘導写像はすべての に対して 0 です。^{[1] : Thm.1.4}これは上記の性質 3 の一般化です。 ${\displaystyle i:I'(G)\to I(G)}$${\displaystyle i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))}$${\displaystyle k\geq -1}$

6. G の分数星優位数は と表記され、 Gにおける分数星優位集合の最小サイズである。 のとき。[ ^{1] : Thm.1.5}${\displaystyle \gamma _{s}^{*}(G)}$${\displaystyle \gamma _{s}^{*}(G)>k}$${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$

メシュラムのゲームはグラフG上で行われるゲームであり、 Gの独立複体のホモロジー接続性の下限を計算するために使用できます。

グラフGのマッチング複体（M( G )と表記）は、 G内のマッチングの抽象単体複体である。これはGの線グラフの独立複体である。^{[6] [7]}

( m , n )-チェス盤複合体は、完全な二部グラフ K _m , _n上のマッチング複合体です。これは、 m行n列の チェス盤上のすべての位置の集合の抽象的な単体複合体であり、その上にルークを置くことで、ルーク同士が互いに脅威を与えることはありません。 ^{[8] [9]}

G のクリーク 複体は、 Gの補グラフの独立複体です。

• 虹独立集合