# Hypergraph

See: Graph, Hyperedge, Hypercube.

## References

### 2011

• (Wikipedia, 2011) ⇒ http://en.wikipedia.org/wiki/Hypergraph
• QUOTE: In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph $\displaystyle{ H }$ is a pair $\displaystyle{ H = (X,E) }$ where $\displaystyle{ X }$ is a set of elements, called nodes or vertices, and $\displaystyle{ E }$ is a set of non-empty subsets of $\displaystyle{ X }$ called hyperedges or links. Therefore, $\displaystyle{ E }$ is a subset of $\displaystyle{ \mathcal{P}(X) \setminus\{\emptyset\} }$, where $\displaystyle{ \mathcal{P}(X) }$ is the power set of $\displaystyle{ X }$.

While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often useful to study hypergraphs where all hyperedges have the same cardinality: a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. (In other words, it is a collection of sets of size k.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of triples, and so on.

A hypergraph is also called a set system or a family of sets drawn from the universal set X. Hypergraphs can be viewed as incidence structures and vice versa. In particular, there is a Levi graph corresponding to every hypergraph, and vice versa. In computational geometry, a hypergraph may be called a range space and the hyperedges are called ranges.[1]

In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory.

Special cases of hypergraphs include the clutter, where no edge appears as a subset of another edge; and the abstract simplicial complex, which contains all subsets of every edge.

The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.

### 2009

1. D. Haussler and E. Welzl. ε-nets and simplex range queries. Discrete Compututational Geometry, 2:127–151, 1987.