{
 "id": "epbra57txt",
 "slug": "hypergraph",
 "title": "Hypergraph",
 "updated": "2026-10-25",
 "topic_path": [
  {
   "id": "physical",
   "label": "Physical world and mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical"
  },
  {
   "id": "physical.math",
   "label": "Mathematics and statistics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math"
  },
  {
   "id": "physical.math.discrete",
   "label": "Logic and discrete mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete"
  },
  {
   "id": "physical.math.discrete.discrete",
   "label": "General discrete mathematics and discrete structures",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete"
  },
  {
   "id": "physical.math.discrete.discrete.graph-theory",
   "label": "Graph theory",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete.graph-theory"
  },
  {
   "id": "physical.math.discrete.discrete.graph-theory-overview",
   "label": "Graph theory overview and basic objects",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete.graph-theory-overview"
  }
 ],
 "geo": [
  {
   "id": "geo.nongeo.nodate.physical.math.discrete.discrete",
   "label": "Non-geographic · Not dated: General discrete mathematics and discrete structures",
   "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.nodate.physical.math.discrete.discrete",
   "path": [
    {
     "id": "geo.nongeo",
     "label": "Non-geographic",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo"
    },
    {
     "id": "geo.nongeo.nodate",
     "label": "Non-geographic · Not dated",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.nodate"
    },
    {
     "id": "geo.nongeo.nodate.physical",
     "label": "Physical world and mathematics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.nodate.physical"
    },
    {
     "id": "geo.nongeo.nodate.physical.math",
     "label": "Mathematics and statistics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.nodate.physical.math"
    },
    {
     "id": "geo.nongeo.nodate.physical.math.discrete",
     "label": "Logic and discrete mathematics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.nodate.physical.math.discrete"
    },
    {
     "id": "geo.nongeo.nodate.physical.math.discrete.discrete",
     "label": "General discrete mathematics and discrete structures",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.nodate.physical.math.discrete.discrete"
    }
   ]
  }
 ],
 "excerpt": "A hypergraph is a generalization of a graph in which an edge may join any number of vertices rather than exactly two; an ordinary graph is a 2-uniform case.",
 "snippet": "A hypergraph is a generalization of a graph in which an edge may join any number of vertices rather than exactly two; an ordinary graph is a 2-uniform case.",
 "node": "physical.math.discrete.discrete.graph-theory-overview",
 "markdown": "# Hypergraph\n\nA 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>\n\n| Key fact | Detail |\n|---|---|\n| 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> |\n| 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> |\n| 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> |\n| 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> |\n| 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> |\n| 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> |\n| 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> |\n\n## Basic definitions\n\nTwo 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>\n\n**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\n\n\\[ a_{ij} = \\begin{cases} 1 & \\text{if } v_i \\in E_j, \\\\ 0 & \\text{if } v_i \\notin E_j. \\end{cases} \\]\n\nThe 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>\n\nPaths, 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>\n\n## Special classes\n\n**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>\n\n**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>\n\n## History\n\nThe 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>\n\n## Why hypergraphs matter\n\nA 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>\n\n**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>\n\n## Computational complexity\n\nProblems 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>\n\n## Hypergraph learning and applications\n\n**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>\n\n**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>\n\n**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>\n\n## References\n\n1. [Hypergraph, Encyclopedia of Mathematics](https://encyclopediaofmath.org/wiki/Hypergraph)\n2. [Hypergraph Theory Basics, R. Kempe](https://blog.rkempe.ca/posts/2024/11/hypergraph-theory-basics/)\n3. [A. Bretto, Hypergraph Theory (Springer, 2013), Chapter 1](https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf)\n4. [University of London lecture notes on hypergraphs](https://citeseerx.ist.psu.edu/document?doi=3b78807648f1ee9b5a2010f0f45c0c28ad0e672e&repid=rep1&type=pdf)\n5. [P. Keevash, Hypergraph matchings and designs (2018)](https://people.maths.ox.ac.uk/keevash/papers/icm-survey-arxiv.pdf)\n6. [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)\n7. [CMSC 27410 Honors Combinatorics 2023, University of Chicago](https://people.cs.uchicago.edu/~laci/23comb/hw.html)\n8. [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)\n9. [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)\n10. [The Erdos-Hajnal problem of hypergraph colouring, ETDEWEB](https://www.osti.gov/etdeweb/biblio/21610010)\n11. [Detecting informative higher-order interactions in statistically validated hypergraphs, Communications Physics (2021)](https://www.nature.com/articles/s42005-021-00710-4)\n12. [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)\n13. [Approximate Hypergraph Coloring (Mahajan et al.)](https://web.math.princeton.edu/~nalon/PDFS/mahajan3.pdf)\n14. [Approximate Hypergraph Coloring under Low-discrepancy and Related Promises, arXiv:1506.06444](https://arxiv.org/abs/1506.06444)\n15. [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)\n16. [Current and future directions in network biology, Briefings in Bioinformatics (2024)](https://pmc.ncbi.nlm.nih.gov/articles/PMC11321866/)\n17. [Hypergraph Computation, Engineering, Volume 40 (2024)](https://www.sciencedirect.com/science/article/pii/S2095809924002510)\n18. [How Much and When Do We Need Higher-order Information in Hypergraphs? arXiv:2001.11181](https://arxiv.org/abs/2001.11181)\n19. [Reducibility of higher-order to pairwise interactions: Social impact models on hypergraphs, Phys. Rev. Research](https://doi.org/10.1103/wy1x-3px8)\n\n---\n*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*\n\n*Initially written Oct 15, 2026 · Edited: Oct 25, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n",
 "same_as": [
  "https://www.math.ucdavis.edu/~saito/data/tensor/bretto_hypergraph-theory.pdf",
  "https://people.cs.uchicago.edu/~laci/23comb/hw.html",
  "https://web.math.princeton.edu/~nalon/PDFS/mahajan3.pdf"
 ],
 "url": "https://www.edgepedia.org/hypergraph",
 "markdown_url": "https://www.edgepedia.org/hypergraph.md",
 "license": {
  "name": "Edgepedia Community License 1.0",
  "url": "https://www.edgepedia.org/edgepedia/license",
  "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.",
  "spdx": "LicenseRef-Edgepedia-Community-1.0"
 },
 "credit": "\"Hypergraph\", Edgepedia (EdgeChat), https://www.edgepedia.org/hypergraph. Edgepedia Community License 1.0.",
 "credit_md": "\"[Hypergraph](https://www.edgepedia.org/hypergraph)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/hypergraph](https://www.edgepedia.org/hypergraph). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).",
 "credit_html": "\"<a href=\"https://www.edgepedia.org/hypergraph\">Hypergraph</a>\", Edgepedia (EdgeChat), <a href=\"https://www.edgepedia.org/hypergraph\">https://www.edgepedia.org/hypergraph</a>. <a href=\"https://www.edgepedia.org/edgepedia/license\">Edgepedia Community License 1.0</a>.",
 "speakable": "A hypergraph is a generalization of a graph in which an edge may join any number of vertices rather than exactly two; an ordinary graph is a 2-uniform case."
}