Clique complex

“Whitney complex” redirects here. For the Mississippi sports facility, see Davey Whitney Complex.

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.

Clique complex

The clique complex X(G) of an undirected graph G is an abstract simplicial complex, 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.^[1]

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.^[2]

Independence complex

The independence complex I(G) of a graph G is formed in the same way as the clique complex from the independent sets of G. It is the clique complex of the complement graph 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.^[3]

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.^[4] 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).^[3] 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.^[3]

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,^[5] 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.

Hodkinson & Otto (2003) 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.^[1][6]

See also

• Simplex graph, a graph having one node for every clique of the underlying graph

Notes

1. ^ ^{a b} Bandelt & Chepoi (2008).
2. ^ Hartsfeld & Ringel (1981); Larrión, Neumann-Lara & Pizaña (2002); Malnič & Mohar (1992).
3. ^ ^{a b c} Davis (2002).
4. ^ Berge (1989); Hodkinson & Otto (2003).
5. ^ Dong & Wachs (2002).
6. ^ Chatterji & Niblo (2005).

References

• Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R., Surveys on Discrete and Computational Geometry: Twenty Years Later, Contemp. Math., 453, Providence, RI: AMS, pp. 49–86 .

• Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0444874895 .

• Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669 .

• Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B., Handbook of Geometric Topology, Elsevier, pp. 373–422 .

• Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics 9: R17, http://www.combinatorics.org/Volume_9/Abstracts/v9i1r17.html .

• Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica 11: 145–155, doi:10.1007/BF01206358 .

• Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic 9 (3): 387–405, doi:10.2178/bsl/1058448678 .

• Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics 258: 123–135, doi:10.1016/S0012-365X(02)00266-2, http://xamanek.izt.uam.mx/map/papers/cuello10_DM.ps .

• Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B 56 (2): 147–164, doi:10.1016/0095-8956(92)90015- .