Abstraktní zjednodušený komplex - Abstract simplicial complex - Wikipedia

Geometrické znázornění abstraktního zjednodušeného komplexu, které není platné zjednodušený komplex.

v kombinatorika, an abstraktní zjednodušený komplex (ASC) je a rodina sad která je uzavřena podmnožiny tj. každá podskupina sady v rodině je také v rodině. Jedná se o čistě kombinatorický popis geometrického pojmu a zjednodušený komplex.^[1] Například v dvourozměrném komplexu jsou sady v rodině trojúhelníky (sady velikosti 3), jejich hrany (sady velikosti 2) a jejich vrcholy (sady velikosti 1).

V kontextu matroidy a greedoidy, nazývají se také abstraktní zjednodušené komplexy systémy nezávislosti.^[2]

Abstraktní simplex lze studovat algebraicky vytvořením jeho Stanley – Reisnerův prsten; Tím se vytvoří silný vztah mezi kombinatorika a komutativní algebra.

Definice

Sbírka $Δ$ neprázdných konečných podmnožin a soubor S se nazývá množinová rodina.

Set-rodina $Δ$ se nazývá abstraktní zjednodušený komplex pokud pro každou sadu $X$ v $Δ$ a každá neprázdná podmnožina $Y \subseteq X$ , sada $Y$ také patří $Δ$ .

Konečné množiny, které patří $Δ$ se nazývají tváře komplexu a tvář $Y$ údajně patří k jiné tváři $X$ -li $Y \subseteq X$ , takže definici abstraktního zjednodušeného komplexu lze přeformulovat tak, že každá tvář je tváří komplexu $Δ$ je sama o sobě tváří $Δ$ . The sada vrcholů z $Δ$ je definován jako $PROTI (Δ) = \cupΔ$ , spojení všech tváří $Δ$ . Prvky sady vrcholů se nazývají vrcholy komplexu. Pro každý vrchol proti z $Δ$ , sada {proti} je tváří komplexu a každá tvář komplexu je konečnou podmnožinou množiny vrcholů.

Maximální tváře $Δ$ (tj. tváře, které nejsou podmnožinami jiných tváří), jsou volány fazety komplexu. The rozměr obličeje $X$ v $Δ$ je definován jako $ztlumit(X) = | X | - 1$ : plochy skládající se z jednoho prvku jsou nulové, plochy skládající se ze dvou prvků jsou jednorozměrné atd rozměr komplexu $dim (Δ)$ je definována jako největší rozměr kterékoli z jeho ploch nebo nekonečno, pokud na dimenzi ploch není žádná konečná vazba.

Komplex $Δ$ se říká, že je konečný pokud má konečně mnoho tváří, nebo ekvivalentně, pokud je jeho sada vrcholů konečná. Taky, $Δ$ se říká, že je čistý pokud je konečně-dimenzionální (ale ne nutně konečný) a každý aspekt má stejnou dimenzi. Jinými slovy, $Δ$ je čistý, pokud $dim (Δ)$ je konečný a každý obličej je obsažen v aspektu dimenze $dim (Δ)$ .

Jednorozměrné abstraktní zjednodušené komplexy jsou matematicky ekvivalentní jednoduchý neorientované grafy: vrcholovou sadu komplexu lze považovat za vrcholovou sadu grafu a dvouprvkové fazety komplexu odpovídají neorientovaným okrajům grafu. V tomto pohledu jedno-elementové aspekty komplexu odpovídají izolovaným vrcholům, které nemají žádné hrany dopadu.

A dílčí komplex z $Δ$ je abstraktní zjednodušený komplex L tak, že každá tvář L patří $Δ$ ; to je $L \subseteq Δ$ a L je abstraktní zjednodušený komplex. Subkomplex, který se skládá ze všech podmnožin jedné tváře $Δ$ se často nazývá a simplexní z $Δ$ . (Někteří autoři však používají výraz „simplex“ pro obličej nebo spíše nejednoznačně pro obličej i subkomplex spojený s obličejem, analogicky s neabstrahujícími (geometrickými) zjednodušený komplex terminologie. Abychom se vyhnuli nejednoznačnosti, nepoužíváme v tomto článku výraz „simplex“ pro tvář v kontextu abstraktních komplexů).

The d-kostra z $Δ$ je dílčí komplex $Δ$ skládající se ze všech tváří $Δ$ které mají maximálně rozměr d. Zejména 1-kostra se nazývá podkladový graf z $Δ$ . Kostra 0 $Δ$ lze identifikovat pomocí jeho sady vrcholů, i když formálně to není úplně to samé (sada vrcholů je jedinou sadou všech vrcholů, zatímco 0-kostra je rodina jednoprvkových sad).

The odkaz tváře $Y$ v $Δ$ , často označován $Δ / Y$ nebo $lk Δ (Y)$ , je dílčí komplex $Δ$ definován

{ displaystyle Delta / Y: = {X in Delta mid X cap Y = varnothing, , X cup Y in Delta }.}

Odkaz na prázdnou sadu je $Δ$ sám.

