Abstract simplicial complex: Difference between revisions

Revision as of 14:07, 20 October 2023

Latest revision as of 04:56, 21 June 2025

(8 intermediate revisions by 7 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 91:

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