Hypergraph

Informally a hypergraph is a graph whose edges, instead of each connecting just two vertices, connect more than two vertices. For any set X, let X^[m] be the set of subsets of X whose elements have precisely m members. Then an m-hypergraph consists of a set X of vertices and a subset E of X^[m]. A hypergraph is then defined to be a pair of sets (X,E) such that the pair constitute an m-hypergraph for some m. Commonly X is finite but this need not always be the case.

It is also possible to define a hypergraph in a more general way as a pair of sets (X,E) where E is some arbitrary subset of the power set of X. In this case the number of the vertices in each edge is not constant from one edge to the next. This definition is less commonly encountered.

Many theorems involving graphs also hold for hypergraphs. See Ramsey's theorem for a typical example. Some methods of studying the symmetries of graphs extend to hypergraphs too. For instance, a hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that one edge is mapped to another edge. An hypergraph isomorphism is a homomorphism that is invertible. A hypergraph automorphism is an isomorphism from a vertex set into itself. The set of automorphisms of a hypergraph H (=(X,E)) is a group under composition. This group is called the automorphism group of the hypergraph, written Aut(H). The collection of hypergraphs is clearly a category with hypergraph homomorphisms as morphisms.

A property of graphs that encourages their study, is that it is easy to draw a representation of them on a piece of paper. This is not so for hypergraphs and so their study tends to be conducted using the nomenclature of set theory rather than the more pictoral descriptions (for instance 'trees','forests' and 'cycles') of graph theory.