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. 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.
Clique complexes are also known as Whitney complexes. A Whitney triangulation or clean triangulation of a two-dimensional manifold is an embedding of a graph G onto the manifold in such a way that every face is a triangle and every triangle is a face. If a graph G has a Whitney triangulation, it must form a cell complex that is isomorphic to the Whitney complex of G. In this case, the complex (viewed as a topological space) is homeomorphic to the underlying manifold. 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.
Read more about this topic: Clique Complex
Famous quotes containing the words clique and/or complex:
“Every clique is a refuge for incompetence. It fosters corruption and disloyalty, it begets cowardice, and consequently is a burden upon and a drawback to the progress of the country. Its instincts and actions are those of the pack.”
—Madame Chiang Kai-Shek (b. 1898)
“All propaganda or popularization involves a putting of the complex into the simple, but such a move is instantly deconstructive. For if the complex can be put into the simple, then it cannot be as complex as it seemed in the first place; and if the simple can be an adequate medium of such complexity, then it cannot after all be as simple as all that.”
—Terry Eagleton (b. 1943)