Abstract simplicial complex: Difference between revisions

Revision as of 22:39, 19 January 2025

Latest revision as of 04:56, 21 June 2025

(One intermediate revision by one other user 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 67:

==Examples==

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, all of whose 2-element subsets are faces of ''K'', is itself a face of ''K''.