Hypergraph

Generalizations of concepts from graphs

Many theorems 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.

Hypergraph drawing

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. 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 curves that enclose sets of points.

In another style of hypergraph visualization, the subdivision model of hypergraph drawing, 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ⁿ − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition of planar graphs, it is NP-complete to determine whether a hypergraph has a planar subdivision drawing, 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.

An alternative representation of the hypergraph called 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 ${\displaystyle \{1,2,3,...,\lambda \}}$ 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.

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.
• ${\displaystyle d}$-regular - every vertex has degree ${\displaystyle d}$, i.e., contained in exactly ${\displaystyle d}$ 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 and balanced.
• ${\displaystyle k}$-uniform - each hyperedge contains precisely ${\displaystyle k}$ vertices.
• ${\displaystyle k}$-partite - the vertices are partitioned into ${\displaystyle k}$ parts, and each hyperedge contains precisely one vertex of each type.
  • Every ${\displaystyle k}$-partite hypergraph (for ${\displaystyle k\ge 2}$) is both ${\displaystyle k}$-uniform and bipartite (and 2-colorable).
• Reduced: 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.
• Connected: for all ${\displaystyle S\subseteq X}$ with ${\displaystyle \mathrm{\varnothing }\ne S\ne X}$ there is ${\displaystyle e\in E}$ that meets both ${\displaystyle S}$ and ${\displaystyle X\setminus S}$. A hypergraph that is not connected is called disconnected.

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 ${\displaystyle H=(X,E)}$ be the hypergraph consisting of vertices

${\displaystyle X=\{x_i\mid i\in I_v\},}$

and having edge set

${\displaystyle E=\{e_i\mid i\in I_e,e_i\subseteq X,e_i\ne \mathrm{\varnothing }\},}$

where ${\displaystyle I_v}$ and ${\displaystyle I_e}$ are the index sets of the vertices and edges respectively.

A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph ${\displaystyle H_A}$ induced by ${\displaystyle A\subseteq X}$ is defined as

${\displaystyle H_A=\left(A,\{e\cap A\mid e\in E,e\cap A\ne \mathrm{\varnothing }\}\right).}$

An alternative term is the restriction of H to A.

A connected component of ${\displaystyle H}$ is a maximal connected subhypergraph of ${\displaystyle H}$, that is, a subhypergraph ${\displaystyle H_A}$ of ${\displaystyle H}$ induced by ${\displaystyle A}$ such that ${\displaystyle H_A}$ is connected and no subhypergraph ${\displaystyle H_{A^{\prime }}}$ with ${\displaystyle A⊊A^{\prime }}$ is connected.

An extension of a subhypergraph is a hypergraph where each hyperedge of ${\displaystyle H}$ which is partially contained in the subhypergraph ${\displaystyle H_A}$ is fully contained in the extension ${\displaystyle Ex(H_A)}$. Formally

${\displaystyle Ex(H_A)=(A\cup A^{\prime },E^{\prime })}$ with ${\displaystyle A^{\prime }=\bigcup _{e\in E}e\setminus A}$ and ${\displaystyle E^{\prime }=\{e\in E\mid e\subseteq (A\cup A^{\prime })\}}$.

The partial hypergraph is a hypergraph with some edges removed. Given a subset ${\displaystyle J\subset I_e}$ of the edge index set, the partial hypergraph generated by ${\displaystyle J}$ is the hypergraph

${\displaystyle \left(X,\{e_i\mid i\in J\}\right).}$

Given a subset ${\displaystyle A\subseteq X}$, the section hypergraph is the partial hypergraph

${\displaystyle H\times A=\left(A,\{e_i\mid i\in I_e,e_i\subseteq A\}\right).}$

The dual ${\displaystyle H^{\ast }}$ of ${\displaystyle H}$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by ${\displaystyle \{e_i\}}$ and whose edges are given by ${\displaystyle \{X_m\}}$ where

${\displaystyle X_m=\{e_i\mid x_m\in e_i\}.}$

When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an involution, i.e.,

${\displaystyle {\left(H^{\ast }\right)}^{\ast }=H.}$

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 induces a connected subgraph in G. For a disconnected hypergraph H, G is a host graph if there is a bijection between the connected components of G and of H, such that each connected component G' of G is a host of the corresponding H'.

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 ${\displaystyle V=\{v_1,v_2,\dots ,v_n\}}$ and ${\displaystyle E=\{e_1,e_2,\dots e_m\}}$. Every hypergraph has an ${\displaystyle n\times m}$ incidence matrix.

For an undirected hypergraph, ${\displaystyle I=(b_{ij})}$ where

${\displaystyle b_{ij}=\{\begin{array}{cc}1& \mathrm{i}\mathrm{f}{v}_i\in e_j\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}}$

