Clique complex
≈ 4 min read
Names in other languages
- РусскийФлаговый комплекс
- Magyarklikk-komplexus
- EnglishClique complex
- DeutschFahnenkomplex
- slkompleks klik
- 日本語旗複体
- 中文團複形
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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.
Independence complex
The independence complex of an undirected graph is an abstract simplicial complex formed by the sets of vertices in the independent sets of . The clique complex of is equivalent to the independence complex of the complement graph of .
Conformal hypergraph
The primal graph G(H) of a hypergraph is the graph on the same vertex set that has as its edges the pairs of vertices appearing together in the same hyperedge. 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. If the hypergraph is required to be downward-closed (so it contains all hyperedges that are contained in some hyperedge) then the hypergraph is conformal precisely when it is a flag complex. This relates the language of hypergraphs to the language of simplicial complexes.
Examples and applications
The barycentric subdivision of any cell complex C is a flag complex having one vertex per cell of C. A collection of vertices of the barycentric subdivision form a simplex if and only if the corresponding collection of cells of C form a flag (a chain in the inclusion ordering of the cells). In particular, the barycentric subdivision of a cell complex on a 2-manifold gives rise to a Whitney triangulation of the manifold. The order complex of a partially ordered set consists of the chains (totally ordered subsets) of the partial order. If every pair of some subset is itself ordered, then the whole subset is a chain, so the order complex satisfies the no-Δ condition. It may be interpreted as the clique complex of the comparability graph of the partial order. The matching complex of a graph consists of the sets of edges no two of which share an endpoint; again, this family of sets satisfies the no-Δ condition. It may be viewed as the clique complex of the complement graph of the line graph of the given graph. When the matching complex is referred to without any particular graph as context, it means the matching complex of a complete graph. The matching complex of a complete bipartite graph K m,n is known as a chessboard complex. It is the clique graph of the complement graph of a rook's graph, and each of its simplices represents a placement of rooks on an m × n chess board such that no two of the rooks attack each other. When m = n ± 1, the chessboard complex forms a pseudo-manifold. 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. describe an application of conformal hypergraphs in the logics of relational structures. In that context, the Gaifman graph of a relational structure is the same as the underlying graph of the hypergraph representing the structure, and a structure is guarded if it corresponds to a conformal hypergraph. Gromov showed that a cubical complex (that is, a family of hypercubes intersecting face-to-face) forms a CAT(0) space if and only if the complex is simply connected and the link of every vertex forms a flag complex. A cubical complex meeting these conditions is sometimes called a cubing or a space with walls.
See also
Simplex graph, a kind of graph having one node for every clique of the underlying graph Partition matroid, a kind of matroid whose matroid intersections may form clique complexes
Notes
References
. . . . . . . . .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1369038824 under CC BY-SA 4.0; modifications have been made.