# Hypergraph

A hypergraph is a generalization of a graph in which an edge, called a hyperedge, may join any number of vertices rather than exactly two. Formally, a hypergraph is a pair \( (V, \mathcal{E}) \) where \( V \) is a set of vertices and \( \mathcal{E} \) is a family of subsets of \( V \) called edges or hyperedges; the concept is a variant of the familiar notions of a complex, a block design, and a network.<sup>[1](https://encyclopediaofmath.org/wiki/Hypergraph)</sup> Under this definition an ordinary graph is a 2-uniform hypergraph, since its edge set consists only of 2-element subsets of the vertices.<sup>[2](https://blog.rkempe.ca/posts/2024/11/hypergraph-theory-basics/)</sup>

| Key fact | Detail |
|---|---|
| Definition | A pair \( (V, \mathcal{E}) \): a vertex set \( V \) and a family \( \mathcal{E} \) of subsets of \( V \) called edges or hyperedges<sup>[1](https://encyclopediaofmath.org/wiki/Hypergraph)</sup> |
| Relation to graphs | A graph is a 2-uniform hypergraph; hyperedges may contain any number of vertices<sup>[2](https://blog.rkempe.ca/posts/2024/11/hypergraph-theory-basics/)</sup> |
| Matrix form | An \( n \times m \) incidence matrix with rows for vertices and columns for edges, entry 1 when vertex \( v_i \) belongs to edge \( E_j \)<sup>[1](https://encyclopediaofmath.org/wiki/Hypergraph)</sup> |
| Uniformity | The rank \( r(H) \) is the largest hyperedge size and the co-rank \( cr(H) \) the smallest; when \( r(H) = cr(H) = k \) the hypergraph is k-uniform<sup>[3](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)</sup> |
| Duality | The transpose of the incidence matrix defines the dual hypergraph, which exchanges the roles of vertices and edges<sup>[4](https://citeseerx.ist.psu.edu/document?doi=3b78807648f1ee9b5a2010f0f45c0c28ad0e672e&repid=rep1&type=pdf)</sup> |
| Algorithmic cost | Deciding whether a hypergraph has a perfect matching is NP-complete even for 3-graphs, one of Karp's original 21 NP-complete problems<sup>[5](https://people.maths.ox.ac.uk/keevash/papers/icm-survey-arxiv.pdf)</sup> |
| Modern use | Hypergraph neural networks extend graph neural networks to higher-order relationships, with model families including HGCNs, HGATs, HGAEs, HGRNs, and DHGGMs<sup>[6](https://link.springer.com/article/10.1007/s40305-025-00630-y)</sup> |

## Basic definitions

Two vertices of a hypergraph are adjacent if some edge contains both, and a vertex \( v \) is incident to an edge \( E \) when \( v \in E \).<sup>[1](https://encyclopediaofmath.org/wiki/Hypergraph)</sup> The order of a hypergraph is the number of vertices \( |V| = n \) and its size is the number of hyperedges \( |E| = m \). A hyperedge of size 1 is a loop; a hypergraph is regular, or k-regular, when every vertex has the same degree \( k \).<sup>[3](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)</sup>

**Incidence matrix.** A hypergraph \( H \) with \( n \) vertices and \( m \) edges is fully described by its \( n \times m \) incidence matrix \( \|a_{ij}\| \), whose columns correspond to edges and rows to vertices, with

\[ a_{ij} = \begin{cases} 1 & \text{if } v_i \in E_j, \\ 0 & \text{if } v_i \notin E_j. \end{cases} \]

The same matrix, transposed, defines the dual hypergraph \( H^* \), in which vertices and edges exchange roles; duality maps a k-uniform hypergraph to a k-regular one and vice versa.<sup>[1](https://encyclopediaofmath.org/wiki/Hypergraph)</sup><sup> • </sup><sup>[3](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)</sup><sup> • </sup><sup>[4](https://citeseerx.ist.psu.edu/document?doi=3b78807648f1ee9b5a2010f0f45c0c28ad0e672e&repid=rep1&type=pdf)</sup> A hypergraph can also be represented as a bipartite incidence graph, whose two parts are the vertex set \( V \) and the edge set \( \mathcal{E} \), with an adjacency exactly when a vertex and an edge are incident in the hypergraph.<sup>[7](https://people.cs.uchicago.edu/~laci/23comb/hw.html)</sup>

Paths, connectedness, and distance carry over from graph theory: a path is an alternating sequence of vertices and hyperedges, a hypergraph is connected when every pair of vertices is joined by a path, and many graph concepts such as planarity, the chromatic number, and stability numbers apply to hypergraphs along with many applicable theorems.<sup>[3](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)</sup><sup> • </sup><sup>[1](https://encyclopediaofmath.org/wiki/Hypergraph)</sup>

## Special classes

**Uniform hypergraphs.** A hypergraph is k-uniform when every hyperedge contains exactly \( k \) vertices. The Fano hypergraph, built from the [Fano plane](https://www.edgepedia.org/fano-plane), the finite projective plane of order 2, has vertex set \( \{0, 1, 2, 3, 4, 5, 6\} \) and seven hyperedges such as 013, 045, and 026; its rank and co-rank are both 3, so it is 3-uniform.<sup>[3](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)</sup> Steiner systems are k-uniform hypergraphs in which every t-element subset of vertices lies in exactly one hyperedge; the complete graph \( K_n \) is the [Steiner system](https://www.edgepedia.org/steiner-system) \( S(2, 2, n) \), and Steiner triple systems \( S(2, 3, n) \) include the Fano plane on 7 vertices.<sup>[3](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)</sup>

**Simple and linear hypergraphs.** A hypergraph is simple when no hyperedge contains another, and linear when it is simple and any two hyperedges intersect in at most one vertex. A hereditary hypergraph is one in which every nonempty subset of a hyperedge is itself a hyperedge; adding the empty set turns it into a simplicial complex.<sup>[3](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)</sup>

## History

The French mathematician Claude Berge of C.N.R.S., Paris, developed the theory in works such as *Théorie des Graphes et des Hypergraphes* and a 1970 paper with Michel Las Vergnas on a König-type theorem for hypergraphs, and a 1979 survey with Berge as author connected hypergraphs to packing problems and integer programming.<sup>[8](https://nyaspubs.onlinelibrary.wiley.com/doi/10.1111/j.1749-6632.1970.tb56451.x)</sup><sup> • </sup><sup>[9](https://oamonitor.ireland.openaire.eu/rpo/rcsi/search/publication?pid=10.1016%2Fs0167-5060%2808%2970816-1)</sup> Extremal problems on hypergraph coloring trace back to the classical investigations of the 1920s and 1930s that gave rise to [Ramsey theory](https://www.edgepedia.org/ramsey-theory), and the Erdős-Hajnal hypergraph coloring problem, posed in 1961, became a central question of extremal combinatorics.<sup>[10](https://www.osti.gov/etdeweb/biblio/21610010)</sup>

## Why hypergraphs matter

A graph edge joins exactly two objects, so a graph cannot directly express a relationship shared by three or more objects at once. Hypergraphs keep that group structure explicit, which makes them a natural generalization of networks to systems with interactions beyond pairwise ones.<sup>[11](https://www.nature.com/articles/s42005-021-00710-4)</sup>

**Reconstruction from pairwise data.** Higher-order data are often inaccessible, and many systems record only pairwise links. A hypergraph can be reconstructed from a network \( G \) by seeking a hypergraph \( H \) whose projection is \( G \), meaning every edge of \( G \) appears jointly in at least one hyperedge of \( H \) and no two disconnected nodes of \( G \) share a hyperedge; principled reconstruction methods based on information-theoretic parsimony and statistical evidence are preferred over ad hoc choices.<sup>[12](https://www.nature.com/articles/s42005-021-00637-w)</sup> Filtering methods have also been extended to hypergraphs to identify statistically overexpressed hyperlinks, since pairwise filtering can produce both false positives, such as a triangle of authors who never published together, and false negatives.<sup>[11](https://www.nature.com/articles/s42005-021-00710-4)</sup>

## Computational complexity

Problems that are easy on graphs often become hard on hypergraphs. Deciding whether a hypergraph has a perfect matching is NP-complete even for 3-graphs, where every edge has size 3, and this was one of Karp's original 21 NP-complete problems, so algorithmic work focuses on approximation algorithms and sufficient conditions such as minimum-degree thresholds.<sup>[5](https://people.maths.ox.ac.uk/keevash/papers/icm-survey-arxiv.pdf)</sup> Coloring shows the same pattern: a 2-colorable graph can be 2-colored in linear time by depth-first search, but the problem is NP-hard for hypergraphs even when all edges have size at most 3, and the best algorithms for coloring a 2-colorable k-uniform hypergraph properly require roughly \( n^{1-1/k} \) colors, approaching the trivial bound of \( n \) as \( k \) grows.<sup>[13](https://web.math.princeton.edu/~nalon/PDFS/mahajan3.pdf)</sup><sup> • </sup><sup>[14](https://arxiv.org/abs/1506.06444)</sup>

## Hypergraph learning and applications

**Neural networks on hypergraphs.** Hypergraph neural networks (HGNNs) extend graph neural networks to data with higher-order relationships. A 2025 survey in the Journal of the Operations Research Society of China categorizes mainstream models into five types: [hypergraph convolutional networks](https://www.edgepedia.org/hypergraph-convolutional-network) (HGCNs), hypergraph attention networks (HGATs), hypergraph autoencoders (HGAEs), hypergraph recurrent networks (HGRNs), and deep hypergraph generative models (DHGGMs), with HGCNs further divided into spectral and spatial variants.<sup>[6](https://link.springer.com/article/10.1007/s40305-025-00630-y)</sup> An earlier KDD 2024 survey breaks HNN design into four components, input features, input structures, message-passing schemes, and training strategies, and reports applications in recommendation, bioinformatics and medical science, time series analysis, and computer vision.<sup>[15](https://arxiv.org/abs/2404.01039)</sup> Reported vision tasks include object detection, 3D shape recognition, image inpainting, and pose estimation.<sup>[6](https://link.springer.com/article/10.1007/s40305-025-00630-y)</sup>

**Science applications.** In network biology, hypergraphs have been used to study metabolic networks, clusters in protein-protein interaction networks, and shortest paths in signaling pathways, the last being the best-developed use of directed hypergraphs in the field, although adoption remains limited by the availability of data and annotations.<sup>[16](https://pmc.ncbi.nlm.nih.gov/articles/PMC11321866/)</sup> A dedicated open-source library, DHG, supports learning hypergraph neural networks, and hypergraph computation is described as a methodology for modeling complex high-order correlations in domains such as the Internet, social networks, and biological networks.<sup>[17](https://www.sciencedirect.com/science/article/pii/S2095809924002510)</sup>

**When pairwise models suffice.** Reducing higher-order structure to pairwise projections loses information, but the loss is not uniform across tasks. Experiments on 15 real-world datasets for hyperedge prediction found diminishing returns, with small projection orders already achieving accuracy comparable to near-perfect approximations, while datasets whose pairwise interactions say little about higher-order interactions lose much accuracy when reduced to pairwise abstractions.<sup>[18](https://arxiv.org/abs/2001.11181)</sup> In some dynamical settings the reduction is exact: a class of social impact models with higher-order interactions on hypergraphs can be mapped to an equivalent pairwise model on a weighted projected network that preserves the microscopic probabilities of node state changes.<sup>[19](https://doi.org/10.1103/wy1x-3px8)</sup>

## References

1. [Hypergraph, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Hypergraph)
2. [Hypergraph Theory Basics, R. Kempe](https://blog.rkempe.ca/posts/2024/11/hypergraph-theory-basics/)
3. [A. Bretto, Hypergraph Theory (Springer, 2013), Chapter 1](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)
4. [University of London lecture notes on hypergraphs](https://citeseerx.ist.psu.edu/document?doi=3b78807648f1ee9b5a2010f0f45c0c28ad0e672e&repid=rep1&type=pdf)
5. [P. Keevash, Hypergraph matchings and designs (2018)](https://people.maths.ox.ac.uk/keevash/papers/icm-survey-arxiv.pdf)
6. [Recent Advances in Hypergraph Neural Networks, Journal of the Operations Research Society of China (2025)](https://link.springer.com/article/10.1007/s40305-025-00630-y)
7. [CMSC 27410 Honors Combinatorics 2023, University of Chicago](https://people.cs.uchicago.edu/~laci/23comb/hw.html)
8. [C. Berge and M. Las Vergnas, Sur un théorème du type König pour hypergraphes, Annals of the New York Academy of Sciences 175 (1970)](https://nyaspubs.onlinelibrary.wiley.com/doi/10.1111/j.1749-6632.1970.tb56451.x)
9. [C. Berge, Packing Problems and Hypergraph Theory: A Survey (1979)](https://oamonitor.ireland.openaire.eu/rpo/rcsi/search/publication?pid=10.1016%2Fs0167-5060%2808%2970816-1)
10. [The Erdos-Hajnal problem of hypergraph colouring, ETDEWEB](https://www.osti.gov/etdeweb/biblio/21610010)
11. [Detecting informative higher-order interactions in statistically validated hypergraphs, Communications Physics (2021)](https://www.nature.com/articles/s42005-021-00710-4)
12. [J.-G. Young, G. Petri, T. P. Peixoto, Hypergraph reconstruction from network data, Communications Physics (2021)](https://www.nature.com/articles/s42005-021-00637-w)
13. [Approximate Hypergraph Coloring (Mahajan et al.)](https://web.math.princeton.edu/~nalon/PDFS/mahajan3.pdf)
14. [Approximate Hypergraph Coloring under Low-discrepancy and Related Promises, arXiv:1506.06444](https://arxiv.org/abs/1506.06444)
15. [S. Kim et al., A Survey on Hypergraph Neural Networks: An In-Depth and Step-By-Step Guide, KDD 2024](https://arxiv.org/abs/2404.01039)
16. [Current and future directions in network biology, Briefings in Bioinformatics (2024)](https://pmc.ncbi.nlm.nih.gov/articles/PMC11321866/)
17. [Hypergraph Computation, Engineering, Volume 40 (2024)](https://www.sciencedirect.com/science/article/pii/S2095809924002510)
18. [How Much and When Do We Need Higher-order Information in Hypergraphs? arXiv:2001.11181](https://arxiv.org/abs/2001.11181)
19. [Reducibility of higher-order to pairwise interactions: Social impact models on hypergraphs, Phys. Rev. Research](https://doi.org/10.1103/wy1x-3px8)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph theory overview and basic objects*

*Initially written Oct 15, 2026 · Edited: Oct 25, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license