The transpose ${\displaystyle I^t}$ of the incidence matrix defines a hypergraph ${\displaystyle H^{\ast }=(V^{\ast },E^{\ast })}$ called the dual of ${\displaystyle H}$, where ${\displaystyle V^{\ast }}$ is an m-element set and ${\displaystyle E^{\ast }}$ is an n-element set of subsets of ${\displaystyle V^{\ast }}$. For ${\displaystyle v_j^{\ast }\in V^{\ast }}$ and ${\displaystyle e_i^{\ast }\in E^{\ast },v_j^{\ast }\in e_i^{\ast }}$ if and only if ${\displaystyle b_{ij}=1}$.

For a directed hypergraph, the heads and tails of each hyperedge ${\displaystyle e_j}$ are denoted by ${\displaystyle H(e_j)}$ and ${\displaystyle T(e_j)}$ respectively. ${\displaystyle I=(b_{ij})}$ where

${\displaystyle b_{ij}=\{\begin{array}{cc}-1& \mathrm{i}\mathrm{f}{v}_i\in T(e_j)\\ 1& \mathrm{i}\mathrm{f}{v}_i\in H(e_j)\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}}$

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₁, e₁) are connected with an edge if and only if vertex x₁ is contained in edge e₁ 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 adjacent. Likewise, we can define the adjacency matrix ${\displaystyle A=(a_{ij})}$ for a hypergraph in general where the hyperedges ${\displaystyle e_{k\le m}}$have real weights ${\displaystyle w_{e_k}\in \mathbb{R}}$ with

${\displaystyle a_{ij}=\{\begin{array}{cc}{w}_{e_k}& \mathrm{i}\mathrm{f}(v_i,v_j)\in E\\ 0& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}}$

Cycles

In contrast with ordinary undirected graphs for which there is a single natural notion of cycles and 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. A Berge cycle in a hypergraph is an alternating sequence of distinct vertices and edges ${\displaystyle (v_1,e_1,\dots ,v_n,e_n)}$, where ${\displaystyle n\ge 2}$ and ${\displaystyle v_i,v_{i+1}}$ are both in ${\displaystyle e_i}$ for each ${\displaystyle i\in [n]}$ (with indices taken modulo ${\displaystyle n}$).

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 ${\displaystyle k}$-uniform hypergraphs, where all hyperedges are of size ${\displaystyle k}$. A tight cycle of length ${\displaystyle n}$ in a hypergraph ${\displaystyle H}$ is a sequence of distinct vertices ${\displaystyle v_1,\dots ,v_n}$ such that every consecutive ${\displaystyle k}$-tuple ${\displaystyle \{v_i,\dots ,v_{i+k-1}\}}$ (indices modulo ${\displaystyle n}$) forms a hyperedge in ${\displaystyle H}$. This notion was introduced by Katona and Kierstead and has since garnered considerable attention, particularly in the study of Hamiltonicity in extremal combinatorics.

Rödl, Szemerédi, and Ruciński showed that every ${\displaystyle n}$-vertex ${\displaystyle k}$-uniform hypergraph ${\displaystyle H}$ in which every ${\displaystyle (k-1)}$-subset of vertices is contained in at least ${\displaystyle n/2+o(n)}$ hyperedges contains a Hamilton cycle. This corresponds to an approximate hypergraph-extension of the celebrated Dirac's theorem about Hamilton cycles in graphs.

The maximum number of hyperedges in a (tightly) acyclic ${\displaystyle k}$-uniform hypergraph remains unknown. For ${\displaystyle k=2}$, it is well known that this number is ${\displaystyle n-1}$. For ${\displaystyle k\ge 3}$, the best known bounds, due to Janzer and Letzter, show that this maximum number is between ${\displaystyle \mathrm{\Omega }(n^{k-1}\log n/\log \log n)}$ and ${\displaystyle O(n^{k-1}(\log n{)}^5)}$. The bounds are optimal up to a poly-logarithmic factor.

An ${\displaystyle l}$-cycle generalizes the notion of a tight cycle. It consists in a sequence of vertices ${\displaystyle v_1,\dots ,v_n}$ and hyperedges ${\displaystyle e_1,\dots ,e_t}$ where each ${\displaystyle e_i}$ consists of ${\displaystyle k}$ consecutive vertices in the sequence and ${\displaystyle |e_i\cap e_{i+1}|=l}$ for every ${\displaystyle 1\le i\le t}$. Since every edge of the ${\displaystyle l}$-cycle contains exactly ${\displaystyle k-l}$ vertices which are not contained in the previous edge, ${\displaystyle n}$ must be divisible by ${\displaystyle k-l}$. Note that ${\displaystyle l=k-1}$ 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 ${\displaystyle v\ne v^{\prime }}$ of vertices and some pair ${\displaystyle f\ne f^{\prime }}$ of hyperedges such that ${\displaystyle v,v^{\prime }\in f}$ and ${\displaystyle v,v^{\prime }\in f^{\prime }}$, then it is Berge-cyclic.

