A hypergraph is an ordered pair 
consisting of a set 
of vertices and a family 
of subsets of 
called hyperedges. For a finite
simple hypergraph, 
is a subset of the power set 
. Conventions differ on whether the empty hyperedge, singleton
hyperedges, or repeated hyperedges are allowed.
The size 
of a hyperedge 
is its cardinality. A hypergraph is 
-uniform if every hyperedge has size 
, and it is nonuniform if hyperedges of different sizes occur.
Thus an ordinary simple graph is a 2-uniform hypergraph.
The degree of a vertex 
is the number of hyperedges containing 
.
For vertices 
and hyperedges 
,
the incidence matrix 
of a hypergraph is defined by
 |
(1)
|
It is also the incidence matrix of the bipartite graph having the vertices in one part and the hyperedges in the other. A vertex-vertex matrix whose off-diagonal entries count common hyperedges is
 |
(2)
|
Such a matrix representation generally loses information about which collections of more than two vertices belong to the same hyperedge.
