クリークコンプレックス
Abstract simplicial complex describing a graph's cliques
グラフのクリーク複合体。サイズ1のクリークは小さな赤い円盤で示され、サイズ2のクリークは黒い線分で示され、サイズ3のクリークは水色の三角形で示され、サイズ4のクリークは濃い青色の四面体で示されます。

クリーク複体、独立複体、旗複体、ホイットニー複体、および共形ハイパーグラフは、グラフ理論と幾何学的位相幾何学において密接に関連した数学的オブジェクトであり、それぞれ無向グラフのクリーク(完全なサブグラフ)を記述します。

クリークコンプレックス

無向グラフGのクリーク複体 X ( G )は、 Gのクリークに含まれる頂点の集合によって形成される抽象単体複体（つまり、部分集合を取る操作に関して閉じた有限集合の族）である。クリークの任意の部分集合はそれ自体がクリークであるため、この集合族は、族内の集合のすべての部分集合が族内にも含まれなければならないという抽象単体複体の要件を満たす。

クリーク複体は、k頂点からなる各クリークがk – 1次元の単体で表される位相空間とみなすこともできる。X ( G )の1 次元スケルトン（複体の基礎グラフとも呼ばれる）は、族内の 1 要素集合ごとに頂点を持ち、族内の 2 要素集合ごとに辺を持つ無向グラフであり、Gと同型である。[1]

否定的な例

すべてのクリーク複体は抽象単体複体ですが、その逆は真ではありません。例えば、極大集合{1,2,3}、{2,3,4}、{4,1}を持つ{1,2,3,4}上の抽象単体複体を考えてみましょう。もしこれがグラフGのX ( G )であるとすると、G は辺{1,2}、{1,3}、{2,3}、{2,4}、{3,4}、{4,1}を持つはずなので、 X ( G )はクリーク{1,2,3,4} も含むはずです。

独立コンプレックス

無向グラフGの独立複体 I ( G )は、 Gの独立集合の頂点集合によって形成される抽象的な単体複体である。 Gのクリーク複体は、Gの補グラフの独立複体と同値である。

旗複合体

旗複体は、 「2 決定性」と呼ばれる追加の特性を持つ抽象的な単体複体です。頂点のすべてのサブセットSについて、 S内のすべての頂点のペアが複体に含まれる場合、S自体も複体に含まれることになります。

すべてのクリーク複合体はフラグ複合体です。つまり、 S内のすべての頂点ペアがサイズ 2 のクリークである場合、それらの間にはエッジが存在するため、Sはクリークになります。

すべての旗複体はクリーク複体である。旗複体が与えられたとき、すべての頂点の集合上にグラフGを定義する。ここで、2つの頂点 u,v がG 上で隣接している場合、かつ {u,v} が複体に含まれる場合のみ、グラフ G は隣接するものとする（このグラフは複体の1-スケルトンと呼ばれる）。旗複体の定義により、2点連結されているすべての頂点集合は複体に含まれる。したがって、旗複体はG上のクリーク複体と等しい。

このように、旗状複体とクリーク複体は本質的に同じものです。しかし、多くの場合、グラフ以外のデータから派生したグラフのクリーク複体として間接的に定義するよりも、グラフ以外のデータから直接旗状複体を定義する方が便利です。[2]

ミハイル・グロモフは、Δ なしの条件を旗状複合体である条件として 定義しました。

ホイットニーコンプレックス

クリーク複体は、ハスラー・ホイットニーにちなんでホイットニー複体とも呼ばれる。2次元多様体のホイットニー三角形分割またはクリーン三角形分割は、すべての面が三角形ですべての三角形が面であるような方法で、グラフGを多様体上に埋め込むことである。グラフG がホイットニー三角形分割を持つ場合、それはGのホイットニー複体に同型なセル複体を形成する必要がある。この場合、複体（位相空間として見ると）は基礎となる多様体に同相である。グラフGは2次元多様体クリーク複体を持ち、 G が局所的に巡回的である場合に限り、ホイットニー三角形分割として埋め込むことができる。つまり、グラフ内のすべての頂点vについて、 vの近傍によって形成される誘導サブグラフは単一のサイクルを形成する。[3]

共形ハイパーグラフ

ハイパーグラフの主グラフ G ( H )とは、同じ頂点集合上のグラフで、同じハイパーエッジに一緒に現れる頂点のペアをそのエッジとして持つグラフのことである。主グラフのすべての極大クリークがハイパーエッジである場合、または同値として、主グラフのすべてのクリークが何らかのハイパーエッジに含まれている場合、ハイパーグラフは共形であるという。 [4]ハイパーグラフが下向きに閉じている（つまり、何らかのハイパーエッジに含まれているすべてのハイパーエッジを含む）必要がある場合、ハイパーグラフはまさにそれが旗複体であるときに共形である。これはハイパーグラフの言語と単体複体の言語を関連付けている。

例と応用

任意のセル複体Cの重心分割は、 Cのセルごとに1つの頂点を持つ旗状複体である。重心分割の頂点の集合が単体を形成するのは、対応するCのセルの集合が旗状（セルの包含順序における鎖）を形成する場合のみである。 [2]特に、2次元多様体上のセル複体の重心分割は、多様体のホイットニー三角形分割を生じる。

半順序集合の順序複体は、半順序の連鎖（全順序部分集合）から構成される。ある部分集合のすべてのペアがそれ自体順序付けられている場合、部分集合全体は連鎖となるため、順序複体は無Δ条件を満たす。これは、半順序の比較可能性グラフのクリーク複体として解釈できる。 [2]

