Clique complex

The clique complex X(G) of an undirected graph G is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the cliques of G. Any subset of a clique is itself a clique, so this family of sets meets the requirement of an abstract simplicial complex that every subset of a set in the family should also be in the family.

However, in many cases it is convenient to define a flag complex directly from some data other than a graph, rather than indirectly as the clique complex of a graph derived from that data.

A graph G has a 2-manifold clique complex, and can be embedded as a Whitney triangulation, if and only if G is locally cyclic; this means that, for every vertex v in the graph, the induced subgraph formed by the neighbors of v forms a single cycle.

A hypergraph is said to be conformal if every maximal clique of its primal graph is a hyperedge, or equivalently, if every clique of its primal graph is contained in some hyperedge.

[2] In particular, the barycentric subdivision of a cell complex on a 2-manifold gives rise to a Whitney triangulation of the manifold.

It may be interpreted as the clique complex of the comparability graph of the partial order.

The Vietoris–Rips complex of a set of points in a metric space is a special case of a clique complex, formed from the unit disk graph of the points; however, every clique complex X(G) may be interpreted as the Vietoris–Rips complex of the shortest path metric on the underlying graph G. Hodkinson & Otto (2003) describe an application of conformal hypergraphs in the logics of relational structures.

A cubical complex meeting these conditions is sometimes called a cubing or a space with walls.

[1][6] Meshulam[7] proves the following theorem on the homology of the clique complex.

, which means that: Then the j-th reduced homology of the clique complex X(G) is trivial for any j between 0 and

The clique complex of a graph. Cliques of size one are shown as small red disks; cliques of size two are shown as black line segments; cliques of size three are shown as light blue triangles; and cliques of size four are shown as dark blue tetrahedra.