Kompleks kliki

Zespół kliki grafu. Kliki o rozmiarze jeden są pokazane jako małe czerwone krążki; kliki rozmiaru dwa są pokazane jako czarne odcinki linii; kliki rozmiaru trzy są pokazane jako jasnoniebieskie trójkąty; a kliki rozmiaru cztery są pokazane jako ciemnoniebieskie czworościany.

Kompleksy klik , kompleksy niezależności, kompleksy flagowe , kompleksy Whitneya i konforemne hipergrafy są blisko spokrewnionymi obiektami matematycznymi w teorii grafów i topologii geometrycznej , z których każdy opisuje kliki (pełne podgrafy) grafu nieskierowanego .

Kompleks kliki

Zespół kliki $X (G)$ grafu nieskierowanego $G$ jest abstrakcyjnym kompleksem symplicjalnym (czyli rodziną skończonych zbiorów zamkniętych operacją przyjmowania podzbiorów), utworzonym przez zbiory wierzchołków w klikach $G$ . Każdy podzbiór kliki sam w sobie jest kliką, więc ta rodzina zbiorów spełnia wymaganie abstrakcyjnego uproszczonego kompleksu, zgodnie z którym każdy podzbiór zbioru w rodzinie powinien również należeć do rodziny.

Kompleks klik można również postrzegać jako przestrzeń topologiczną , w której każda klika $k$ wierzchołków jest reprezentowana przez simplex o wymiarze $k - 1$ . 1-szkielet X ( $; G) ($ znany również jako podstawowy graf zespołu) jest grafem nieskierowanym z wierzchołkiem dla każdego 1-elementowego zestawu w rodzinie i krawędzią dla każdego 2-elementowego zestawu w rodzinie jest izomorficzny z $G$ .

Negatywny przykład

Każdy kompleks kliki jest abstrakcyjnym kompleksem uproszczonym, ale nie jest odwrotnie. Rozważmy na przykład abstrakcyjny kompleks uproszczony nad ${1,2,3,4}$ z maksymalnymi zbiorami ${1,2,3},$ ${2,3,4},$ ${4,1}.$ Gdyby to był $X (G)$ jakiegoś grafu $G$ , to $G$ musiałby mieć krawędzie ${1,2},$ ${1,3},$ ${2,3},$ ${2,4},$ ${3,4},$ ${4,1},$ więc $X (G)$ powinien również zawierać klikę ${1,2,3,4}.$

Kompleks Niepodległości

Kompleks niezależności $I (G)$ grafu nieskierowanego $G$ jest abstrakcyjnym kompleksem symplicalnym utworzonym przez zbiory wierzchołków w niezależnych zbiorach $G$ . Kompleks klik $G$ $jest$ równoważny kompleksowi niezależności grafu dopełniacza G .

Kompleks flagowy

Kompleks flagowy to abstrakcyjny kompleks symplicalny z dodatkową właściwością zwaną „2-zdeterminowany”: dla każdego podzbioru S wierzchołków, jeśli każda para wierzchołków w S jest w zespole, to samo S również jest w zespole.

Każdy zespół kliki jest zespołem flagowym: jeśli każda para wierzchołków w S jest kliką o rozmiarze 2, to istnieje między nimi krawędź, więc S jest kliką.

Każdy zespół flag jest zespołem kliki: mając dany zespół flag, zdefiniuj graf G na zbiorze wszystkich wierzchołków, gdzie dwa wierzchołki u,v sąsiadują ze sobą w G iff {u,v} jest w zespole (ten graf nazywa się 1-szkielet kompleksu). Z definicji kompleksu flagowego każdy zbiór wierzchołków połączonych parami należy do kompleksu. Dlatego kompleks flagi jest równy zespołowi kliki na G .

Tak więc kompleksy flagowe i kompleksy klik są zasadniczo tym samym. Jednak w wielu przypadkach wygodniej jest zdefiniować kompleks flag bezpośrednio z niektórych danych innych niż wykres, a nie pośrednio jako zespół kliki wykresu wyprowadzonego z tych danych.

