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.
A hypergraph edge coloring assigns different colors to intersecting hyperedges. It extends edge coloring from ordinary graphs to hypergraphs.
Hypergraph independent sets contain no whole hyperedge. Clique-factor and equitable-coloring extensions of the Hajnal-Szemerédi theorem give sufficient codegree conditions for uniform hypergraphs (Delcourt et al. 2026).
For a fixed finite simple uniform hypergraph without isolated vertices, the maximum number of copies in a host with hyperedges has a full leading
asymptotic term. Its exponent is the fractional
edge cover number; this extends the extremal subgraph
count problem from graphs to uniform hypergraphs (Kuang et al. 2026).