View source for Hypergraph

{{Short description|Generalization of graph theory}}
[[File:Hypergraph-wikipedia.svg|frame|An example of an undirected hypergraph, with
<math>X = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}</math> and
<math>E = \{e_1,e_2,e_3,e_4\} = </math>
<math>\{\{v_1, v_2, v_3\},</math>
<math>\{v_2,v_3\},</math>
<math>\{v_3,v_5,v_6\},</math>
<math>\{v_4\}\}</math>.
This hypergraph has order 7 and size 4. Here, edges do not just connect two vertices but several, and are represented by colors.]]
[[File:PAOH hypergraph representation.png|alt=PAOH visualization of a hypergraph|thumb|Alternative representation of the hypergraph reported in the figure above, called PAOH.<ref name="paoh">{{Cite journal|last1=Valdivia|first1=Paola|last2=Buono|first2=Paolo|last3=Plaisant|first3=Catherine|last4=Dufournaud|first4=Nicole|last5=Fekete|first5=Jean-Daniel|date=2020|title=Analyzing Dynamic Hypergraphs with Parallel Aggregated Ordered Hypergraph Visualization|journal=IEEE Transactions on Visualization and Computer Graphics|publisher=IEEE|volume=26|issue=1|pages=12|doi=10.1109/TVCG.2019.2933196|pmid=31398121|hdl=11586/518500 |s2cid=199518871|issn=1077-2626|url=https://hal.inria.fr/hal-02264960/file/Paohvis.pdf|eissn=1941-0506|access-date=2020-09-08|archive-date=2021-01-26|archive-url=https://web.archive.org/web/20210126021713/https://hal.inria.fr/hal-02264960/file/Paohvis.pdf|url-status=live}}</ref> Edges are vertical lines connecting vertices. V7 is an isolated vertex. Vertices are aligned to the left. The legend on the right shows the names of the edges.]]
[[File:Directed hypergraph example.svg|thumb|An example of a directed hypergraph, with
<math>X = \{1, 2, 3, 4, 5, 6\}</math> and
<math>E = \{a_1, a_2, a_3, a_4, a_5\} = </math>
<math>\{(\{1\}, \{2\}),</math>
<math>(\{2\}, \{3\}),</math>
<math>(\{3\}, \{1\}),</math>
<math>(\{2, 3\}, \{4, 5\}),</math>
<math>(\{3, 5\}, \{6\})\}</math>
]]
In [[mathematics]], a '''hypergraph''' is a generalization of a [[Graph (discrete mathematics)|graph]] in which an [[graph theory|edge]] can join any number of [[vertex (graph theory)|vertices]]. In contrast, in an ordinary graph, an edge connects exactly two vertices.

Formally, a '''directed hypergraph''' is a pair <math>(X,E)</math>, where <math>X</math> is a set of elements called ''nodes'', ''vertices'', ''points'', or ''elements'' and <math>E</math> is a set of pairs of subsets of <math>X</math>. Each of these pairs <math>(D,C)\in E</math> is called an ''edge'' or ''[[hyperedge]]'';  the vertex subset <math>D</math> is known as its ''tail'' or ''domain'', and  <math>C</math> as its  ''head'' or ''[[codomain]]''.

The '''order of a hypergraph''' <math>(X,E)</math> is the number of vertices in <math>X</math>. The '''size of the hypergraph''' is the number of edges in <math>E</math>. The '''order of an edge''' <math>e=(D,C)</math> in a directed hypergraph is <math>|e| = (|D|,|C|)</math>: that is, the number of vertices in its tail followed by the number of vertices in its head.

The definition above generalizes from a [[directed graph]] to a directed hypergraph by defining the head or tail of each edge as a set of vertices (<math>C\subseteq X</math> or <math>D\subseteq X</math>) rather than as a single vertex. A graph is then the special case where each of these sets contains only one element. Hence any standard graph theoretic concept that is independent of the edge orders <math>|e|</math> will generalize to hypergraph theory.

An '''undirected hypergraph''' <math>(X, E)</math> is an undirected graph whose edges connect not just two vertices, but an arbitrary number.<ref>{{cite arXiv |mode=cs2
 | last1 = Ouvrard | first1 = Xavier | author1-link = Xavier Ouvrard
 | eprint=2002.05014
 | title = Hypergraphs: an introduction and review
 | year = 2020
 | class = cs.DM }}.</ref> An undirected hypergraph is also called a ''set system'' or a ''[[family of sets]]'' drawn from the [[universal set]].

Hypergraphs can be viewed as [[incidence structure]]s.  In particular, there is a bipartite "incidence graph" or "[[Levi graph]]" corresponding to every hypergraph, and conversely, every [[bipartite graph]] can be regarded as the incidence graph of a hypergraph when it is 2-colored and it is indicated which color class corresponds to hypergraph vertices and which to hypergraph edges.

Hypergraphs have many other names.  In [[computational geometry]], an undirected hypergraph may sometimes be called a '''range space''' and then the hyperedges are called ''ranges''.<ref>{{citation
 | last1 = Haussler | first1 = David | author1-link = David Haussler
 | last2 = Welzl | first2 = Emo | author2-link = Emo Welzl
 | doi = 10.1007/BF02187876
 | issue = 2
 | journal = [[Discrete and Computational Geometry]]
 | mr = 884223
 | pages = 127–151
 | title = ε-nets and simplex range queries
 | volume = 2
 | year = 1987| doi-access = free
 }}.</ref>
In [[Cooperative game theory|cooperative game]] theory, hypergraphs are called '''simple games''' (voting games); this notion is applied to solve problems in [[social choice theory]].  In some literature edges are referred to as ''hyperlinks'' or ''connectors''.<ref>{{cite book |first=Judea |last=Pearl |title=Heuristics: Intelligent Search Strategies for Computer Problem Solving |url=https://books.google.com/books?id=0XtQAAAAMAAJ |year=1984 |publisher=Addison-Wesley Publishing Company |isbn=978-0-201-05594-8 |page=25 |access-date=2021-06-12 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204155707/https://books.google.com/books?id=0XtQAAAAMAAJ |url-status=live }}</ref>

The collection of hypergraphs is a [[Category (mathematics)|category]] with hypergraph [[homomorphism]]s as [[morphism]]s.

==Applications==
Undirected hypergraphs are useful in modelling such things as satisfiability problems,<ref>{{cite conference
 |url          = https://ieeexplore.ieee.org/document/4031385
 |title        = Witnesses for non-satisfiability of dense random 3CNF formulas
 |last1        = Feige
 |first1       = Uriel
 |last2        = Kim
 |first2       = Jeong Han
 |last3        = Ofek
 |first3       = Eran
 |date         = 2006
 |publisher    = IEEE
 |conference   = 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
 |pages        = 497–508
 |doi          = 10.1109/FOCS.2006.78
 |access-date  = 2021-01-20
 |archive-date = 2021-01-27
 |archive-url  = https://web.archive.org/web/20210127222018/https://ieeexplore.ieee.org/document/4031385
 |url-status   = live
|url-access= subscription
 }}</ref> databases,<ref name=database /> machine learning,<ref name=hyperx /> and [[Steiner tree problem]]s.<ref>{{cite book
 |last1        = Brazil
 |first1       = M
 |last2        = Zachariasen
 |first2       = M
 |title = Optimal Interconnection Trees in the Plane
 |chapter = Steiner Trees in Graphs and Hypergraphs
 |series = Algorithms and Combinatorics
 |date         = 2015
 |chapter-url          = https://link.springer.com/chapter/10.1007/978-3-319-13915-9_5
 |volume       = 29
 |pages        = 301–317
 |doi          = 10.1007/978-3-319-13915-9_5
 |publisher    = Springer
 |isbn         = 978-3-319-13915-9
 |access-date  = 2021-01-20
 |archive-date = 2021-01-29
 |archive-url  = https://web.archive.org/web/20210129091642/https://link.springer.com/chapter/10.1007/978-3-319-13915-9_5
 |url-status   = live
}}</ref> They have been extensively used in [[machine learning]] tasks as the data model and classifier [[regularization (mathematics)]].<ref>{{citation | last1 = Zhou | first1 = Dengyong | last2 = Huang | first2 = Jiayuan | last3 = Scholkopf | first3 = Bernhard | issue = 2 | title = Advances in Neural Information Processing Systems | pages = 1601–8 | chapter = Learning with hypergraphs: clustering, classification, and embedding | year = 2006 | publisher = MIT Press | isbn = 9780262256919 | chapter-url = https://ieeexplore.ieee.org/document/6287378 | access-date = 2021-07-24 | archive-date = 2021-10-22 | archive-url = https://web.archive.org/web/20211022175429/https://ieeexplore.ieee.org/document/6287378 | url-status = live }}</ref> The applications include [[recommender system]] (communities as hyperedges),<ref>{{citation|last1=Ghoshal | first1=Gourab | last2=Zlatic | first2=Vinko | last3=Caldarelli | first3=Guido | last4=Newman | first4=Mark E.J.| journal = Physical Review E| title = Random Hypergraphs and their applications  |volume=79 |date= 2009 | issue=6 | page=066118 |doi=10.1103/PhysRevE.79.066118 | pmid=19658575 | arxiv=0903.0419 | bibcode=2009PhRvE..79f6118G | s2cid=6391099 }}</ref><ref>{{citation|last1=Tan | first1=Shulong | last2=Bu | first2=Jiajun | last3=Chen | first3=Chun | last4=Xu | first4=Bin | last5=Wang | first5=Can | last6=He | first6=Xiaofei| journal = ACM Transactions on Multimedia Computing, Communications, and Applications| title = Using rich social media information for music recommendation via hypergraph model |url=https://www.researchgate.net/publication/226075153| bibcode=2011smma.book..213T |volume=7S |issue=1 |at=Article 22 |date=October 2011 |doi=10.1145/2037676.2037679 | s2cid=432036 }}</ref> [[image retrieval]] (correlations as hyperedges),<ref>{{citation|last1=Liu | first1=Qingshan | last2=Huang | first2=Yuchi | last3=Metaxas | first3=Dimitris N. |issue = 10–11| journal = Pattern Recognition| title = Hypergraph with sampling for image retrieval| pages=2255–2262| year = 2013| doi=10.1016/j.patcog.2010.07.014 | volume=44}}</ref> and [[bioinformatics]] (biochemical interactions as hyperedges).<ref>{{citation|last1=Patro |first1=Rob | last2=Kingsoford | first2=Carl| issue = 10–11| journal = Bioinformatics| title = Predicting protein interactions via parsimonious network history inference| year = 2013| pages=237–246|doi=10.1093/bioinformatics/btt224 |pmid=23812989 |pmc=3694678 | volume=29}}</ref> Representative hypergraph learning techniques include hypergraph [[spectral clustering]] that extends the [[spectral graph theory]] with hypergraph Laplacian,<ref>{{citation | last1=Gao | first1=Tue | last2=Wang | first2=Meng | last3=Zha | first3=Zheng-Jun | last4=Shen | first4=Jialie | last5=Li | first5=Xuelong | last6=Wu | first6=Xindong | issue=1 | journal=IEEE Transactions on Image Processing | volume=22 | title=Visual-textual joint relevance learning for tag-based social image search | year=2013 | pages=363–376 | url=http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | doi=10.1109/tip.2012.2202676 | pmid=22692911 | bibcode=2013ITIP...22..363Y | s2cid=7432373 | access-date=2017-09-22 | archive-date=2017-09-23 | archive-url=https://web.archive.org/web/20170923002956/http://ink.library.smu.edu.sg/cgi/viewcontent.cgi?article=2510&context=sis_research | url-status=live }}</ref> and hypergraph [[semi-supervised learning]] that introduces extra hypergraph structural cost to restrict the learning results.<ref>{{citation|last1=Tian|first1=Ze|last2=Hwang|first2=TaeHyun|last3=Kuang|first3=Rui|issue = 21| journal = Bioinformatics| title = A hypergraph-based learning algorithm for classifying gene expression and arrayCGH data with prior knowledge| year = 2009| pages=2831–2838|doi=10.1093/bioinformatics/btp467|pmid=19648139| volume=25|doi-access=free}}</ref> For large scale hypergraphs, a distributed framework<ref name=hyperx /> built using [[Apache Spark]] is also available. It can be desirable to study hypergraphs where all hyperedges have the same cardinality; a ''k-uniform hypergraph'' is a hypergraph such that all its hyperedges have size ''k''. (In other words, one such hypergraph is a collection of sets, each such set a hyperedge connecting ''k'' nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on.

Directed hypergraphs can be used to model things including telephony applications,<ref>{{cite journal
 |last=Goldstein
 |first=A.
 |date=1982
| title      = A Directed Hypergraph Database: A Model for the Local Loop Telephone Plant
| url        = https://archive.org/details/bstj61-9-2529
| journal    = Bell System Technical Journal
| volume     = 61 |issue=9 |pages=2529–54 |doi=10.1002/j.1538-7305.1982.tb03439.x 
|s2cid=11290643
 }}</ref> detecting [[money laundering]],<ref>{{cite conference
| url = http://fc17.ifca.ai/bitcoin/papers/bitcoin17-final17.pdf
| title = Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph
| conference = Financial Cryptography and Data Security
| last1 = Ranshous
| first1 = Stephen
| last2 = Joslyn
| first2 = Cliff
| last3 = Kreyling
| first3 = Sean
| last4 = Nowak
| first4 = Kathleen
| last5 = Samatova
| first5 = Nagiza
| last6 = West
| first6 = Curtis
| last7 = Winters
| first7 = Samuel
| date = 2017
| publisher = Springer
| doi = 10.1007/978-3-319-70278-0_16
| access-date = 2021-01-20
| archive-date = 2021-07-15
| archive-url = https://web.archive.org/web/20210715183918/http://fc17.ifca.ai/bitcoin/papers/bitcoin17-final17.pdf
| url-status = live
}}</ref> operations research,<ref name=ausiello>{{cite journal
 |last1=Ausiello
 |first1=Giorgio
 |last2=Laura
 |first2=Luigi
 |date=2017
| title      = Directed hypergraphs: Introduction and fundamental algorithms - A survey
| pages = 293–306
| doi = 10.1016/j.tcs.2016.03.016
| journal    = Theoretical Computer Science
| volume     = 658
| doi-access= free
}}</ref> and transportation planning. They can also be used to model [[Horn-satisfiability]].<ref name=gallo />

==Generalizations of concepts from graphs==
Many [[theorem]]s and concepts involving graphs also hold for hypergraphs, in particular:

*[[Matching in hypergraphs]];
*[[Vertex cover in hypergraphs]] (also known as: '''transversal''');
*[[Line graph of a hypergraph]];
*[[Hypergraph grammar]] - created by augmenting a class of hypergraphs with a set of replacement rules;
*[[Ramsey's theorem]];
*[[Erdős–Ko–Rado theorem]];
*[[Kruskal–Katona theorem]] on uniform hypergraphs;
*[[Hall-type theorems for hypergraphs]].

In directed hypergraphs: [[transitive closure]], and shortest path problems.<ref name=ausiello />

==Hypergraph drawing==
[[File:CircuitoDosMallas.png|thumb|This [[circuit diagram]] can be interpreted as a drawing of a hypergraph in which four vertices (depicted as white rectangles and disks) are connected by three hyperedges drawn as trees.]]
Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.

In one possible visual representation for hypergraphs, similar to the standard [[graph drawing]] style in which curves in the plane are used to depict graph edges, a hypergraph's vertices are depicted as points, disks, or boxes, and its hyperedges are depicted as trees that have the vertices as their leaves.<ref>{{citation
 | last = Sander
 | first = G.
 | contribution = Layout of directed hypergraphs with orthogonal hyperedges
 | pages = 381–6
 | publisher = Springer
 | isbn = 978-3-540-24595-7
 | series = [[Lecture Notes in Computer Science]]
 | title = Proc. 11th International Symposium on Graph Drawing (GD 2003)
 | contribution-url = http://gdea.informatik.uni-koeln.de/585/1/hypergraph.ps
 | volume = 2912
 | year = 2003
 | title-link = International Symposium on Graph Drawing
 | access-date = 2010-05-17
 | archive-date = 2011-07-18
 | archive-url = https://web.archive.org/web/20110718171911/http://gdea.informatik.uni-koeln.de/585/1/hypergraph.ps
 | url-status = live
 }}.</ref><ref>{{citation
 | last1 = Eschbach
 | first1 = Thomas
 | last2 = Günther
 | first2 = Wolfgang
 | last3 = Becker
 | first3 = Bernd
 | issue = 2
 | journal = [[Journal of Graph Algorithms and Applications]]
 | pages = 141–157
 | title = Orthogonal hypergraph drawing for improved visibility
 | url = http://jgaa.info/accepted/2006/EschbachGuentherBecker2006.10.2.pdf
 | volume = 10
 | year = 2006
 | doi = 10.7155/jgaa.00122
 | doi-access = free
 | access-date = 2010-05-17
 | archive-date = 2011-07-18
 | archive-url = https://web.archive.org/web/20110718121435/http://jgaa.info/accepted/2006/EschbachGuentherBecker2006.10.2.pdf
 | url-status = live
 }}.</ref> If the vertices are represented as points, the hyperedges may also be shown as smooth curves that connect sets of points, or as [[simple closed curve]]s that enclose sets of points.<ref>{{citation
 | last = Mäkinen | first = Erkki
 | doi = 10.1080/00207169008803875
 | issue = 3
 | journal = International Journal of Computer Mathematics
 | pages = 177–185
 | title = How to draw a hypergraph
 | volume = 34
 | year = 1990}}.</ref><ref>{{citation
 | last1 = Bertault | first1 = François
 | last2 = Eades | first2 = Peter | title = Graph Drawing
 | author2-link = Peter Eades
 | contribution = Drawing hypergraphs in the subset standard
 | doi = 10.1007/3-540-44541-2_15
 | pages = 45–76
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 1984
 | year = 2001| title-link = International Symposium on Graph Drawing
 | isbn = 978-3-540-41554-1
 | doi-access = free
 }}.</ref><ref>{{citation
 | last1 = Naheed Anjum | first1 = Arafat
 | last2 = Bressan | first2 = Stéphane
 | title = Database and Expert Systems Applications
 | contribution = Hypergraph Drawing by Force-Directed Placement
 | doi = 10.1007/978-3-319-64471-4_31
 | pages = 387–394
 | publisher = Springer International Publishing
 | series = Lecture Notes in Computer Science
 | volume = 10439
 | year = 2017| isbn = 978-3-319-64470-7
 }}.</ref>

[[File:Venn's four ellipse construction.svg|thumb|An order-4 Venn diagram, which can be interpreted as a subdivision drawing of a hypergraph with 15 vertices (the 15 colored regions) and 4 hyperedges (the 4 ellipses)]]
In another style of hypergraph visualization, the subdivision model of hypergraph drawing,<ref>{{citation
 | last1 = Kaufmann | first1 = Michael
 | last2 = van Kreveld | first2 = Marc
 | last3 = Speckmann | first3 = Bettina | title = Graph Drawing
 | author3-link = Bettina Speckmann
 | contribution = Subdivision drawings of hypergraphs
 | doi = 10.1007/978-3-642-00219-9_39
 | pages = 396–407
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 5417
 | year = 2009| title-link = International Symposium on Graph Drawing
 | isbn = 978-3-642-00218-2
 | doi-access = free
 }}.</ref> the plane is subdivided into regions, each of which represents a single vertex of the hypergraph. The hyperedges of the hypergraph are represented by contiguous subsets of these regions, which may be indicated by coloring, by drawing outlines around them, or both. An order-''n'' [[Venn diagram]], for instance, may be viewed as a subdivision drawing of a hypergraph with ''n'' hyperedges (the curves defining the diagram) and 2<sup>''n''</sup>&nbsp;−&nbsp;1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition of [[planar graph]]s, it is [[NP-complete]] to determine whether a hypergraph has a planar subdivision drawing,<ref>{{citation
 | last1 = Johnson | first1 = David S. | author1-link = David S. Johnson
 | last2 = Pollak | first2 = H. O.
 | doi = 10.1002/jgt.3190110306
 | issue = 3
 | journal = [[Journal of Graph Theory]]
 | pages = 309–325
 | title = Hypergraph planarity and the complexity of drawing Venn diagrams
 | volume = 11
 | year = 2006}}.</ref> but the existence of a drawing of this type may be tested efficiently when the adjacency pattern of the regions is constrained to be a path, cycle, or tree.<ref>{{citation
 | last1 = Buchin | first1 = Kevin
 | last2 = van Kreveld | first2 = Marc
 | last3 = Meijer | first3 = Henk
 | last4 = Speckmann | first4 = Bettina
 | last5 = Verbeek | first5 = Kevin
 | title = Graph Drawing
 | contribution = On planar supports for hypergraphs
 | doi = 10.1007/978-3-642-11805-0_33
 | pages = 345–356
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 5849
 | year = 2010| title-link = International Symposium on Graph Drawing
 | isbn = 978-3-642-11804-3
 | doi-access = free
 }}.</ref>

An alternative representation of the hypergraph called PAOH<ref name="paoh" /> is shown in the figure on top of this article. Edges are vertical lines connecting vertices. Vertices are aligned on the left. The legend on the right shows the names of the edges. It has been designed for dynamic hypergraphs but can be used for simple hypergraphs as well.

==Hypergraph coloring==
Classic hypergraph coloring is assigning one of the colors from set <math>\{1,2,3,...,\lambda\}</math> to every vertex of a hypergraph in such a way that each hyperedge contains at least two vertices of distinct colors. In other words, there must be no monochromatic hyperedge with cardinality at least 2. In this sense it is a direct generalization of graph coloring. The minimum number of used distinct colors over all colorings is called the chromatic number of a hypergraph.

Hypergraphs for which there exists a coloring using up to ''k'' colors are referred to as ''k-colorable''. The 2-colorable hypergraphs are exactly the bipartite ones.

There are many generalizations of classic hypergraph coloring. One of them is the so-called mixed hypergraph coloring, when monochromatic edges are allowed. Some mixed hypergraphs are uncolorable for any number of colors. A general criterion for uncolorability is unknown.  When a mixed hypergraph is colorable, then the minimum and maximum number of used colors are called the lower and upper chromatic numbers respectively.<ref>{{Cite web |title=Vitaly Voloshin: Mixed Hypergraph Coloring Website |url=http://spectrum.troy.edu/voloshin/mh.html |access-date=2022-04-27 |website=spectrum.troy.edu |archive-date=2022-01-20 |archive-url=https://web.archive.org/web/20220120170127/http://spectrum.troy.edu/voloshin/mh.html |url-status=live }}</ref>

==Properties of hypergraphs==
A hypergraph can have various properties, such as:
* '''Empty''' - has no edges.
* '''Non-simple''' ''(or'' '''multiple''''')'' - has loops (hyperedges with a single vertex) or repeated edges, which means there can be two or more edges containing the same set of vertices.
* '''Simple''' - has no loops and no repeated edges.
* '''<math>d </math>-regular''' - every vertex has degree <math>d </math>, i.e., contained in exactly <math>d </math> hyperedges.
*'''2-colorable''' - its vertices can be partitioned into two classes ''U'' and ''V'' in such a way that each hyperedge with cardinality at least 2 contains at least one vertex from both classes. An alternative term is '''[[Property B]]'''.
** Two stronger properties are [[Bipartite hypergraph|'''bipartite''']] and [[Balanced hypergraph|'''balanced''']].
* '''<math>k </math>-uniform''' - each hyperedge contains precisely <math>k</math> vertices.
* '''<math>k </math>-partite''' - the vertices are partitioned into <math>k</math> parts, and each hyperedge contains precisely one vertex of each type.
** Every '''<math>k </math>-partite''' hypergraph (for  <math>k\geq 2</math>) is both  '''<math>k </math>'''-uniform and bipartite (and 2-colorable).
* '''Reduced''':<ref>{{Cite journal |last=Fagin |first=Ronald |date=1983-07-01 |title=Degrees of acyclicity for hypergraphs and relational database schemes |journal=Journal of the ACM |volume=30 |issue=3 |pages=514–550 |doi=10.1145/2402.322390 |issn=0004-5411|doi-access=free }}</ref> no hyperedge is a strict subset of another hyperedge; equivalently, every hyperedge is maximal for inclusion. The '''reduction''' of a hypergraph is the reduced hypergraph obtained by removing every hyperedge which is included in another hyperedge.
* '''Downward-closed''' - every subset of an undirected hypergraph's edges is a hyperedge too. A downward-closed hypergraph is usually called an '''[[abstract simplicial complex]]'''. It is generally not reduced, unless all hyperedges have cardinality 1.
** An abstract simplicial complex with the ''augmentation property'' is called a '''[[matroid]]'''.
* '''Laminar''': for any two hyperedges, either they are disjoint, or one is included in the other. In other words, the set of hyperedges forms a [[laminar set family]].

== Related hypergraphs ==
Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called ''subhypergraphs'', ''partial hypergraphs'' and ''section hypergraphs''.

Let <math>H=(X,E)</math> be the hypergraph consisting of vertices

:<math>X = \lbrace x_i \mid i \in I_v \rbrace,</math>

and having ''edge set''

:<math>E = \lbrace e_i \mid i\in I_e, e_i \subseteq X, e_i \neq \emptyset \rbrace,</math>

where <math>I_v</math> and <math>I_e</math> are the [[index set]]s of the vertices and edges respectively.

A '''subhypergraph''' is a hypergraph with some vertices removed.  Formally, the subhypergraph <math>H_A</math> induced by <math>A \subseteq X </math> is defined as

:<math>H_A=\left(A, \lbrace e \cap A \mid e \in E, 
e \cap A \neq \emptyset \rbrace \right).</math>

An alternative term is the '''restriction of ''H'' to ''A'''''.<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{rp|468}}

An '''extension of a subhypergraph''' is a hypergraph where each hyperedge of <math>H</math> which is partially contained in the subhypergraph <math>H_A</math> is fully contained in the extension <math>Ex(H_A)</math>. Formally
:<math>Ex(H_A) = (A \cup A', E' )</math> with <math>A' = \bigcup_{e \in E} e \setminus A</math> and <math>E' = \lbrace e \in E \mid e \subseteq (A \cup A') \rbrace</math>.

The '''partial hypergraph''' is a hypergraph with some edges removed.<ref name="lp" />{{rp|468}} Given a subset <math>J \subset I_e</math> of the edge index set, the partial hypergraph generated by <math>J</math> is the hypergraph

:<math>\left(X, \lbrace e_i \mid i\in J \rbrace \right).</math>

Given a subset <math>A\subseteq X</math>, the '''section hypergraph''' is the partial hypergraph

:<math>H \times A = \left(A, \lbrace e_i \mid 
i\in I_e, e_i \subseteq A   \rbrace \right).</math>
The '''dual''' <math>H^*</math> of <math>H</math> is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by <math>\lbrace e_i \rbrace</math> and whose edges are given by <math>\lbrace X_m \rbrace</math> where

:<math>X_m = \lbrace e_i \mid x_m \in e_i \rbrace. </math>

When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an [[involution (mathematics)|involution]], i.e.,

:<math>\left(H^*\right)^* = H.</math>

A [[connected graph]] ''G'' with the same vertex set as a connected hypergraph ''H'' is a '''host graph''' for ''H'' if every hyperedge of ''H'' [[induced subgraph|induces]] a connected subgraph in  ''G''. For a disconnected hypergraph ''H'', ''G'' is a host graph if there is a bijection between the [[connected component (graph theory)|connected components]] of ''G'' and of ''H'', such that each connected component ''G<nowiki>'</nowiki>'' of ''G'' is a host of the corresponding ''H<nowiki>'</nowiki>''.

The '''2-section''' (or '''clique graph''', '''representing graph''', '''primal graph''', '''Gaifman graph''') of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.

==Incidence matrix==
Let <math>V = \{v_1, v_2, ~\ldots, ~ v_n\}</math> and <math>E = \{e_1, e_2, ~ \ldots ~ e_m\}</math>. Every hypergraph has an <math>n \times m</math> [[incidence matrix]].

For an undirected hypergraph, <math>I = (b_{ij})</math> where
:<math>b_{ij} = \left\{ \begin{matrix} 1 & \mathrm{if} ~ v_i \in e_j \\ 0 & \mathrm{otherwise}. \end{matrix} \right.</math>
The [[transpose]] <math>I^t</math> of the [[incidence (geometry)|incidence]] matrix defines a hypergraph <math>H^* = (V^*,\ E^*)</math> called the '''dual''' of <math>H</math>, where <math>V^*</math> is an ''m''-element set and <math>E^*</math> is an ''n''-element set of subsets of <math>V^*</math>. For <math>v^*_j \in V^*</math> and <math>e^*_i \in E^*, ~ v^*_j \in e^*_i</math> [[if and only if]] <math>b_{ij} = 1</math>.

For a directed hypergraph, the heads and tails of each hyperedge <math>e_j</math> are denoted by <math>H(e_j)</math> and <math>T(e_j)</math> respectively.<ref name=gallo>{{cite journal |first1=G. |last1=Gallo |first2=G. |last2=Longo |first3=S. |last3=Pallottino |first4=S. |last4=Nguyen |title=Directed hypergraphs and applications |journal=Discrete Applied Mathematics |volume=42 |issue=2–3 |pages=177–201 |year=1993 |doi=10.1016/0166-218X(93)90045-P |doi-access=free }}</ref> <math>I = (b_{ij})</math> where
:<math>b_{ij} = \left\{ \begin{matrix} -1 & \mathrm{if} ~ v_i \in T(e_j) \\ 1 & \mathrm{if} ~ v_i \in H(e_j) \\ 0 & \mathrm{otherwise}. \end{matrix} \right.</math>

===Incidence graph===
A hypergraph ''H'' may be represented by a [[bipartite graph]] ''BG'' as follows: the sets ''X'' and ''E'' are the parts of ''BG'', and (''x<sub>1</sub>'',  ''e<sub>1</sub>'') are connected with an edge if and only if vertex ''x<sub>1</sub>'' is contained in edge ''e<sub>1</sub>'' in ''H''.

Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called [[incidence graph]].

== Adjacency matrix ==
A parallel for the adjacency matrix of a hypergraph can be drawn from the [[adjacency matrix]] of a graph. In the case of a graph, the adjacency matrix is a square matrix which indicates whether pairs of vertices are [[Neighbourhood (graph theory)|adjacent]]. Likewise, we can define the adjacency matrix <math>A = (a_{ij})</math> for a hypergraph in general where the hyperedges <math>e_{k \leq m}</math>have real weights <math>w_{e_{k}} \in \R</math> with 

<math>a_{ij} = \left\{ \begin{matrix} w_{e_{k}} & \mathrm{if} ~ (v_i, v_j) \in E \\ 0 & \mathrm{otherwise}. \end{matrix} \right.</math>

==Cycles==
In contrast with ordinary undirected graphs for which there is a single natural notion of [[cycle (graph theory)|cycles]] and [[Forest (graph theory)|acyclic graphs]]. For hypergraphs, there are multiple natural non-equivalent definitions of cycles which collapse to the ordinary notion of cycle when the graph case is considered.

===Berge cycles===
A first notion of cycle was introduced by [[Claude Berge]].<ref>{{cite book |first=Claude |last=Berge |title=Graphs and Hypergraphs |location=Amsterdam |publisher=North-Holland |year=1973 |isbn=0-7204-2450-X }}</ref> A '''Berge cycle''' in a hypergraph is an alternating sequence of distinct vertices and edges <math>(v_1, e_1, \dots , v_n, e_n)</math> where <math>v_i, v_{i+1}</math> are both in <math>e_i</math> for each <math>i \in [n]</math> (with indices taken modulo <math>n</math>).

Under this definition a hypergraph is '''acyclic''' if and only if its [[incidence graph]] (the [[bipartite graph]] defined above) is acyclic. Thus Berge-cyclicity can obviously be tested in [[linear time]] by an exploration of the incidence graph.

===Tight cycles===
This definition is particularly used for <math>k</math>-uniform hypergraphs, where all hyperedges are of size <math>k</math>. A '''tight cycle''' of length <math>n</math> in a hypergraph <math>H</math> is a sequence of distinct vertices <math>v_1,\dots, v_n</math> such that every consecutive <math>k</math>-tuple <math>\{v_i, \dots, v_{i+k-1}\}</math> (indices modulo <math>n</math>) forms a hyperedge in <math>H</math>. 
This notion was introduced by Katona and Kierstead<ref>{{cite journal | author-link1= Gyula O. H. Katona  | first1=G. | last1=Katona |first2=H. A.|last2=Kierstead| title= Hamiltonian chains in hypergraphs |journal=Journal of Graph Theory |volume=30 | issue=3 |pages=205–212 |year=1999 |doi=10.1002/(SICI)1097-0118(199903)30:3<205::AID-JGT5>3.0.CO;2-O |url=https://doi.org/10.1002/(SICI)1097-0118(199903)30:3<205::AID-JGT5>3.0.CO;2-O|url-access=subscription }}</ref> and has since garnered considerable attention, particularly in the study of Hamiltonicity in extremal combinatorics.<ref>{{cite book | first1=Y. | last1=Zhao | chapter=Recent advances on Dirac-type problems for hypergraphs |title=Recent Trends in Combinatorics | series=The IMA Volumes in Mathematics and its Applications |pages=145–165 |year=2016 | volume=159 |doi=10.1007/978-3-319-24298-9_6 | arxiv=1508.06170 | isbn=978-3-319-24296-5 }}</ref><ref>{{cite journal | author-link1=Daniela Kühn  | first1=D. | last1=Kühn |author-link2=Deryk Osthus |first2=D.|last2=Osthus| title=Hamilton cycles in graphs and hypergraphs: an extremal perspective |journal=Proceeding of the International Congress of Mathematicans, ICM  |pages=381–406 |year=2014 |isbn=9788961058070 |url=https://web.mat.bham.ac.uk/D.Osthus/icmsurvey4.pdf}}</ref> 

Rödl, Szemerédi, and Ruciński showed that every <math>n</math>-vertex <math>k</math>-uniform hypergraph <math>H</math> in which every <math>(k-1)</math>-subset of vertices is contained in at least <math>n/2 + o(n)</math> hyperedges contains a Hamilton cycle. 
This corresponds to an approximate hypergraph-extension of the celebrated [[Hamiltonian path#Bondy–Chvátal theorem| Dirac's theorem]] about Hamilton cycles in graphs.<ref>{{cite journal | author-link1= Vojtěch Rödl  | first1=V. | last1=Rödl |author-link2=Endre Szemerédi |first2=E.|last2=Szemerédi|first3=A. |last3=Ruciński |title=An approximate Dirac-type theorem for k-uniform hypergraphs |journal=Combinatorica |volume=28 |pages=229–260 |year=2008 | issue=2 |doi=10.1007/s00493-008-2295-z |url=https://doi.org/10.1007/s00493-008-2295-z|url-access=subscription }}</ref>

The maximum number of hyperedges in a (tightly) acyclic <math>k</math>-uniform hypergraph remains unknown. The best known bounds, obtained by Sudakov and Tomon,<ref>{{cite journal | author-link1= Benny Sudakov  | first1=B. | last1=Sudakov |first2=I.|last2=Tomon |title=The Extremal Number of Tight Cycles |journal=International Mathematics Research Notices |volume=2022 |pages=9663–9684 |year=2022 | issue=13 |doi=10.1093/imrn/rnaa396 |url=https://doi.org/10.1093/imrn/rnaa396|arxiv=2009.00528 }}</ref> show that every <math>n</math>-vertex <math>k</math>-uniform hypergraph with at least <math>n^{k-1+o(1)}</math> hyperedges must contain a tight cycle. This bound is optimal up to the <math>o(1)</math> error term.

An '''<math>\ell</math>-cycle''' generalizes the notion of a tight cycle.
It consists in a sequence of vertices <math>v_1,\dots, v_n </math> and hyperedges <math>e_1,\dots, e_t</math> where each <math>e_i</math> consists of <math>k</math> consecutive vertices in the sequence and <math>|e_i\cap e_{i+1}|=\ell</math> for every <math>1\leq i\leq t</math>. Since every edge of the <math>\ell</math>-cycle contains exactly <math>k-\ell</math> vertices which are not contained in the previous edge, <math>n</math> must be divisible by <math>k-\ell</math>. Note that <math>\ell=k-1</math> recovers the definition of a tight cycle.

===α-acyclicity===
The definition of Berge-acyclicity might seem to be very restrictive: for instance, if a hypergraph has some pair <math>v \neq v'</math> of vertices and some pair <math>f \neq f'</math> of hyperedges such that <math>v, v' \in f</math> and <math>v, v' \in f'</math>, then it is Berge-cyclic. 

We can define a weaker notion of hypergraph acyclicity,<ref name=database>{{cite journal |first1=C. |last1=Beeri |author-link2=Ronald Fagin |first2=R. |last2=Fagin |first3=D. |last3=Maier |author-link4=Mihalis Yannakakis |first4=M. |last4=Yannakakis |title=On the Desirability of Acyclic Database Schemes |journal=Journal of the ACM |volume=30 |issue=3 |pages=479–513 |year=1983 |doi=10.1145/2402.322389 |s2cid=2418740 |url=http://cse.unl.edu/~choueiry/Documents/jacm83a.pdf |access-date=2021-01-03 |archive-date=2021-04-21 |archive-url=https://web.archive.org/web/20210421203326/http://cse.unl.edu/~choueiry/Documents/jacm83a.pdf |url-status=live }}</ref> later termed α-acyclicity. This notion of acyclicity is equivalent to the hypergraph being conformal (every clique of the primal graph is covered by some hyperedge) and its primal graph being [[chordal graph|chordal]]; it is also equivalent to reducibility to the empty graph through the [[GYO algorithm]]<ref>{{cite journal |first1=C. T. |last1=Yu |first2=M. Z. |last2=Özsoyoğlu |url=https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf |title=An algorithm for tree-query membership of a distributed query |journal=Proc. IEEE COMPSAC |pages=306–312 |year=1979 |doi=10.1109/CMPSAC.1979.762509 |access-date=2018-09-02 |archive-date=2018-09-02 |archive-url=https://web.archive.org/web/20180902151638/https://www.computer.org/csdl/proceedings/cmpsac/1979/9999/00/00762509.pdf |url-status=live }}</ref><ref name="graham1979universal">{{cite journal |first=M. H. |last=Graham |title=On the universal relation |journal=Technical Report |publisher=University of Toronto |location=Toronto, Ontario, Canada |year=1979 }}</ref> (also known as Graham's algorithm), a [[confluence (abstract rewriting)|confluent]] iterative process which removes hyperedges using a generalized definition of [[ear (graph theory)|ears]]. In the domain of [[database theory]], it is known that a [[database schema]] enjoys certain desirable properties if its underlying hypergraph is α-acyclic.<ref>{{cite book |author-link=Serge Abiteboul |first1=S. |last1=Abiteboul |author-link2=Richard B. Hull |first2=R. B. |last2=Hull |author-link3=Victor Vianu |first3=V. |last3=Vianu |title=Foundations of Databases |publisher=Addison-Wesley |year=1995 |isbn=0-201-53771-0 }}</ref> Besides, α-acyclicity is also related to the expressiveness of the [[guarded fragment]] of [[first-order logic]].

We can test in [[linear time]] if a hypergraph is α-acyclic.<ref>{{cite journal |author-link=Robert Tarjan |first1=R. E. |last1=Tarjan |author-link2=Mihalis Yannakakis |first2=M. |last2=Yannakakis |title=Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs |journal=SIAM Journal on Computing |volume=13 |issue=3 |pages=566–579 |year=1984 |doi=10.1137/0213035 }}</ref>

Note that α-acyclicity has the counter-intuitive property that adding hyperedges to an α-cyclic hypergraph may make it α-acyclic (for instance, adding a hyperedge containing all vertices of the hypergraph will always make it α-acyclic). Motivated in part by this perceived shortcoming, [[Ronald Fagin]]<ref name="fagin1983degrees">{{cite journal |first=Ronald |last=Fagin |title=Degrees of Acyclicity for Hypergraphs and Relational Database Schemes |journal=Journal of the ACM |year=1983 |volume=30 |issue=3 |pages=514–550 |doi=10.1145/2402.322390 |s2cid=597990 |doi-access=free }}</ref> defined the stronger notions of β-acyclicity and γ-acyclicity. We can state β-acyclicity as the requirement that all subhypergraphs of the hypergraph are α-acyclic, which is equivalent<ref name="fagin1983degrees" /> to an earlier definition by Graham.<ref name="graham1979universal" /> The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to [[Bachman diagram]]s. Both β-acyclicity and γ-acyclicity can be tested in [[PTIME|polynomial time]].

Those four notions of acyclicity are comparable: γ-acyclicity which implies β-acyclicity which implies α-acyclicity. Moreover, Berge-acyclicity implies all of them. None of the reverse implications hold including the Berge one. In other words, these four notions are different.<ref name="fagin1983degrees" />

==Isomorphism, symmetry, and equality==
A hypergraph [[homomorphism]] is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge.

A hypergraph <math>H=(X,E)</math> is ''isomorphic'' to a hypergraph <math>G=(Y,F)</math>,  written as <math>H \simeq G</math> if there exists a [[bijection]]

:<math>\phi:X \to Y</math>

and a [[permutation]] <math>\pi</math> of <math>I</math> such that

:<math>\phi(e_i) = f_{\pi(i)}</math>

The bijection <math>\phi</math> is then called the [[isomorphism]] of the graphs.  Note that

:<math>H \simeq G</math> if and only if <math>H^* \simeq G^*</math>.

When the edges of a hypergraph are explicitly labeled, one has the additional notion of ''strong isomorphism''. One says that <math>H</math> is ''strongly isomorphic'' to <math>G</math> if the permutation is the identity. One then writes <math>H \cong G</math>.  Note that all strongly isomorphic graphs are isomorphic, but not vice versa.

When the vertices of a hypergraph are explicitly labeled, one has the notions of ''equivalence'', and also of ''equality''. One says that <math>H</math> is ''equivalent'' to <math>G</math>, and writes <math>H\equiv G</math> if the isomorphism <math>\phi</math> has

:<math>\phi(x_n) = y_n</math>

and

:<math>\phi(e_i) = f_{\pi(i)}</math>

Note that

:<math>H\equiv G</math> if and only if <math>H^* \cong G^*</math>

If, in addition, the permutation <math>\pi</math> is the identity, one says that <math>H</math> equals <math>G</math>, and writes <math>H=G</math>.  Note that, with this definition of equality, graphs are self-dual:

:<math>\left(H^*\right) ^* = H</math>

A hypergraph [[automorphism]] is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph ''H'' (= (''X'',&nbsp;''E'')) is a [[group (mathematics)|group]] under composition, called the [[automorphism group]] of the hypergraph and written Aut(''H'').

===Examples===
Consider the hypergraph <math>H</math> with edges
:<math>H = \lbrace
e_1 = \lbrace a,b \rbrace,
e_2 = \lbrace b,c \rbrace,
e_3 = \lbrace c,d \rbrace,
e_4 = \lbrace d,a \rbrace,
e_5 = \lbrace b,d \rbrace,
e_6 = \lbrace a,c \rbrace
\rbrace</math>
and
:<math>G = \lbrace
f_1 = \lbrace \alpha,\beta \rbrace,
f_2 = \lbrace \beta,\gamma \rbrace,
f_3 = \lbrace \gamma,\delta \rbrace,
f_4 = \lbrace \delta,\alpha \rbrace,
f_5 = \lbrace \alpha,\gamma \rbrace,
f_6 = \lbrace \beta,\delta \rbrace
\rbrace</math>

Then clearly <math>H</math> and <math>G</math> are isomorphic (with <math>\phi(a)=\alpha</math>, ''etc.''), but they are not strongly isomorphic. So, for example, in <math>H</math>, vertex <math>a</math> meets edges 1, 4 and 6, so that,

:<math>e_1 \cap e_4 \cap e_6 = \lbrace a\rbrace</math>

In graph <math>G</math>, there does not exist any vertex that meets edges 1, 4 and 6:

:<math>f_1 \cap f_4 \cap f_6 = \varnothing</math>

In this example, <math>H</math> and <math>G</math> are equivalent, <math>H\equiv G</math>, and the duals are strongly isomorphic: <math>H^*\cong G^*</math>.

===Symmetry===
The ''{{visible anchor|rank}}'' <math>r(H)</math> of a hypergraph <math>H</math> is the maximum cardinality of any of the edges in the hypergraph.  If all edges have the same cardinality ''k'', the hypergraph is said to be ''uniform'' or ''k-uniform'', or is called a ''k-hypergraph''.  A graph is just a 2-uniform hypergraph.

The degree ''d(v)'' of a vertex ''v'' is the number of edges that contain it. ''H'' is ''k-regular'' if every vertex has degree ''k''.

The dual of a uniform hypergraph is regular and vice versa.

Two vertices ''x'' and ''y'' of ''H'' are called ''symmetric'' if there exists an automorphism such that <math>\phi(x)=y</math>.  Two edges <math>e_i</math> and <math>e_j</math> are said to be  ''symmetric'' if there exists an automorphism such that <math>\phi(e_i)=e_j</math>.

A hypergraph is said to be ''vertex-transitive'' (or ''vertex-symmetric'') if all of its vertices are symmetric. Similarly, a hypergraph is ''edge-transitive'' if all edges are symmetric. If a hypergraph is both edge- and vertex-symmetric, then the hypergraph is simply ''transitive''.

Because of hypergraph duality, the study of edge-transitivity is identical to the study of vertex-transitivity.

==Partitions==
A partition theorem due to E. Dauber<ref>{{cite book |first=F. |last=Harary |title=Graph Theory |url=https://books.google.com/books?id=AmhQDwAAQBAJ |date=2018 |publisher=CRC Press |isbn=978-0-429-96231-8 |orig-year=1969 |page=172 |quote=We next state a theorem due to Elayne Dauber whose corollaries describe properties of line-symmetric graphs. Note the obvious but important observation that every line-symmetric graph is line-regular. |access-date=2021-06-12 |archive-date=2023-02-04 |archive-url=https://web.archive.org/web/20230204155708/https://books.google.com/books?id=AmhQDwAAQBAJ |url-status=live }}</ref> states that, for an edge-transitive hypergraph <math>H=(X,E)</math>, there exists a [[partition of a set|partition]]

:<math>(X_1, X_2,\cdots,X_K)</math>

of the vertex set <math>X</math> such that the subhypergraph <math>H_{X_k}</math> generated by <math>X_k</math> is transitive for each <math>1\le k \le K</math>, and such that

:<math>\sum_{k=1}^K r\left(H_{X_k} \right) = r(H)</math>

where <math>r(H)</math> is the rank of ''H''.

As a corollary, an edge-transitive hypergraph that is not vertex-transitive is bicolorable.

[[Graph partitioning]] (and in particular, hypergraph partitioning) has many applications to IC design<ref>{{Citation |title=Multilevel hypergraph partitioning: applications in VLSI domain |author=Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. |journal=IEEE Transactions on Very Large Scale Integration (VLSI) Systems |date=March 1999 |volume=7 |issue=1 |pages=69–79 |doi=10.1109/92.748202 |postscript=.|citeseerx=10.1.1.553.2367 }}</ref> and [[parallel computing]].<ref>{{Citation |doi=10.1016/S0167-8191(00)00048-X |title=Graph partitioning models for parallel computing |author=Hendrickson, B., Kolda, T.G. |journal=Parallel Computing |year=2000 |volume=26 |issue=12 |pages=1519–1545 |osti=4179 |postscript=. |url=https://digital.library.unt.edu/ark:/67531/metadc684945/ |type=Submitted manuscript |access-date=2018-10-13 |archive-date=2021-01-26 |archive-url=https://web.archive.org/web/20210126021713/https://digital.library.unt.edu/ark:/67531/metadc684945/ |url-status=live }}</ref><ref>{{Cite conference |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=A Hypergraph Model for Mapping Repeated Sparse Matrix–Vector Product Computations onto Multicomputers |conference=Proc. International Conference on Hi Performance Computing (HiPC'95) |year=1995}}</ref><ref>{{Citation |last1=Catalyurek |first1=U.V. |last2=Aykanat |first2=C. |title=Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication |journal=IEEE Transactions on Parallel and Distributed Systems |volume=10 |issue=7 |pages=673–693 |year=1999|doi=10.1109/71.780863 |postscript=. |citeseerx=10.1.1.67.2498 }}</ref> Efficient and scalable [[Graph partition|hypergraph partitioning algorithms]] are also important for processing large scale hypergraphs in machine learning tasks.<ref name=hyperx>{{cite book|last1=Huang|first1=Jin|last2=Zhang|first2=Rui|last3=Yu|first3=Jeffrey Xu|title=2015 IEEE International Conference on Data Mining |chapter=Scalable Hypergraph Learning and Processing |year=2015|url=https://www.ruizhang.info/publications/Icdm2015-hyperx.pdf|pages=775–780|doi=10.1109/ICDM.2015.33|isbn=978-1-4673-9504-5|s2cid=5130573|access-date=2021-01-08|archive-date=2021-01-26|archive-url=https://web.archive.org/web/20210126233924/https://ruizhang.info/publications/Icdm2015-hyperx.pdf|url-status=live}}</ref>

==Further generalizations==
{{Unreferenced section|date=January 2021}}
One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ''ad infinitum''. In essence, every edge is just an internal node of a tree or [[directed acyclic graph]], and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout [[computer science]] and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of [[term algebra]]; edges correspond to [[term (logic)|terms]] and vertices correspond to constants or variables.

For such a hypergraph, set membership then provides an ordering, but the ordering is neither a [[partial order]] nor a [[preorder]], since it is not transitive. The graph corresponding to the Levi graph of this generalization is a [[directed acyclic graph]]. Consider, for example, the generalized hypergraph whose vertex set is <math>V= \{a,b\}</math> and whose edges are <math>e_1=\{a,b\}</math> and <math>e_2=\{a,e_1\}</math>. Then, although <math>b\in e_1</math> and <math>e_1\in e_2</math>, it is not true that <math>b\in e_2</math>.  However, the [[transitive closure]] of set membership for such hypergraphs does induce a [[partial order]], and "flattens" the hypergraph into a [[partially ordered set]].

Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges <math>e_1</math> and <math>e_2</math>, and zero vertices, so that <math>e_1 = \{e_2\}</math> and <math>e_2 = \{e_1\}</math>. As this loop is infinitely recursive, sets that are the edges violate the [[axiom of foundation]].  In particular, there is no transitive closure of set membership for such hypergraphs.  Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer [[Bipartite graph|bipartite]], but is rather just some general [[directed graph]].

The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the [[incidence matrix]] is simply

:<math>\left[ \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right].</math>

==See also==
{{Commons category|Hypergraphs}}
{{cols}}
*{{annotated link|BF-graph}}
*{{annotated link|Combinatorial design}}
*{{annotated link|Factor graph}}
*{{annotated link|Greedoid}}
*{{annotated link|Incidence structure}}
*{{annotated link|Multigraph}}
*{{annotated link|P system}}
*{{annotated link|Sparse matrix–vector multiplication}}
*{{annotated link|Petri Net}}
{{colend}}

==Notes==
{{Reflist}}

==References==
* {{cite book |first=Claude |last=Berge |title=Hypergraphs: Combinatorics of Finite Sets |url=https://books.google.com/books?id=jEyfse-EKf8C |date=1984 |publisher=Elsevier |isbn=978-0-08-088023-5}}
* {{cite book |first1=C. |last1=Berge |first2=D. |last2=Ray-Chaudhuri |title=Hypergraph Seminar: Ohio State University, 1972 |url=https://books.google.com/books?id=1Jt7CwAAQBAJ&pg=PP3 |date=2006 |publisher=Springer |isbn=978-3-540-37803-7 |series=Lecture Notes in Mathematics |volume=411}}
* {{springer|title=Hypergraph|id=p/h048470}}
* {{cite book |first=Alain |last=Bretto |title=Hypergraph Theory: An Introduction |url=https://books.google.com/books?id=lb5DAAAAQBAJ&pg=PP1 |date=2013 |publisher=Springer |isbn=978-3-319-00080-0 }}
* {{cite book |first=Vitaly I. |last=Voloshin |title=Coloring Mixed Hypergraphs: Theory, Algorithms and Applications: Theory, Algorithms, and Applications |url=https://books.google.com/books?id=Qr8jDwAAQBAJ |year=2002 |publisher=American Mathematical Society |isbn=978-0-8218-2812-0 |series=Fields Institute Monographs |volume=17}}
* {{cite book |first=Vitaly I. |last=Voloshin |title=Introduction to Graph and Hypergraph Theory |url=https://books.google.com/books?id=IvVIAQAACAAJ |year=2009 |publisher=Nova Science |isbn=978-1-61470-112-5}}
* {{PlanetMath attribution|urlname=hypergraph|title=hypergraph}}

==External links==
* [https://www.aviz.fr/paohvis PAOHVis]: open-source PAOHVis system for visualizing dynamic hypergraphs.

{{Graph representations}}
{{Incidence structures}}
{{Authority control}}

[[Category:Hypergraphs]]
[[Category:Extensions_and_generalizations_of_graphs]]
[[Category:Families of sets]]

[[de:Graph (Graphentheorie)#Hypergraph]]
[[Category:Mathematical structures]]