Michaił Gromow zdefiniował warunek no-Δ jako warunek bycia kompleksem flagowym.

kompleks Whitneya

Kompleksy klik są również znane jako kompleksy Whitneya , po Hasslerze Whitneyu . Triangulacja Whitneya lub czysta triangulacja dwuwymiarowej rozmaitości to osadzenie wykresu G $na$ rozmaitości w taki sposób, że każda ściana jest trójkątem, a każdy trójkąt jest ścianą. Jeśli graf $G$ ma triangulację Whitneya, musi tworzyć kompleks komórek, który jest izomorficzny z kompleksem Whitneya $G$ . W tym przypadku kompleks (postrzegany jako przestrzeń topologiczna) jest homeomorficzny w stosunku do leżącej u jego podstaw rozmaitości. Graf $G$ ma 2-rozmaitościowy kompleks kliki i może być osadzony jako triangulacja Whitneya wtedy i tylko wtedy, gdy $G$ jest lokalnie cykliczny ; oznacza to, że dla każdego wierzchołka $v$ grafu indukowany podgraf utworzony przez sąsiadów $v$ tworzy pojedynczy cykl.

Hipergraf konforemny

Graf pierwotny G ( H ) hipergrafu jest grafem na tym samym zbiorze wierzchołków, którego krawędziami są pary wierzchołków występujących razem w tej samej hiperkrawędzi . Mówimy, że hipergraf jest konforemny , jeśli każda maksymalna klika jego grafu pierwotnego jest hiperkrawędzią lub równoważnie, jeśli każda klika jego grafu pierwotnego jest zawarta w jakiejś hiperkrawędzi. Jeśli hipergraf musi być zamknięty w dół (a więc zawiera wszystkie hipergrafy, które są zawarte w jakiejś hipergrafie), to hipergraf jest konforemny dokładnie wtedy, gdy jest kompleksem flagowym. Wiąże to język hipergrafów z językiem uproszczonych kompleksów.

Przykłady i zastosowania

Podział barycentryczny dowolnego kompleksu komórek C jest kompleksem flagowym mającym jeden wierzchołek na komórkę C . Zbiór wierzchołków podziału barycentrycznego tworzy simpleks wtedy i tylko wtedy, gdy odpowiedni zbiór komórek C tworzy flagę (łańcuch w porządku inkluzji komórek). W szczególności barycentryczny podział kompleksu komórek na rozmaitości 2 powoduje triangulację rozmaitości Whitneya.

Złożony porządek częściowo uporządkowanego zbioru składa się z łańcuchów ( całkowicie uporządkowanych podzbiorów) częściowego porządku. Jeśli każda para jakiegoś podzbioru sama jest uporządkowana, to cały podzbiór jest łańcuchem, więc kompleks porządku spełnia warunek no-Δ. Można to interpretować jako zespół kliki wykresu porównywalności rzędu częściowego.

Dopasowany kompleks grafu składa się z zestawów krawędzi, z których żadne dwie nie mają wspólnego punktu końcowego; ponownie ta rodzina zbiorów spełnia warunek no-Δ. Można go postrzegać jako zespół kliki wykresu dopełniacza wykresu liniowego danego wykresu. Kiedy zespół dopasowania jest określany bez żadnego konkretnego grafu jako kontekstu, oznacza to kompleks dopasowania pełnego grafu . Dopasowany kompleks pełnego dwudzielnego grafu K _{m , n} jest znany jako zespół szachownicy. Jest to wykres kliki wykresu dopełnienia grafu wieży , a każdy z jego uproszczeń przedstawia rozmieszczenie wież na szachownicy m × n w taki sposób, że żadne dwie wieże nie atakują się nawzajem. Gdy m = n ± 1, zespół szachownicy tworzy pseudorozmaitość .

Vietorisa -Ripsa zbioru punktów w przestrzeni metrycznej jest szczególnym przypadkiem kompleksu kliki, utworzonego z wykresu dysków jednostkowych punktów; jednakże każdy kompleks kliki X(G) może być interpretowany jako kompleks Vietorisa-Ripsa metryki najkrótszej ścieżki na podstawowym wykresie G.

