Clique complex
Encyclopedia
Clique complexes, flag 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.
, 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 it be closed under subsets. The 1-skeleton
of X(G) (also known as the underlying graph of the complex) is an undirected graph that 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; the Whitney complex of G is then an equivalent cell complex to the embedding, and 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
; that is, the neighbors of each vertex should form a cycle.
s of G. It is the clique complex of the complement graph
of G.
Any flag complex is the clique complex of its 1-skeleton. Thus, flag complexes and clique complexes are essentially the same thing. However, in many cases it may be 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.
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.
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
Km,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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
objects in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
and geometric topology
Geometric topology
In mathematics, geometric topology is the study of manifolds and maps between them, particularly embeddings of one manifold into another.- Topics :...
that each describe the cliques
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
(complete subgraphs) of an undirected graph.
Clique complex
The clique complex X(G) of an undirected graph G is an abstract simplicial complexAbstract simplicial complex
In mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of 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 it be closed under subsets. The 1-skeleton
N-skeleton
In mathematics, particularly in algebraic topology, the n-skeleton of a topological space X presented as a simplicial complex refers to the subspace Xn that is the union of the simplices of X of dimensions m ≤ n...
of X(G) (also known as the underlying graph of the complex) is an undirected graph that is isomorphic to G.
Clique complexes are also known as Whitney complexes. A Whitney triangulation
Triangulation (topology)
In mathematics, topology generalizes the notion of triangulation in a natural way as follows:A triangulation of a topological space X is a simplicial complex K, homeomorphic to X, together with a homeomorphism h:K\to X....
or clean triangulation of a two-dimensional manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
is an embedding
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
of a graph G onto the manifold in such a way that every face is a triangle and every triangle is a face; the Whitney complex of G is then an equivalent cell complex to the embedding, and is homeomorphic
Homeomorphism
In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...
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
Neighbourhood (graph theory)
In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a...
; that is, the neighbors of each vertex should form a cycle.
Independence complex
The independence complex I(G) of a graph G is formed in the same way as the clique complex from the independent setIndependent set
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
s of G. It is the clique complex of the complement graph
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of G.
Flag complex
In an abstract simplicial complex, a set S of vertices that is not itself part of the complex, but such that each pair of vertices in S belongs to some simplex in the complex, is called an empty simplex. Mikhail Gromov defined the no-Δ condition to be the condition that a complex have no empty simplices. A flag complex is an abstract simplicial complex that has no empty simplices; that is, it is a complex satisfying Gromov's no-Δ condition.Any flag complex is the clique complex of its 1-skeleton. Thus, flag complexes and clique complexes are essentially the same thing. However, in many cases it may be 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.
Conformal hypergraph
The primal graph G(H) of a hypergraphHypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
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 subdivisionBarycentric subdivision
In geometry, the barycentric subdivision is a standard way of dividing an arbitrary convex polygon into triangles, a convex polyhedron into tetrahedra, or, in general, a convex polytope into simplices with the same dimension, by connecting the barycenters of their faces in a specific way.The name...
of any cell complex
CW complex
In topology, a CW complex is a type of topological space introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still retains a combinatorial naturethat allows for...
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
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...
consists of the chains (totally ordered
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
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
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
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
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of the line graph
Line graph
In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
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
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
. The matching complex of a complete bipartite graph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
Km,n is known as a chessboard complex. It is the clique graph of the complement graph of a rook's graph
Rook's graph
In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move...
, 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
Vietoris–Rips complex
In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is an abstract simplicial complex that can be defined from any metric space M and distance δ by forming a simplex for every finite set of points that has diameter at most δ...
of a set of points in a metric space is a special case of a clique complex, formed from the unit disk graph
Unit disk graph
In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross each other....
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
Constraint graph
In constraint satisfaction research of artificial intelligence and operations research, constraint graphs and hypergraphs are used to represent relations among constraints in a constraint satisfaction problem.-Constraint hypergraph:...
of a relational structure is the same as the underlying graph of the hypergraph representing the structure, and a structure is guarded
Guarded logic
Guarded logic is a choice set of dynamic logic involved in choices, where outcomes are limited.A simple example of guarded logic is as follows: if X is true, then Y, else Z can be expressed in dynamic logic as ∪. This shows a guarded logical choice: if X holds, then X?;Y is equal to Y, and ~X?;Z is...
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
CAT(k) space
In mathematics, a CAT space is a specific type of metric space. Intuitively, triangles in a CAT space are "slimmer" than corresponding "model triangles" in a standard space of constant curvature k. In a CAT space, the curvature is bounded from above by k...
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.