Clique complex

Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques (complete subgraphs) of an undirected graph. 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. The clique complex can also be viewed as a topological space in which each clique of k vertices is represented by a simplex of dimension k – 1. The 1-skeleton of X(G) (also known as the underlying graph of the complex) is an undirected graph with a vertex for every 1-element set in the family and an edge for every 2-element set in the family; it is isomorphic to G. Every clique complex is an abstract simplicial complex, but the opposite is not true. For example, consider the abstract simplicial complex over {1,2,3,4} with maximal sets {1,2,3}, {2,3,4}, {4,1}. If it were the X(G) of some graph G, then G had to have the edges {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {4,1}, so X(G) should also contain the clique {1,2,3,4}. The independence complex I(G) of an undirected graph G is an abstract simplicial complex formed by the sets of vertices in the independent sets of G. The clique complex of G is equivalent to the independence complex of the complement graph of G. A flag complex is an abstract simplicial complex with an additional property called "2-determined": for every subset S of vertices, if every pair of vertices in S is in the complex, then S itself is in the complex too. Every clique complex is a flag complex: if every pair of vertices in S is a clique of size 2, then there is an edge between them, so S is a clique.