# Chapter 24. Hypergraphs # Chapter 24. Hypergraphs A hypergraph is a generalization of a graph in which an edge may join any number of vertices. In an ordinary graph, each edge joins two vertices. In a hypergraph, an edge may contain one vertex, two vertices, three vertices, or more. Such an edge is called a hyperedge. Hypergraphs are useful when relations involve groups rather than pairs. A committee contains several members. A database record may relate several fields. A chemical reaction may involve several compounds. A document may contain many terms. A transaction may contain many items. These are not naturally binary relations. They are relations among sets of objects. ## 24.1 Definition A hypergraph is an ordered pair $$ H = (V,E), $$ where \(V\) is a set of vertices and \(E\) is a set of hyperedges. Each hyperedge is a subset of \(V\): $$ e \subseteq V. $$ Thus $$ E \subseteq \mathcal{P}(V), $$ where \(\mathcal{P}(V)\) denotes the power set of \(V\). Many authors exclude the empty set as a hyperedge. Under that convention, $$ e \neq \varnothing $$ for every $$ e \in E. $$ Unless stated otherwise, this chapter assumes that hyperedges are nonempty subsets of \(V\). An ordinary undirected graph is a special case of a hypergraph in which every edge contains exactly two vertices. In this sense, a graph is a \(2\)-uniform hypergraph. ## 24.2 First Example Let $$ V = \{a,b,c,d,e\}. $$ Define $$ E = \{ \{a,b,c\}, \{b,d\}, \{a,d,e\}, \{c\} \}. $$ Then $$ H=(V,E) $$ is a hypergraph. The hyperedge $$ \{a,b,c\} $$ joins three vertices. The hyperedge $$ \{b,d\} $$ joins two vertices. The hyperedge $$ \{c\} $$ contains one vertex. This example cannot be represented faithfully as an ordinary graph without adding extra conventions, because the relation among \(a,b,c\) is one three-way relation, not merely three pairwise edges. ## 24.3 Hyperedges A hyperedge is a subset of the vertex set. If $$ e = \{v_1,v_2,\ldots,v_k\}, $$ then \(e\) is incident with each of the vertices $$ v_1,v_2,\ldots,v_k. $$ The number of vertices in a hyperedge is its cardinality: $$ |e|. $$ A hyperedge of cardinality \(1\) is sometimes called a loop or singleton edge. A hyperedge of cardinality \(2\) behaves like an ordinary graph edge. A hyperedge of cardinality greater than \(2\) represents a genuine higher-order relation. For example, $$ \{u,v,w,x\} $$ is a hyperedge of size \(4\). It records one relation involving all four vertices. ## 24.4 Rank and Uniformity The rank of a hypergraph is the maximum size of its hyperedges: $$ r(H) = \max_{e \in E} |e|. $$ A hypergraph is \(k\)-uniform if every hyperedge has exactly \(k\) vertices: $$ |e| = k $$ for every $$ e \in E. $$ Thus an ordinary graph is a \(2\)-uniform hypergraph. A \(3\)-uniform hypergraph has only hyperedges of size \(3\). For example, if $$ E = \{ \{a,b,c\}, \{a,d,e\}, \{b,c,e\} \}, $$ then \(H\) is \(3\)-uniform. If $$ E = \{ \{a,b\}, \{b,c,d\}, \{a,d,e,f\} \}, $$ then \(H\) has rank \(4\), but it is not uniform. Uniform hypergraphs are important in extremal combinatorics because they fix the size of each relation. ## 24.5 Degree of a Vertex The degree of a vertex in a hypergraph counts the number of hyperedges that contain it. For a vertex \(v \in V\), define $$ \deg(v) = |\{e \in E : v \in e\}|. $$ For example, let $$ E = \{ \{a,b,c\}, \{a,d\}, \{a,c,e\}, \{b,e\} \}. $$ Then \(a\) belongs to three hyperedges: $$ \{a,b,c\},\qquad \{a,d\},\qquad \{a,c,e\}. $$ Therefore $$ \deg(a)=3. $$ A hypergraph is \(d\)-regular if every vertex has degree \(d\). ## 24.6 Incidence Incidence is the basic relation between vertices and hyperedges. A vertex \(v\) is incident with a hyperedge \(e\) if $$ v \in e. $$ This relation may be represented by an incidence matrix. Let $$ V=\{v_1,\ldots,v_n\} $$ and $$ E=\{e_1,\ldots,e_m\}. $$ The incidence matrix of \(H\) is the \(n \times m\) matrix \(B\) defined by $$ B_{ij} = \begin{cases} 1, & \text{if } v_i \in e_j, \\ 0, & \text{otherwise}. \end{cases} $$ Rows correspond to vertices. Columns correspond to hyperedges. For ordinary graphs, each column of the incidence matrix usually has two nonzero entries. For hypergraphs, a column may have any positive number of nonzero entries. ## 24.7 Example of an Incidence Matrix Let $$ V = \{a,b,c,d\} $$ and $$ E = \{e_1,e_2,e_3\}, $$ where $$ e_1=\{a,b,c\}, \qquad e_2=\{b,d\}, \qquad e_3=\{a,d\}. $$ Using the vertex order \(a,b,c,d\), the incidence matrix is $$ B = \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix}. $$ The first column has three \(1\)'s because \(e_1\) contains \(a,b,c\). The second column has two \(1\)'s because \(e_2\) contains \(b,d\). The third column has two \(1\)'s because \(e_3\) contains \(a,d\). The row sum gives the degree of the corresponding vertex. The column sum gives the size of the corresponding hyperedge. ## 24.8 Hypergraphs and Bipartite Incidence Graphs Every hypergraph has an associated bipartite graph called its incidence graph. The incidence graph has two kinds of vertices: $$ V $$ and $$ E. $$ A vertex \(v \in V\) is connected to a hyperedge-node \(e \in E\) when $$ v \in e. $$ Thus each incidence relation becomes an ordinary graph edge. For example, if $$ e=\{a,b,c\}, $$ then the incidence graph contains edges $$ a-e,\qquad b-e,\qquad c-e. $$ The incidence graph converts a hypergraph into an ordinary bipartite graph while preserving which vertices belong to which hyperedges. This representation is useful for algorithms, visualization, and matrix methods. It also makes clear that a hypergraph is fundamentally a vertex-edge incidence structure. ## 24.9 The 2-Section Graph Another way to associate an ordinary graph to a hypergraph is the \(2\)-section, also called the primal graph. The \(2\)-section graph has the same vertex set \(V\). Two distinct vertices \(u\) and \(v\) are adjacent if they occur together in some hyperedge: $$ \exists e \in E \quad \text{such that} \quad u,v \in e. $$ Thus each hyperedge becomes a clique in the \(2\)-section graph. For example, the hyperedge $$ \{a,b,c\} $$ creates ordinary graph edges $$ \{a,b\},\qquad \{a,c\},\qquad \{b,c\}. $$ The \(2\)-section is useful when pairwise co-occurrence is enough. It loses information, however. The single hyperedge \(\{a,b,c\}\) and the three hyperedges \(\{a,b\}, \{a,c\}, \{b,c\}\) have the same \(2\)-section, but they describe different hypergraphs. ## 24.10 Dual Hypergraph The dual of a hypergraph interchanges the roles of vertices and hyperedges. Let $$ H=(V,E). $$ The dual hypergraph $$ H^* $$ has one vertex for each hyperedge of \(H\). For each original vertex \(v \in V\), the dual has a hyperedge consisting of all original hyperedges that contain \(v\). More concretely, if $$ E = \{e_1,\ldots,e_m\}, $$ then the vertices of \(H^*\) are $$ e_1,\ldots,e_m. $$ For each $$ v \in V, $$ define $$ e_v^* = \{e_i \in E : v \in e_i\}. $$ The collection of these sets forms the hyperedges of the dual. Duality is useful because many statements about vertices have corresponding statements about hyperedges. In matrix terms, taking the dual corresponds to transposing the incidence matrix. ## 24.11 Simple Hypergraphs and Repeated Hyperedges A hypergraph is simple if it has no repeated hyperedges and usually no hyperedge contained in another, depending on convention. The most common minimal condition for simplicity is that no hyperedge is repeated. Some authors also call a hypergraph reduced if no hyperedge is a strict subset of another hyperedge. If repeated hyperedges are allowed, the edge collection \(E\) should be treated as a multiset. This is useful when the same group relation occurs more than once. For example, in transaction data, the same item set may appear in many transactions. One may either keep repeated hyperedges or store one hyperedge with a multiplicity. The choice depends on whether repeated occurrence carries information. ## 24.12 Weighted Hypergraphs A weighted hypergraph assigns weights to hyperedges, vertices, or both. For hyperedge weights, one writes $$ w:E\to \mathbb{R}. $$ The number \(w(e)\) may represent cost, capacity, frequency, strength, probability, or importance. For example, if a hyperedge represents a transaction, its weight may be the number of times that exact transaction appears. If a hyperedge represents a collaboration team, its weight may measure the strength or duration of collaboration. Weighted hypergraphs are important in clustering, machine learning, information retrieval, and network analysis. ## 24.13 Hypergraph Coloring A coloring of a hypergraph assigns colors to vertices. One common coloring problem asks for a coloring such that no hyperedge of size at least \(2\) is monochromatic. That is, every hyperedge with at least two vertices must contain at least two colors. A hypergraph is \(2\)-colorable if its vertices can be split into two color classes so that no nontrivial hyperedge lies entirely in one class. This property is also known as Property B. Hypergraph coloring generalizes graph coloring, but it behaves differently. In graph coloring, every edge has size \(2\), so an edge is properly colored exactly when its two endpoints receive different colors. In a hypergraph, a hyperedge with many vertices only needs to avoid being entirely one color under this weak coloring rule. Other stronger coloring conventions are also used. ## 24.14 Matchings and Covers A matching in a hypergraph is a set of pairwise disjoint hyperedges. Thus $$ M \subseteq E $$ is a matching if $$ e \cap f = \varnothing $$ for all distinct $$ e,f \in M. $$ A vertex cover is a set of vertices that meets every hyperedge. Thus $$ C \subseteq V $$ is a vertex cover if $$ C \cap e \neq \varnothing $$ for every $$ e \in E. $$ These definitions generalize ordinary graph matching and vertex cover. They are central in combinatorics and optimization. In hypergraphs, matching and covering problems are often harder than their graph counterparts because each hyperedge may involve many vertices. ## 24.15 Hypergraph Cycles Cycles in hypergraphs are subtler than cycles in ordinary graphs. In a graph, there is one standard notion of a cycle. In a hypergraph, several definitions are useful. One common definition is the Berge cycle. A Berge cycle is an alternating sequence of distinct vertices and distinct hyperedges $$ v_1,e_1,v_2,e_2,\ldots,v_k,e_k,v_1, $$ where each consecutive pair of vertices lies in the corresponding hyperedge: $$ v_i, v_{i+1} \in e_i, $$ with indices taken cyclically. Other notions, such as tight cycles, are used especially for uniform hypergraphs. The correct definition depends on the theorem or application. ## 24.16 Directed Hypergraphs A directed hypergraph generalizes a directed graph by allowing an arc to have a set of tails and a set of heads. A directed hyperedge may be written as $$ (T,H), $$ where $$ T \subseteq V $$ is the tail set and $$ H \subseteq V $$ is the head set. This can model rules with multiple inputs and multiple outputs. For example, $$ \{a,b\} \to \{c,d\} $$ may mean that \(a\) and \(b\) together imply, produce, or enable \(c\) and \(d\). Directed hypergraphs appear in logic, databases, reaction networks, workflow systems, and program analysis. The standard definition generalizes directed graph arcs by replacing the single tail and single head with sets of vertices. ## 24.17 Applications Hypergraphs appear when relations are higher-order rather than pairwise. | Application | Vertices | Hyperedges | |---|---|---| | Databases | attributes or records | multi-attribute relations | | Transactions | items | baskets of items | | Collaboration networks | people | teams or papers | | Chemistry | atoms or compounds | reactions or molecular groups | | Machine learning | data points | higher-order similarity groups | | Information retrieval | terms or documents | documents or term sets | | Circuit design | components | nets connecting several pins | | Logic | propositions | clauses | | Scheduling | tasks | shared resource constraints | | Biology | genes or proteins | pathways or complexes | In each case, replacing a hyperedge by all pairwise edges may lose meaning. A group relation is not always the same as a collection of pairwise relations. ## 24.18 Hypergraphs Versus Graphs A graph records binary relations. A hypergraph records set-valued relations. | Structure | Edge type | Relation represented | |---|---|---| | Graph | pair of vertices | binary relation | | Directed graph | ordered pair of vertices | directed binary relation | | Hypergraph | subset of vertices | higher-order relation | | Directed hypergraph | pair of vertex subsets | directed higher-order relation | The choice depends on the model. If every relation is naturally between two objects, a graph is appropriate. If one relation may involve many objects at once, a hypergraph is often more faithful. ## 24.19 Common Mistakes A common mistake is to replace every hyperedge by a clique without considering information loss. The hyperedge $$ \{a,b,c\} $$ means one ternary relation. The clique on \(a,b,c\) means three binary relations. These are different structures. Another mistake is to assume that every graph theorem extends directly to hypergraphs. Many graph concepts have several non-equivalent hypergraph analogues. A third mistake is to ignore uniformity. Results for \(k\)-uniform hypergraphs may fail when hyperedges have varying sizes. A fourth mistake is to confuse degree with hyperedge size. The degree of a vertex counts how many hyperedges contain it. The size of a hyperedge counts how many vertices it contains. ## 24.20 Summary A hypergraph is a pair $$ H=(V,E), $$ where \(V\) is a set of vertices and \(E\) is a collection of nonempty subsets of \(V\). The elements of \(E\) are hyperedges. Hypergraphs generalize graphs by allowing edges to contain any number of vertices. A graph is a \(2\)-uniform hypergraph. The main quantities are hyperedge size, rank, vertex degree, incidence, uniformity, and duality. Hypergraphs are the natural language for higher-order relations. They appear in combinatorics, databases, optimization, circuit design, chemistry, machine learning, logic, and network science.