클라이크 콤플렉스

그래프의 클라이크 콤플렉스.1 사이즈의 집단은 작은 붉은 원반으로 표시되고, 2 사이즈의 집단은 검은 선 세그먼트로 표시되며, 3 사이즈의 집단은 옅은 청색 삼각형으로 표시되며, 4 사이즈의 집단은 짙은 청색 사분면으로 표시된다.

클라이크 콤플렉스, 국기 콤플렉스, 등정 하이퍼그래프는 그래프 이론과 기하학적 토폴로지에서 수학 개체와 밀접하게 연관되어 있으며, 각각은 비방향 그래프의 클릭(완전한 서브그래프)을 기술하고 있다.

비방향 그래프 G의 clique complex X(G)는 G의 clique에 있는 정점 집합에 의해 형성된 추상적 단순 복합체(즉, 하위 집합을 취하기 위한 조작에 의해 닫힌 유한 집합의 패밀리)이다.어떤 집단의 하위 집합은 그 자체로 집단이기 때문에, 이 집단의 집합은 가족 내 집합의 모든 하위 집합도 또한 가족 내에 있어야 한다는 추상적인 단순화 콤플렉스의 요건을 충족한다.clique complex는 또한 k 정점의 각 clique가 치수 k - 1의 심플렉스(simplex)로 표현되는 위상학적 공간으로 볼 수 있다.X(G)의 1-골격(복합체의 기본 그래프라고도 함)은 패밀리에 설정된 모든 1-요소에 대한 꼭지점과 패밀리에 설정된 2-요소에 대한 가장자리가 있는 비방향 그래프로서 G에 대해 이형적이다.^[1]

클라이크 단지는 하슬러 휘트니의 뒤를 이어 휘트니 단지로도 알려져 있다.휘트니 삼각측량 또는 2차원 다지관의 깨끗한 삼각측량은 모든 얼굴이 삼각형이고 모든 삼각형이 얼굴일 수 있도록 다지관에 그래프 G를 내장한 것이다.그래프 G가 휘트니 삼각측량을 갖는다면 G의 휘트니 콤플렉스에 이형화된 세포 콤플렉스를 형성해야 한다.이 경우 복합체(위상학적 공간으로 보기)는 기저 다지관에 동형이다.그래프 G는 2-매니폴드 클라이크 콤플렉스를 가지고 있으며, G가 국소적으로 순환하는 경우에만 휘트니 삼각측량으로서 내장될 수 있다. 즉, 그래프의 모든 정점 v에 대해, v의 이웃에 의해 형성된 유도 서브그래프가 단일 사이클을 형성한다는 것을 의미한다.^[2]

G의 클라이크 콤플렉스는 G의 보완 그래프의 독립 콤플렉스에 해당한다.

모든 추상적인 단순화 콤플렉스가 패거리 콤플렉스는 아니다.예를 들어 최대 집합이 {1,2,3,}, {2,3,4}, {4,1}인 {1,2,3,4}에 대한 추상적 단순화 콤플렉스를 고려해 보십시오.만일 그것이 일부 그래프 G의 X(G)라면, G는 가장자리 {1,2}, {1,3}, {2,4}, {3,4}, {4,1}을(를) 가져야 했으므로 X(G)는 또한 {1,2,3,4}, {4,4},4}의 패거리도 포함해야 한다.

플래그 콤플렉스

플래그 콤플렉스는 추상적인 단순화 콤플렉스로, 모든 쌍이 콤플렉스의 면으로 되어 있는 정점의 집합 하나하나가 콤플렉스의 면이기도 하다.따라서 국기 단지와 패거리 단지는 본질적으로 같은 것이다.어떤 국기 콤플렉스라도 그 1스켈레톤에 속하는 클릭 콤플렉스다.단, 많은 경우, 해당 데이터에서 파생된 그래프의 클릭 콤플렉스로서 간접적으로 정의하기 보다는 그래프 이외의 일부 데이터에서 직접 플래그 콤플렉스를 정의하는 것이 편리하다.^[3]

미하일 그로모프는 Δ가 없는 상태를 국기 콤플렉스로 규정했다.

등각 하이퍼그래프

하이퍼그래프의 원초 그래프 G(H)는 동일한 합성어로 함께 나타나는 정점 쌍을 가장자리로 하는 동일한 정점 집합의 그래프다.하이퍼그래프는 원시 그래프의 모든 최대 집단이 혼합형일 경우 순응형이며, 원시 그래프의 모든 집단이 어떤 혼합형 안에 포함되어 있을 경우 동등하게 일치한다고 한다.^[4]하이퍼그래프를 아래쪽으로 닫아야 하는 경우(그래서 일부 합성물에 포함된 모든 합성물을 포함) 하이퍼그래프는 국기 복합체일 때 정확하게 일치한다.이것은 하이퍼그래프의 언어와 단순한 콤플렉스의 언어를 연관시킨다.

예제 및 응용 프로그램

세포 복합체 C의 편심분할은 세포당 하나의 꼭지점을 갖는 국기 복합체다.이심분할의 정점 집합은 C의 해당 셀 집합이 플래그(셀의 포함 순서에 있는 체인)를 형성하는 경우에만 심플렉스(simplex)를 형성한다.^[3]특히 2매니폴드에 있는 세포단지의 이심분할은 다지관의 휘트니 삼각측량을 낳는다.

