Abstract simplicial complex: Difference between revisions

Revision as of 09:23, 10 July 2023

Latest revision as of 04:56, 21 June 2025

(10 intermediate revisions by 9 users not shown)

Line 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-1'' − 1)-dimensional simplex in <math>\R^N</math>. Construct the GSC {[[convex hull|conv]](F): F is a face in K}. Clearly, the ASC associated with this GSC is identical to ''K'', so we have indeed constructed a geometric realization of ''K.'' In fact, an ASC can be realized using much fewer dimensions. If an ASC is ''d''-dimensional (that is, the maximum cardinality of a simplex in it is ''d''+1), then it has a geometric realization in <math>\R^{2d+1}</math>, but might not have a geometric realization in <math>\R^{2d}</math> ''<ref name=":0" />{{Rp|page=16|___location=}}'' The special case ''d''=1 corresponds to the well-known fact, that any [[Graph (discrete mathematics)|graph]] can be plotted in <math>\R^{3}</math> where the edges are straight lines that do not intersect each other except in common vertices, but not any [[Graph (discrete mathematics)|graph]] can be plotted in <math>\R^{2}</math> in this way.

If ''K'' is the standard combinatorial ''n''-simplex, then <math>|K|</math> can be naturally identified with {{math|Δ^''n''}}.

Line 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, ofall elementsof thatwhose pairwise2-element belongsubsets toare faces of ''K'', is itself a face of ''K''.

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 87:

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 ==