Abstract simplicial complex: Difference between revisions

Revision as of 09:27, 10 July 2023

Latest revision as of 04:56, 21 June 2025

(9 intermediate revisions by 8 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 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 ==