Vzhledem ke dvěma abstraktním zjednodušeným komplexům $Δ$ a $Γ$ , a zjednodušená mapa je funkce $F$ který mapuje vrcholy $Δ$ k vrcholům $Γ$ a to má tu vlastnost, že pro jakoukoli tvář $X$ z $Δ$ , obraz $F (X)$ je tváří $Γ$ . Tady je kategorie SCpx s abstraktními zjednodušenými komplexy jako objekty a zjednodušenými mapami jako morfismy. To odpovídá ekvivalentní kategorii definované pomocí neabstrahového zjednodušené komplexy.

Kromě toho nám kategorické hledisko umožňuje zpřísnit vztah mezi podkladovou množinou S abstraktního zjednodušeného komplexu $Δ$ a sada vrcholů $PROTI (Δ) \subseteq S$ z $Δ$ : pro účely definice kategorie abstraktních zjednodušených komplexů jsou prvky S neležet dovnitř $PROTI (Δ)$ jsou irelevantní. Přesněji, SCpx odpovídá kategorii, kde:

objekt je množina S vybavené sbírkou neprázdných konečných podmnožin $Δ$ který obsahuje všechny singletony a takové, že pokud $X$ je v $Δ$ a $Y \subseteq X$ není tedy prázdný $Y$ také patří $Δ$ .
morfismus z $(S, Δ)$ na $(T, Γ)$ je funkce $F : S \to T$ takový, že obraz libovolného prvku $Δ$ je prvek $Γ$ .

Geometrická realizace

Můžeme se spojit s abstraktním zjednodušeným komplexem K. A topologický prostor ${ displaystyle | K |}$ , volal jeho geometrická realizace, který je přepravcem a zjednodušený komplex. Konstrukce probíhá následovně.

Nejprve definujte ${ displaystyle | K |}$ jako podmnožina ${ displaystyle [0,1] ^ {S}}$ skládající se z funkcí ${ displaystyle t dvojtečka S až [0,1]}$ splňující dvě podmínky:

{ displaystyle {s v S: t_ {s}> 0 } v K}

{ displaystyle sum _ {s v S} t_ {s} = 1}

Nyní přemýšlejte o sadě prvků ${ displaystyle [0,1] ^ {S}}$ s konečnou podporou jako přímý limit z ${ displaystyle [0,1] ^ {A}}$ kde A se pohybuje přes konečné podmnožiny Sa dejte tomuto přímému limitu indukovaná topologie. Teď dej ${ displaystyle | K |}$ the topologie podprostoru.

Případně nechte ${ displaystyle { mathcal {K}}}$ označují kategorii, jejíž objekty jsou tvářemi $K.$ a jejichž morfismy jsou inkluze. Dále zvolte a celková objednávka na vrcholovém souboru $K.$ a definovat a funktor F z ${ displaystyle { mathcal {K}}}$ do kategorie topologických prostor následovně. Pro jakoukoli tvář X v K. dimenze n, nechť $F (X) = Δ n$ být standardem n-jednodušší. Pořadí na množině vrcholů pak určuje jedinečný bijekce mezi prvky $X$ a vrcholy $Δ n$ , objednáno obvyklým způsobem $E 0 < E 1 < ... < E n$ . Li $Y \subseteq X$ je tváří dimenze $m < n$ , pak tato bijekce určuje jedinečnost m-rozměrná tvář $Δ n$ . Definovat $F (Y) \to F (X)$ být jedinečný afinní lineární vkládání z $Δ m$ jako ta význačná tvář $Δ n$ , takže mapa na vrcholech zachovává pořadí.

Poté můžeme definovat geometrickou realizaci ${ displaystyle | K |}$ jako colimit funktoru F. Konkrétněji ${ displaystyle | K |}$ je kvocientový prostor z disjunktní unie

{ displaystyle coprod _ {X v K} {F (X)}}

podle vztah ekvivalence který identifikuje bod $y \in F (Y)$ s jeho obrázkem pod mapou $F (Y) \to F (X)$ , pro každé zařazení $Y \subseteq X$ .

Li K. je konečný, pak můžeme popsat ${ displaystyle | K |}$ jednodušeji. Vyberte vložení sady vrcholů K. jako afinně nezávislý podmnožina některých Euklidovský prostor ${ displaystyle mathbb {R} ^ {N}}$ dostatečně vysoké dimenze N. Pak libovolná tvář X v K. lze identifikovat pomocí geometrického simplexu v ${ displaystyle mathbb {R} ^ {N}}$ překlenuta odpovídajícími vloženými vrcholy. Vzít ${ displaystyle | K |}$ být spojením všech takových jednoduchostí.

Li K. je standardní kombinační n- tedy jednoduché ${ displaystyle | K |}$ lze přirozeně identifikovat $Δ n$ .

Příklady