We can define a weaker notion of hypergraph acyclicity, 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; it is also equivalent to reducibility to the empty graph through the GYO algorithm (also known as Graham's algorithm), a confluent iterative process which removes hyperedges using a generalized definition of ears. In the domain of database theory, it is known that a database schema enjoys certain desirable properties if its underlying hypergraph is α-acyclic. 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.

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 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 to an earlier definition by Graham. The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to Bachman diagrams. Both β-acyclicity and γ-acyclicity can be tested in 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.

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 ${\displaystyle H=(X,E)}$ is isomorphic to a hypergraph ${\displaystyle G=(Y,F)}$, written as ${\displaystyle H\simeq G}$ if there exists a bijection

${\displaystyle \varphi :X\to Y}$

and a permutation ${\displaystyle \pi }$ of ${\displaystyle I}$ such that

${\displaystyle \varphi (e_i)=f_{\pi (i)}}$

The bijection ${\displaystyle \varphi }$ is then called the isomorphism of the graphs. Note that

${\displaystyle H\simeq G}$ if and only if ${\displaystyle H^{\ast }\simeq G^{\ast }}$.

When the edges of a hypergraph are explicitly labeled, one has the additional notion of strong isomorphism. One says that ${\displaystyle H}$ is strongly isomorphic to ${\displaystyle G}$ if the permutation is the identity. One then writes ${\displaystyle H\cong G}$. 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 ${\displaystyle H}$ is equivalent to ${\displaystyle G}$, and writes ${\displaystyle H\equiv G}$ if the isomorphism ${\displaystyle \varphi }$ has

${\displaystyle \varphi (x_n)=y_n}$

and

${\displaystyle \varphi (e_i)=f_{\pi (i)}}$

Note that

${\displaystyle H\equiv G}$ if and only if ${\displaystyle H^{\ast }\cong G^{\ast }}$

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

${\displaystyle {\left(H^{\ast }\right)}^{\ast }=H}$

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, E)) is a group under composition, called the automorphism group of the hypergraph and written Aut(H).

Examples

Consider the hypergraph ${\displaystyle H}$ with edges

${\displaystyle H=\{e_1=\{a,b\},e_2=\{b,c\},e_3=\{c,d\},e_4=\{d,a\},e_5=\{b,d\},e_6=\{a,c\}\}}$

and

${\displaystyle G=\{f_1=\{\alpha ,\beta \},f_2=\{\beta ,\gamma \},f_3=\{\gamma ,\delta \},f_4=\{\delta ,\alpha \},f_5=\{\alpha ,\gamma \},f_6=\{\beta ,\delta \}\}}$

Then clearly ${\displaystyle H}$ and ${\displaystyle G}$ are isomorphic (with ${\displaystyle \varphi (a)=\alpha }$, etc.), but they are not strongly isomorphic. So, for example, in ${\displaystyle H}$, vertex ${\displaystyle a}$ meets edges 1, 4 and 6, so that,

${\displaystyle e_1\cap e_4\cap e_6=\{a\}}$

In graph ${\displaystyle G}$, there does not exist any vertex that meets edges 1, 4 and 6:

${\displaystyle f_1\cap f_4\cap f_6=\varnothing }$

In this example, ${\displaystyle H}$ and ${\displaystyle G}$ are equivalent, ${\displaystyle H\equiv G}$, and the duals are strongly isomorphic: ${\displaystyle H^{\ast }\cong G^{\ast }}$.

Symmetry

The rank ${\displaystyle r(H)}$ of a hypergraph ${\displaystyle H}$ 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 ${\displaystyle \varphi (x)=y}$. Two edges ${\displaystyle e_i}$ and ${\displaystyle e_j}$ are said to be symmetric if there exists an automorphism such that ${\displaystyle \varphi (e_i)=e_j}$.

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 states that, for an edge-transitive hypergraph ${\displaystyle H=(X,E)}$, there exists a partition

${\displaystyle (X_1,X_2,\cdots ,X_K)}$

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

${\displaystyle \sum _{k=1}^{K}r\left(H_{X_k}\right)=r(H)}$

where ${\displaystyle r(H)}$ 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 and parallel computing. Efficient and scalable hypergraph partitioning algorithms are also important for processing large scale hypergraphs in machine learning tasks.

Further generalizations

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 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 ${\displaystyle V=\{a,b\}}$ and whose edges are ${\displaystyle e_1=\{a,b\}}$ and ${\displaystyle e_2=\{a,e_1\}}$. Then, although ${\displaystyle b\in e_1}$ and ${\displaystyle e_1\in e_2}$, it is not true that ${\displaystyle b\in e_2}$. 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 ${\displaystyle e_1}$ and ${\displaystyle e_2}$, and zero vertices, so that ${\displaystyle e_1=\{e_2\}}$ and ${\displaystyle e_2=\{e_1\}}$. 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, 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

${\displaystyle \left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]}$.