TOPICS
Search

Hypergraph


A hypergraph is an ordered pair H=(V,E) consisting of a set V of vertices and a family E of subsets of V called hyperedges. For a finite simple hypergraph, E is a subset of the power set P(V). Conventions differ on whether the empty hyperedge, singleton hyperedges, or repeated hyperedges are allowed.

The size |e| of a hyperedge e is its cardinal number. A hypergraph is k-uniform if every hyperedge has size k, 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 v is the number of hyperedges containing v.

For vertices v_1,...,v_n and hyperedges e_1,...,e_m, the incidence matrix M of a hypergraph is defined by

 M_(ij)={1   if v_i in e_j; 0   otherwise.
(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

 A=MM^T-diag(MM^T).
(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 m 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).


See also

Average Sensitivity, Bipartite Graph, Codegree Turan Density, Erdős-Sós Bipartite-Link Conjecture, Friedgut-Kalai Sharp-Threshold Conjecture, Generalized Hypergraph 4-Cycle, Graph, Hyperedge, Hypergraph Shadow, Hypergraph Stochastic Block Model, Hypergraph Tutte Polynomial, Incidence Matrix, Multigraph, Positional Game, Pseudograph, Tight Tree

Explore with Wolfram|Alpha

References

Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Berge, C. Hypergraphs: The Theory of Finite Sets. Amsterdam, Netherlands: North-Holland, 1989.Delcourt, M.; Henderson, C.; Lesgourgues, T.; and Postle, L. "Hypergraph Hajnal-Szemerédi." 19 Nov 2026. https://arxiv.org/abs/2611.26513v1.Kuang, P.; Sun, S.; Wang, Y.; and Zeng, J. "Subhypergraph Counts and Proofs of Two Conjectures of Alon." 17 Nov 2026. https://arxiv.org/abs/2606.18321v2.Qiao, C.; Lu, Z.; and Song, H. "The Proof of the Alon-Kim Conjecture." 10 Nov 2026. https://arxiv.org/abs/2611.13698v1.

Referenced on Wolfram|Alpha

Hypergraph

Cite this as:

Weisstein, Eric W. "Hypergraph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Hypergraph.html

Subject classifications