Content deleted Content added
Erel Segal (talk | contribs) |
|||
| (12 intermediate revisions by 10 users not shown) | |||
Line 31:
Note that the link of the empty set is {{math|Δ}} itself.
=== Simplicial maps ===
Given two abstract simplicial complexes, {{math|Δ}} and {{math|Γ}}, a '''simplicial map''' is a [[Function (mathematics)|function]] {{math| ''f'' }} that maps the vertices of {{math|Δ}} to the vertices of {{math|Γ}} and that has the property that for any face {{mvar|X}} of {{math|Δ}}, the [[Image (mathematics)|image]] {{math| ''f'' (''X'')}} is a face of {{math|Γ}}. There is a [[Category (mathematics)|category]] '''SCpx''' with abstract simplicial complexes as objects and simplicial maps as [[morphism]]s. This is equivalent to a suitable category defined using non-abstract [[simplicial complexes]].▼
{{Main|Simplicial map}}
▲Given two abstract simplicial complexes, {{math|Δ}} and {{math|Γ}}, a '''[[simplicial map]]''' is a [[Function (mathematics)|function]] {{math| ''f'' }} that maps the vertices of {{math|Δ}} to the vertices of {{math|Γ}} and that has the property that for any face {{mvar|X}} of {{math|Δ}}, the [[Image (mathematics)|image]] {{math| ''f'' (''X'')}} is a face of {{math|Γ}}. There is a [[Category (mathematics)|category]] '''SCpx''' with abstract simplicial complexes as objects and simplicial maps as [[morphism]]s. This is equivalent to a suitable category defined using non-abstract [[simplicial complexes]].
Moreover, the categorical point of view allows us to tighten the relation between the underlying set ''S'' of an abstract simplicial complex {{math|Δ}} and the vertex set {{math|''V''(Δ) ⊆ ''S''}} of {{math|Δ}}: for the purposes of defining a category of abstract simplicial complexes, the elements of ''S'' not lying in {{math|''V''(Δ)}} are irrelevant. More precisely, '''SCpx''' is equivalent to the category where:
Line 43 ⟶ 45:
Every [[geometric simplicial complex]] (GSC) determines an ASC:''<ref name=":0">{{Cite Matousek 2007}}, Section 4.3</ref>''{{Rp|page=14|___location=}} the vertices of the ASC are the vertices of the GSC, and the faces of the ASC are the vertex-sets of the faces of the GSC. For example, consider a GSC with 4 vertices {1,2,3,4}, where the maximal faces are the triangle between {1,2,3} and the lines between {2,4} and {3,4}. Then, the corresponding ASC contains the sets {1,2,3}, {2,4}, {3,4}, and all their subsets. We say that the GSC is the '''geometric realization''' of the ASC.
Every ASC has a geometric realization. This is easy to see for a finite ASC.''<ref name=":0" />''{{Rp|page=14|___location=}} Let <math>N := |V(K)|</math>. Identify the vertices in <math>V(K)</math> with the vertices of an (''N
If ''K'' is the standard combinatorial ''n''-simplex, then <math>|K|</math> can be naturally identified with {{math|Δ<sup>''n''</sup>}}.
Line 67 ⟶ 69:
1. Let ''V'' be a finite set of [[cardinality]] {{math|''n'' + 1}}. The '''combinatorial ''n''-simplex''' with vertex-set ''V'' is an ASC whose faces are all nonempty subsets of ''V'' (i.e., it is the [[power set]] of ''V''). If {{math|''V'' {{=}} ''S'' {{=}} {0, 1, ..., ''n''},}} then this ASC is called the '''standard combinatorial ''n''-simplex'''.
2. Let ''G'' be an undirected graph. The '''[[clique complex]]''' '''of ''G''''' is an ASC whose faces are all [[Clique (graph theory)|cliques]] (complete subgraphs) of ''G''. The '''independence complex of ''G''''' is an ASC whose faces are all [[Independent set (graph theory)|independent sets]] of ''G'' (it is the clique complex of the [[complement graph]] of G). Clique complexes are the prototypical example of [[flag complex]]es. A '''flag complex''' is a complex ''K'' with the property that every set,
3. Let ''H'' be a [[hypergraph]]. A [[Matching in hypergraphs|matching]] in ''H'' is a set of edges of ''H'', in which every two edges are [[Disjoint sets|disjoint]]. The '''matching complex of ''H''''' is an ASC whose faces are all [[Matching in hypergraphs|matchings]] in ''H''. It is the [[independence complex]] of the [[Line graph of a hypergraph|line graph]] of ''H''.
Line 80 ⟶ 82:
==Enumeration==
The number of abstract simplicial complexes on up to ''n'' labeled elements (that is on a set ''S'' of size ''n'') is one less than the ''n''th [[Dedekind number]]. These numbers grow very rapidly, and are known only for {{math|''n'' ≤
:1, 2, 5, 19, 167, 7580, 7828353, 2414682040997, 56130437228687557907787, 286386577668298411128469151667598498812365 {{OEIS|id=A014466}}. This corresponds to the number of non-empty [[antichain]]s of subsets of an {{math| ''n''}} set.
The number of abstract simplicial complexes whose vertices are exactly ''n'' labeled elements is given by the sequence "1, 2, 9, 114, 6894, 7785062, 2414627396434, 56130437209370320359966, 286386577668298410623295216696338374471993" {{OEIS|id=A006126}}, starting at ''n'' = 1. This corresponds to the number of antichain covers of a labeled ''n''-set; there is a clear bijection between antichain covers of an ''n''-set and simplicial complexes on ''n'' elements described in terms of their maximal faces.
The number of abstract simplicial complexes on exactly ''n'' unlabeled elements is given by the sequence "1, 2, 5, 20, 180, 16143, 489996795, 1392195548399980210" {{OEIS|id=A006602}}, starting at ''n'' = 1.
== Computational problems ==
{{Main|Simplicial complex recognition problem}}
The [[simplicial complex recognition problem]] is: given a finite ASC, decide whether its geometric realization is homeomorphic to a given geometric object. This problem is [[Undecidable problem|undecidable]] for any ''d''-dimensional manifolds for ''d'' ≥ 5.<ref>{{citation |last=Stillwell |first=John |title=Classical Topology and Combinatorial Group Theory |url=https://books.google.com/books?id=265lbM42REMC&pg=PA247 |volume=72 |page=247 |year=1993 |series=Graduate Texts in Mathematics |publisher=Springer |isbn=9780387979700 |authorlink=John Stillwell}}.</ref>
== Relation to other concepts ==
| |||