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 cardinal number.
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 vertex-part-by-hyperedge-part block of the adjacency 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.