Hodkinson i Otto (2003) opisują zastosowanie konforemnych hipergrafów w logice struktur relacyjnych. W tym kontekście wykres Gaifmana struktury relacyjnej jest tym samym, co podstawowy wykres hipergrafu reprezentującego strukturę, a struktura jest strzeżona , jeśli odpowiada konforemnemu hipergrafowi.

Gromov wykazał, że sześcienny kompleks (to znaczy rodzina hipersześcianów przecinających się twarzą w twarz) tworzy przestrzeń CAT (0) wtedy i tylko wtedy, gdy kompleks jest po prostu połączony, a połączenie każdego wierzchołka tworzy kompleks flagowy. Sześcienny zespół spełniający te warunki nazywany jest czasem sześcianem lub przestrzenią ze ścianami .

Grupy homologiczne

Meszulam dowodzi następującego twierdzenia o homologii kompleksu kliki. ${\ Displaystyle l \ geq 1, t \ geq 0} ,$ załóżmy , że wykres G spełnia właściwość zwaną , co oznacza, że ${\ Displaystyle P (l, t)}$ :

$wierzchołków$ zestaw w G ma wspólnego sąsiada;
Istnieje zbiór A wierzchołków, który zawiera wspólnego sąsiada dla każdego zestawu $l {\ displaystyle l}$ , a ponadto indukowany wykres G [ ZA ] nie zawiera, jako indukowanego podgrafu, kopii 1 -szkielet t - wymiarowej oktaedrycznej sfery .

Wtedy j -ta zredukowana homologia kompleksu kliki X ( sol ) jest trywialna dla dowolnego j między 0 a ${\ Displaystyle \ max (lt, \ lfloor {l} /{2}\rfloor )-1}$ .

Zobacz też

Graf simplex , rodzaj wykresu mającego jeden węzeł dla każdej kliki grafu bazowego
Matroid partycji , rodzaj matroidu , którego przecięcia z matroidami mogą tworzyć kompleksy kliki

Notatki

Bandelt, H.-J.; Chepoi, V. (2008), „Teoria grafów metrycznych i geometria: ankieta”, w: Goodman, JE ; Pach, J .; Pollack, R. (red.), Surveys on Discrete and Computational Geometry: dwadzieścia lat później (PDF) , Współczesna matematyka, tom. 453, Providence, RI: AMS, s. 49–86 .
Berge, C. (1989), Hipergrafy: Kombinatoryka zbiorów skończonych , Holandia Północna, ISBN 0-444-87489-5 .
Chatterji, I .; Niblo, G. (2005), „Od ścian do kompleksów kostek 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), „Niedodatnie grupy krzywizny i odbicia”, w: Daverman, RJ ; Sher, RB (red.), Handbook of Geometric Topology , Elsevier, s. 373–422 .
Dong, X.; Wachs, ML (2002), „Kombinatoryczny Laplacian kompleksu dopasowującego” , Electronic Journal of Combinatorics , 9 : R17, doi : 10.37236/1634 .
Hartsfeld, N.; Ringel, Gerhard (1991), „Czyste triangulacje”, Combinatorica , 11 (2): 145–155, doi : 10.1007/BF01206358 , S2CID 28144260 .
Hodkinson, I.; Otto, M. (2003), „Skończone konforemne okładki hipergrafów i kliki Gaifmana w skończonych strukturach”, 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), „Triangulacje Whitneya, lokalne wykresy obwodu i iterowane kliki” , Discrete Mathematics , 258 (1–3): 123–135, doi : 10.1016 / S0012-365X (02) 00266-2 .
Malnič, A.; Mohar, B. (1992), „Generowanie lokalnie cyklicznych triangulacji powierzchni”, Journal of Combinatorial Theory, Series B , 56 (2): 147–164, doi : 10.1016/0095-8956 (92) 90015-P .