부분 주문 세트의 주문 콤플렉스는 부분 주문의 체인(전체 주문 서브셋)으로 구성된다.일부 부분 집합의 모든 쌍이 자체 순서가 되면 전체 부분 집합이 체인이기 때문에 순서 복합체는 no-Δ 조건을 만족한다.부분순서의 비교가능성 그래프의 clique complex로 해석될 수 있다.^[3]

그래프의 일치 콤플렉스는 엔드포인트를 공유하는 두 개 없는 에지 집합으로 구성된다. 다시 말해, 이 집합 집합 집합은 Δ가 없는 조건을 만족한다.주어진 그래프의 선 그래프의 보완 그래프의 클라이크 콤플렉스로 볼 수 있다.어떤 특정한 그래프 없이 일치하는 콤플렉스를 컨텍스트로서 언급할 때, 그것은 완전한 그래프의 일치 콤플렉스를 의미한다.완전한 초당적 그래프 K의_m,n 매칭 콤플렉스는 체스판 콤플렉스로 알려져 있다.루크 그래프의 보완 그래프를 보여주는 클라이크 그래프인데,^[5] 각각의 단순화는 루크 두 마리가 서로 공격하지 않는 m × n 체스 판에 루크를 배치한 것을 나타낸다.m = n ± 1일 때 체스판 콤플렉스는 사이비 매니폴드를 형성한다.

미터법 공간의 점 집합의 베토리스-립스 콤플렉스는 포인트의 단위 디스크 그래프에서 형성된 클라이크 콤플렉스의 특수한 경우지만, 모든 클라이크 콤플렉스 X(G)는 기본 그래프 G에서 최단 경로 메트릭의 베토리스-립스 콤플렉스로 해석될 수 있다.

Hodkinson & Otto(2003)는 관계 구조 로직에서 일치 하이퍼그래프의 적용을 설명한다.그런 맥락에서 관계형 구조의 가이프만 그래프는 구조를 나타내는 하이퍼그래프의 기본 그래프와 같으며, 순응형 하이퍼그래프에 해당할 경우 구조가 보호된다.

그로모프는 입체복합체(즉, 대면 교차하는 하이퍼큐브 계열)가 단순히 콤플렉스를 연결하고 모든 꼭지점의 링크가 국기 콤플렉스를 형성하는 경우에만 CAT(0) 공간을 형성한다는 것을 보여주었다.이러한 조건을 충족하는 입체복합체를 입체형 또는 벽이 있는 공간이라고 부르기도 한다.^[1]^[6]

호몰로지 집단

므술람은^[7] 클라이크 콤플렉스의 호몰로지(homology)에 관한 다음과 같은 정리를 증명한다.정수 $l\geq 1,t\geq 0$ $l\geq 1,t\geq 0$ , $l\geq 1,t\geq 0$ $l\geq 1,t\geq 0$ $l\geq 1,t\geq 0$ ${\displaystyle l\geq$ 1 $, t\t\geq$ 0 $l\geq 1,t\geq 0$ 을(를) 지정하면 그래프 $P(l,t)$ 가 P $P(l,t)$ l $P(l,t)$ , t $P(l,t)$ ) {\ $displaystyle P(l$ ,t $)}$ 라는 속성을 만족한다고 가정해 보십시오 $P(l,t)$ 즉,

G의 $모든$ l $l$ 꼭지점 $l$ 세트에는 공통적인 이웃이 있다.
정점의 집합 A가 존재하며, 여기에는 $모든$ l $l$ 정점의 $l$ 집합에 대한 공통적인 인접성이 포함되며, 또한 유도 그래프 G[A]는 t-차원 팔면체의 1-골격의 복사본을 포함하지 않는다.

그러면 clique complex X(G)의 j번째 감소된 homology는 0과 $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ 사이의 j에 $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ 사소한 $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ 이다 $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ l $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ t $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ , $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ l $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ / $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ { $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ ) - 1 {\ $displaystyle \max$ (l-t $,\lfloor {l}/{2}\rfloor )-1$ .

참고 항목

심플렉스 그래프(Simplex graph), 기본 그래프의 각 클래스에 대해 하나의 노드를 갖는 그래프의 일종
칸막이 매트로이드(Partition matroid)는 매트로이드 교차로들이 집단 복합체를 형성할 수 있는 매트로이드의 일종이다.

메모들

^ ^a ^b 반델트 & 체포이(2008).
^ 하츠펠드 & 링겔(1991); 라리온, 노이만 라라 & 피사냐(2002);말니치&모하르(1992년).
^ ^a ^b ^c 데이비스(2002년).
^ 버지(1989년), 호지킨슨 & 오토(2003년).
^ 동앤워즈(2002년).
^ 채터지 & 니블로(2005년).
^ Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

참조

Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, vol. 453, Providence, RI: AMS, pp. 49–86.
Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation, 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669, S2CID 2786607.
Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B. (eds.), Handbook of Geometric Topology, Elsevier, pp. 373–422.
Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17, doi:10.37236/1634.
Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358, S2CID 28144260.
Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", 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, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258 (1–3): 123–135, doi:10.1016/S0012-365X(02)00266-2.
Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.

[bc-1] 반델트 & 체포이(2008).

[2] 하츠펠드 & 링겔(1991); 라리온, 노이만 라라 & 피사냐(2002);말니치&모하르(1992년).

[davis-3] 데이비스(2002년).

[4] 버지(1989년), 호지킨슨 & 오토(2003년).

[5] 동앤워즈(2002년).

[6] 채터지 & 니블로(2005년).

[:3-7] Meshulam, Roy (2001-01-01). "The Clique Complex and Hypergraph Matching". Combinatorica. 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search