徒党コンプレックス

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

無向グラフ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} が複体内にある場合のみです (このグラフは複体の1 スケルトンと呼ばれます)。旗状複体の定義により、ペアで接続されているすべての頂点の集合が複体内にあります。したがって、旗状複体はG上のクリーク複体に等しくなります。

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

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

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

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

任意のセル複合体Cの重心分割は、 Cのセルごとに 1 つの頂点を持つ旗状複合体です。重心分割の頂点のコレクションが単体を形成するのは、Cの対応するセルのコレクションが旗(セルの包含順序のチェーン)を形成する場合のみです。 ^[2]特に、2 次元多様体上のセル複合体の重心分割により、多様体のホイットニー三角形分割が生成されます。

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

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

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

Hodkinson と Otto (2003) は、リレーショナル構造のロジックにおける共形ハイパーグラフの応用について説明しています。そのコンテキストでは、リレーショナル構造のGaifman グラフは、その構造を表すハイパーグラフの基礎となるグラフと同じであり、構造が共形ハイパーグラフに対応する場合は ガードされます。

グロモフは、立方体複合体（つまり、面と面が交差する超立方体の族）がCAT(0)空間を形成するのは、複合体が単連結であり、すべての頂点のリンクが旗状複合体を形成する場合のみであることを示した。これらの条件を満たす立方体複合体は、キュービングまたは壁付き空間と呼ばれることがある。^{[1] [6]}

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

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

すると、クリーク複体X( G )のj番目の縮小ホモロジーは、 0から までの任意のjに対して自明である。 ${\displaystyle \max(lt,\lfloor {l}/{2}\rfloor )-1}$

• 単体グラフ、基になるグラフの各クリークごとに 1 つのノードを持つグラフの一種
• 分割マトロイド、マトロイド交差がクリーク複合体を形成する可能性のあるマトロイドの一種

• Bandelt, H.-J.; Chepoi, V. (2008)、「メトリック グラフ理論と幾何学: 概観」、Goodman, JE ; Pach, J. ; Pollack, R. (編)、離散幾何学と計算幾何学に関する概観: 20 年後(PDF)、Contemporary Mathematics、第 453 巻、プロビデンス、RI: AMS、pp. 49–86。
• ベルゲ、C. (1989)、ハイパーグラフ：有限集合の組合せ論、ノースホランド、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。
• Hodkinson, I.; Otto, M. (2003)、「有限構造における有限共形ハイパーグラフ被覆と Gaifman クリーク」、The Bulletin of Symbolic Logic、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。