グラフのマッチング複合体は、どの 2 つも端点を共有しない辺の集合から構成されます。この場合も、この集合族は no-Δ 条件を満たします。これは、与えられたグラフの線グラフの補グラフのクリーク複合体として見ることができます。マッチング複合体が文脈として特定のグラフなしで参照される場合、それは完全グラフのマッチング複合体を意味します。完全二部グラフK m , nのマッチング複合体は、チェスボード複合体として知られています。これは、ルークのグラフの補グラフのクリーク グラフであり、[5]その各単体は、 m  ×  nのチェス盤上でのルークの配置を表し、 2 つのルークが互いに攻撃することはありません。m = n ± 1 のとき、チェス ボード複合体は擬似多様体を形成します。

距離空間内の点の集合の Vietoris–Rips 複合体は、点の単位円グラフから形成されるクリーク複合体の特殊なケースです。ただし、すべてのクリーク複合体X (G) は、基礎となるグラフG上の最短経路距離の Vietoris–Rips 複合体として解釈できます。

ホドキンソンとオットー (2003) は、関係構造の論理における共形ハイパーグラフの応用について述べている。この文脈では、関係構造のガイフマングラフは、その構造を表すハイパーグラフの基底グラフと同じであり、構造が共形ハイパーグラフに対応する場合 、その構造はガードされているとされる。

グロモフは、立方体複体（すなわち、面と面が交わる超立方体の族）がCAT(0)空間を形成するための必要十分条件は、その複体が単連結であり、かつすべての頂点の連結が旗複体を形成する場合であることを示した。これらの条件を満たす立方体複体は、立方体または壁面を持つ空間と呼ばれることもある。[1] [6]

ホモロジー群

メシュラム[7]はクリーク複体のホモロジーに関する次の定理を証明している。整数 が与えられたとき、グラフGがと呼ばれる性質を満たすと仮定する。これは以下のことを意味する。 l ≥ 1 , t ≥ 0 {\displaystyle l\geq 1,t\geq 0} P ( l , t ) {\displaystyle P(l,t)}

  • G内の頂点のすべての集合には共通の隣接頂点があります。 l {\displaystyle l}
  • 頂点の集合Aが存在し、これはすべての頂点の集合に共通の隣接頂点を含んでいます。また、誘導グラフG [ A ] には、誘導サブグラフとして、t次元八面体球の1 スケルトンのコピーは含まれていません。 l {\displaystyle l}

すると、クリーク複体X( G )のj番目の縮小ホモロジーは0とjの間の任意のjに対して自明となる。 max ( l − t , ⌊ l / 2 ⌋ ) − 1 {\displaystyle \max(l-t,\lfloor {l}/{2}\rfloor )-1}

参照

注記

  1. ^ ab Bandelt & Chepoi (2008).
  2. ^ abc デイビス（2002年）。
  3. ^ ハーツフェルドとリンゲル (1991);ラリオン、ノイマン-ララ、ピザーニャ (2002)。マルニッチとモハール (1992)。
  4. ^ Berge (1989); Hodkinson & Otto (2003).
  5. ^ ドン＆ワックス（2002年）。
  6. ^ Chatterji & Niblo (2005).
  7. ^ Meshulam, Roy (2001-01-01). 「クリーク複体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89– 94. doi :10.1007/s004930170006. ISSN  1439-6912. S2CID  207006642.

参考文献

  • Bandelt, H.-J.; Chepoi, V. (2008)、「計量グラフ理論と幾何学：概説」、Goodman, JE ; Pach, J. ; Pollack, R. (編)、『離散幾何学と計算幾何学の概説：20年後』（PDF）、Contemporary Mathematics、第453巻、プロビデンス、ロードアイランド州：AMS、pp.  49– 86。
  • Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets , North-Holland, ISBN 0-444-87489-5。
  • Chatterji, I. ; Niblo, G. (2005 ) 、 「壁空間からCAT(0)立方体複体へ」、International  Journal of Algebra and Computation、15 ( 5– 6): 875– 885、arXiv : math.GT/0309036、doi:10.1142/S0218196705002669、S2CID 2786607。
  • Davis, MW (2002)、「非正曲率と反射群」、Daverman, RJ ; Sher, RB (編)、Handbook of Geometric Topology、Elsevier、pp.  373– 422。
  • Dong, X.; Wachs, ML (2002)、「マッチング複体の組合せラプラシアン」、Electronic Journal of Combinatorics、9 : R17、doi : 10.37236/1634。
  • ハーツフェルド、N.リンゲル、ゲルハルト (1991)、「きれいな三角形分割」、Combinatorica、11 (2): 145–155、doi :10.1007/BF01206358、S2CID  28144260。
  • ホドキンソン, I.; オットー, M. (2003)、「有限構造における有限共形ハイパーグラフ被覆とガイフマンクリーク」、記号論理学会誌、9 (3): 387– 405、CiteSeerX  10.1.1.107.5000、doi :10.2178/bsl/1058448678。
  • Larrión, F.; Neumann-Lara, V .; Pizaña, MA (2002)「ホイットニー三角分割、局所内周、反復クリークグラフ」、離散数学、258 ( 1– 3): 123– 135、doi : 10.1016/S0012-365X(02)00266-2。
  • Malnič, A.; Mohar, B. (1992)、「表面の局所的巡回三角形分割の生成」、Journal of Combinatorial Theory、シリーズB、56 (2): 147– 164、doi :10.1016/0095-8956(92)90015-P。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Clique_complex&oldid=1187440823"