1. Nechte PROTI být konečnou sadou mohutnost $n + 1$ . The kombinační n-jednodušší se sadou vrcholů PROTI je ASC, jehož tváře jsou všechny podmnožiny PROTI (tj. je to napájecí sada z PROTI). Li $PROTI = S = {0, 1, ..., n},$ pak se tento ASC nazývá standardní kombinatorický n-jednodušší.

2. Nechte G být neorientovaným grafem. The klikový komplex z G je ASC, jehož tváře jsou všechny kliky (úplné podgrafy) G. The komplex nezávislosti G je ASC, jehož tváře jsou všechny nezávislé sady z G (je to klikový komplex doplňkový graf G). Clique komplexy jsou prototypovým příkladem vlajkové komplexy. A komplex vlajky je komplex K. s vlastností, které každá sada prvků, které párově patří do tváří K. je sama o sobě tváří K..

3. Nechte H být hypergraf. A vhodný v H je sada okrajů H, ve kterém jsou každé dva okraje disjunktní. The odpovídající komplex H je ASC, jehož tváře jsou všechny párování v H. To je komplex nezávislosti z hranový graf z H.

4. Nechť P být částečně objednaná sada (poset). The objednávat komplex z P je ASC, jehož tváře jsou konečné řetězy v P. Své homologie skupiny a další topologické invarianty obsahují důležité informace o posetu P.

5. Nechť M být metrický prostor a δ skutečné číslo. The Vietoris – Rips komplex je ASC, jehož tváře jsou konečné podmnožiny M s průměrem maximálně δ. Má aplikace v teorie homologie, hyperbolické skupiny, zpracování obrazu, a mobilní ad hoc sítě. Je to další příklad komplexu vlajek.

6. Nechť ${ displaystyle I}$ být bez čtverce monomiální ideál v polynomiální kruh ${ displaystyle S = K [x_ {1}, tečky, x_ {n}]}$ (tj. ideál generovaný produkty podmnožin proměnných). Pak exponentové vektory těchto čtvercových monomiálů z ${ displaystyle S}$ které nejsou v ${ displaystyle I}$ určit abstraktní zjednodušený komplex prostřednictvím mapy ${ displaystyle mathbf {a} v {0,1 } ^ {n} mapsto {i v [n]: a_ {i} = 1 }}$ . Ve skutečnosti existuje bijekce mezi (neprázdnými) abstraktními zjednodušenými komplexy $n$ vrcholy a monomiální ideály bez čtverců $S$ . Li ${ displaystyle I _ { Delta}}$ je ideál bez čtverců odpovídající zjednodušenému komplexu ${ displaystyle Delta}$ pak kvocient ${ displaystyle S / I _ { Delta}}$ je známý jako Stanley – Reisnerův prsten z ${ displaystyle { Delta}}$ .

7. Pro všechny otevřená krytina C topologického prostoru, nervový komplex z C je abstraktní zjednodušený komplex obsahující podskupiny C s neprázdným průsečík.

Výčet

Počet abstraktních zjednodušených komplexů až n označené prvky (tj. na množině S velikosti n) je o jeden menší než nth Dedekindovo číslo. Tato čísla rostou velmi rychle a jsou známa pouze pro $n \leq 8$ ; čísla Dedekind jsou (počínaje n = 0):

1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787 (sekvence A014466 v OEIS ). To odpovídá počtu neprázdných antichains podmnožin an

n

soubor.

Počet abstraktních zjednodušených komplexů, jejichž vrcholy jsou přesně n označené prvky je dáno posloupností „1, 2, 9, 114, 6894, 7785062, 2414627396434, 56130437209370320359966“ (posloupnost A006126 v OEIS ), počínaje n = 1. To odpovídá počtu předřetězcových obalů štítku n-soubor; existuje jasná bijekce mezi antichainovými kryty an n- nastavit a zjednodušit komplexy na n prvky popsané z hlediska jejich maximálních ploch.

Počet abstraktních zjednodušených komplexů přesně n neoznačené prvky jsou dány posloupností „1, 2, 5, 20, 180, 16143“ (posloupnost A006602 v OEIS ), počínaje od n = 1.

Vztah k jiným pojmům

Abstraktní zjednodušený komplex s další vlastností zvanou vlastnost augmentace nebo směnit majetek výnosy a matroid. Následující výraz ukazuje vztahy mezi výrazy:

HYPERGRAPY = SADY RODIN ⊃ NEZÁVISLOST SYSTÉMY = ABSTRAKT-JEDNODUCHÉ KOMPLEXY ⊃ MATROIDY.

Viz také

Reference

^ Lee, John M., Úvod do topologických potrubí, Springer 2011, ISBN 1-4419-7939-5, str. 153
^ Korte, Bernhard; Lovász, László; Schrader, Rainer (1991). Greedoids. Springer-Verlag. p. 9. ISBN 3-540-18190-3.

[Lee-1] Lee, John M., Úvod do topologických potrubí, Springer 2011, ISBN 1-4419-7939-5, str. 153

[2] Korte, Bernhard; Lovász, László; Schrader, Rainer (1991). Greedoids. Springer-Verlag. p. 9. ISBN 3-540-18190-3.

[1]

[2]