独立コンプレックス
Gの独立複合体

グラフの独立複体は、グラフの独立集合を記述する数学的対象である。正式には、無向グラフGの独立複体（ I( G )と表記）は、Gの独立集合の頂点集合によって形成される抽象的な単体複体（すなわち、部分集合をとる操作に関して閉じた有限集合の族）である。独立集合の任意の部分集合はそれ自体が独立集合であるため、I( G )は部分集合をとる操作に関して閉じている。

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

ホモロジー群

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

1. G の全支配数 は、 Gの全支配集合（集合Sにおいて、 V のすべての頂点がSの頂点に隣接するような集合）の最小の基数である。その場合となる。[ 2 ]γ0（G）{\displaystyle \gamma _{0}(G)}γ0（G）>け{\displaystyle \gamma _{0}(G)>k}H〜け−1（私（G））＝0{\displaystyle {\tilde {H}}_{k-1}(I(G))=0}

2. G におけるVの部分集合Aの全支配数（ ）は、集合SにおいてAのすべての頂点がSの頂点に隣接するような最小の基数である。Gの独立支配数（ ）は、 Gにおけるすべての独立集合A上 の の最大値である。 ならば 、 である。[ 1 ] [ 3 ]γ0（G、あ）{\displaystyle \gamma_{0}(G,A)}私γ（G）{\displaystyle i\gamma (G)}γ0（G、あ）{\displaystyle \gamma_{0}(G,A)}私γ（G）>け{\displaystyle i\gamma (G)>k}H〜け−1（私（G））＝0{\displaystyle {\tilde {H}}_{k-1}(I(G))=0}

3. Gの支配数（）は、 G の支配集合（ V \ S のすべての頂点がSの頂点に隣接するような集合S ）の最小濃度である。 に留意する。Gが弦グラフである場合、となる。[ 4 ]γ（G）{\displaystyle \gamma (G)}γ0（G）≥γ（G）{\displaystyle \gamma _{0}(G)\geq \gamma (G)}γ（G）>け{\displaystyle \gamma (G)>k}H〜け−1（私（G））＝0{\displaystyle {\tilde {H}}_{k-1}(I(G))=0}

4. Gの誘導マッチング数（と表記）は、Gにおける誘導マッチング（部分集合内の任意の2頂点を結ぶすべての辺を含むマッチング）の最大濃度である。Vの部分集合Aが存在し、 となる場合、 となる。[ 5 ]これは、 上記の性質 1 と 2 の両方を一般化したものである。 μ（G）{\displaystyle \mu (G)}γ0（G、あ）>け+分[け、μ（G[あ]）]{\displaystyle \gamma_{0}(G,A)>k+\min[k,\mu(G[A])]}H〜け−1（私（G））＝0{\displaystyle {\tilde {H}}_{k-1}(I(G))=0}

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

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

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

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

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

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

参照

参考文献

  1. ^ a b c d Meshulam, Roy (2003-05-01). 「支配数とホモロジー」 . Journal of Combinatorial Theory, Series A. 102 ( 2): 321– 330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN  0097-3165 .
  2. ^ Chudnovsky, Maria (2000).分離代表システム（修士論文） . ハイファ（イスラエル）：テクニオン大学数学部.
  3. ^ Aharoni, Ron; Haxell, Penny (2000). 「ハイパーグラフに対するホールの定理」. Journal of Graph Theory . 35 (2): 83– 88. doi : 10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v . ISSN 0364-9024 . 
  4. ^ロン、アハロニ;バーガー、イーライ。ジヴ、ラン (2002-07-01)。 「ケーニッヒの定理のツリー版」。コンビナトリカ。22 (3): 335–343 .土井: 10.1007/s004930200016。ISSN 0209-9683。S2CID 38277360。  
  5. ^ Meshulam, Roy (2001-01-01). 「クリーク複合体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89– 94. doi : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .  
  6. ^ Björner, A.; Lovász, L.; Vrećica, ST; Živaljević, RT (1994). 「チェスボード複体とマッチング複体」.ロンドン数学会誌. 49 (1): 25– 39. doi : 10.1112/jlms/49.1.25 . ISSN 1469-7750 . 
  7. ^ライナー、ビクター；ロバーツ、ジョエル (2000年3月1日). 「最小解像度とマッチング複体およびチェスボード複体のホモロジー」 .代数的組合せ論ジャーナル. 11 (2): 135– 154. doi : 10.1023/A:1008728115910 . ISSN 1572-9192 . 
  8. ^フリードマン, ジョエル; ハンロン, フィル (1998-09-01). 「チェス盤複体のベッティ数について」 .代数的組合せ論ジャーナル. 8 (2): 193– 203. doi : 10.1023/A:1008693929682 . hdl : 2027.42/46302 . ISSN 1572-9192 . 
  9. ^ Ziegler, Günter M. (1994-02-01). 「チェス盤複体のシェル可能性」. Israel Journal of Mathematics . 87 (1): 97– 110. doi : 10.1007/BF02772986 . ISSN 1565-8511 . S2CID 59040033 .  
「 https://en.wikipedia.org/w/index.php?title=Independence_complex&oldid=1285189182」より取得