Fact-checked by Grok 2 weeks ago

Hypergraph

A hypergraph is a combinatorial structure that generalizes the concept of a traditional graph by allowing edges, known as hyperedges, to connect an arbitrary number of vertices rather than limiting them to pairs.^[1] Formally, a hypergraph consists of a pair (V, E), where V is a finite set of vertices and E is a family of nonempty subsets of V, each subset representing a hyperedge.^[2] This structure enables the modeling of multi-way relationships that cannot be captured by pairwise connections in standard graphs.^[3] Hypergraphs come in various forms, including k-uniform hypergraphs, where every hyperedge contains exactly k vertices, and linear hypergraphs, where any two hyperedges intersect in at most one vertex.^[3] These generalizations extend classical graph theory concepts such as connectivity, cycles, and matchings to higher-order interactions, with a Berge cycle defined as an alternating sequence of distinct vertices and hyperedges where each vertex in the sequence is contained in the preceding and following hyperedges.^[2] The theory of hypergraphs forms one of the most general frameworks in discrete mathematics, encompassing systems of finite sets and supporting advanced topics like extremal combinatorics and spectral analysis.^[4] The systematic study of hypergraphs was pioneered by French mathematician Claude Berge, who formalized the concept in his 1973 book Graphs and Hypergraphs, building on earlier ideas from set theory and combinatorics dating back to around 1960.^[5] Berge's work established hypergraphs as a foundational tool in combinatorial optimization and theoretical computer science, influencing subsequent developments in areas like matroid theory and coding theory.^[6] Hypergraphs find extensive applications across mathematics and computer science, including the resolution of scheduling and location problems in optimization, modeling complex networks in social and biological systems, and higher-order data analysis in computer vision and machine learning.^[7] In database design, they represent relational schemas where attributes form hyperedges connecting multiple entities, while in network science, they capture group interactions beyond binary relations.^[8] Their versatility also extends to chemistry for molecular structure modeling and to data science for homology computations in topological analysis.^[9]

Definition and Fundamentals

Formal Definition

A hypergraph H is formally defined as an ordered pair H = (V, E), where V is a finite set of elements called vertices, and E is a family of non-empty subsets of V, known as hyperedges or edges.^[5] Each hyperedge connects an arbitrary number of vertices, generalizing the concept of edges in graphs, which are restricted to pairs. The size of a hyperedge is its cardinality, and hyperedges may have sizes of 1 or greater, though single-vertex hyperedges (loops) are sometimes excluded in simple variants.^[10] Several variants of hypergraphs exist to address specific structural constraints. A simple hypergraph has no repeated hyperedges. A k-uniform hypergraph, or k-hypergraph, is one where every hyperedge contains exactly k vertices.^[5] Directed hypergraphs extend the structure by defining each hyperedge as an ordered pair (T, H) of disjoint non-empty subsets of V, where T is the tail (source) and H is the head (target).^[10] Degenerate cases include the empty hypergraph, where both V = \emptyset and E = \emptyset, and the trivial hypergraph, where V \neq \emptyset but E = \emptyset. Standard definitions typically exclude empty hyperedges to ensure meaningful connectivity, as an empty set would not incident any vertices.^[11] The term "hypergraph" was coined by Claude Berge in his 1973 book Graphs and Hypergraphs, where he formalized the structure as a generalization of graphs (which are precisely 2-uniform hypergraphs).^[5]

Examples and Intuition

A basic example of a hypergraph consists of a vertex set V = \{1, 2, 3, 4\} and a hyperedge set E = \{\{1,2\}, \{2,3,4\}, \{1,4\}\}, where the hyperedges connect subsets of varying sizes among the vertices.^[12] This structure captures multi-way associations, such as grouping elements that share common properties or relations. Hyperedges in a hypergraph serve as generalizations of edges in ordinary graphs, acting like "hyperlinks" that bind multiple vertices together in a single connection rather than limiting associations to pairs.^[12] This allows modeling of complex interactions where more than two entities are interdependent, providing intuition for scenarios beyond binary relationships. In real-world applications, hypergraphs model group dynamics effectively; for example, vertices representing members of Congress can have hyperedges corresponding to committees, where each hyperedge encompasses all members assigned to a specific committee, thus encoding collective decision-making processes.^[13] A prominent uniform hypergraph example is the Fano plane, a 3-uniform hypergraph with 7 vertices and 7 hyperedges, each containing exactly 3 vertices, derived from the projective plane of order 2 over the finite field GF(2).^[14] Here, every pair of vertices appears in exactly one hyperedge, illustrating balanced, symmetric multi-connections typical in combinatorial designs. Non-uniform hypergraphs arise naturally as families of sets in set theory, where the vertex set is the universal set and hyperedges form an arbitrary collection of subsets without size restrictions, enabling the representation of diverse relational structures like power sets or intersecting families.^[12]

Relation to Graphs

Hypergraphs generalize the concept of graphs by allowing edges to connect arbitrary subsets of vertices rather than just pairs, providing a framework for modeling more complex relational structures. An undirected graph is a special case of a hypergraph known as a 2-uniform hypergraph, where every hyperedge contains exactly two vertices.^[15] Similarly, a directed graph corresponds to a 2-uniform directed hypergraph, in which each directed hyperedge links exactly two vertices with a specified direction.^[16] This uniformity condition aligns the structural properties of graphs with those of hypergraphs while highlighting the latter's capacity to extend beyond pairwise connections. One common way to represent a hypergraph is through its associated bipartite incidence graph, also called the Levi graph, where one part of the bipartition consists of the original vertices and the other part consists of the hyperedges, with edges in the bipartite graph connecting a vertex to a hyperedge if the vertex belongs to that hyperedge.^[15] This bipartite structure preserves the incidence relations of the hypergraph and facilitates the application of graph-theoretic algorithms to hypergraph problems, such as connectivity analysis or matching. Conversely, not every bipartite graph arises as an incidence graph of a hypergraph, as the hyperedge side must correspond to non-empty subsets without isolated components in certain formulations. The primary motivation for introducing hypergraphs stems from the limitations of graphs in capturing higher-order interactions, where multiple entities interact simultaneously in ways that cannot be adequately represented by pairwise edges alone.^[17] For instance, in relational data modeling, such as databases or social networks, hypergraphs can represent tuples or group affiliations as hyperedges encompassing several vertices, enabling the analysis of multi-way associations that traditional graphs approximate through auxiliary nodes or cliques. This generalization supports applications in areas like data mining, where complex dependencies require modeling beyond binary relations. Historically, the formal theory of hypergraphs was developed by Claude Berge in the 1960s and 1970s, with his 1970 book Graphes et hypergraphes providing a systematic extension of graph theory to include hyperedges of arbitrary size. However, the underlying ideas trace back to earlier uses in incidence geometry, where structures like points and lines in projective planes were modeled using set systems akin to hypergraphs, predating Berge's formalization by over a century in the context of combinatorial designs and geometric configurations.

Properties and Structure

Basic Properties

The order of a hypergraph H = (V, E) is defined as the number of vertices, denoted |V|.^[18] The size of H is the number of edges, denoted |E|.^[18] The rank of a hypergraph, denoted r(H), is the maximum cardinality of its edges, i.e., r(H) = \max_{e \in E} |e|.^[19] The minimum cardinality of its edges is called the anti-rank or corank, denoted s(H) = \min_{e \in E} |e|.^[19] A hypergraph is uniform (or k-uniform) if all edges have the same cardinality k, in which case r(H) = s(H) = k.^[20] The degree of a vertex v \in V, denoted d(v), is the number of edges in E that contain v.^[21] A hypergraph is r-regular if every vertex has degree r.^[21] The average degree \overline{d} is given by the formula

\overline{d} = \frac{\sum_{e \in E} |e|}{|V|},

which represents the total number of vertex-edge incidences divided by the order of the hypergraph.^[22] For a k-uniform hypergraph, the total number of incidences equals k \cdot |E|.^[20] The dual hypergraph H^* of H = (V, E) is constructed by interchanging the roles of vertices and edges: the vertex set of H^* is E, and for each v \in V, there is an edge in H^* consisting of all edges in E that contain v.^[23] This duality preserves the incidence structure but reverses the perspective between vertices and edges.^[24]

Connectivity and Components

In hypergraphs, a path is formally defined as an alternating sequence of distinct vertices v_0, v_1, \dots, v_k and distinct hyperedges e_1, e_2, \dots, e_k such that for each i = 1, \dots, k, the vertices v_{i-1} and v_i both belong to the hyperedge e_i.^[25] This Berge path generalizes the notion from graphs, allowing hyperedges to connect more than two vertices while ensuring no repetition of vertices or edges in the sequence. The length of such a path is k, corresponding to the number of hyperedges traversed. A hypergraph is connected if, for every pair of distinct vertices u and v, there exists a path between them.^[25] Equivalently, the underlying incidence graph of the hypergraph—where vertices represent both the original vertices and hyperedges, with edges linking vertices to their incident hyperedges—is connected, provided no empty hyperedges exist.^[25] In a connected hypergraph, the number of connected components is exactly 1.^[25] Connected components of a hypergraph are the maximal connected subhypergraphs, obtained by partitioning the vertex set into equivalence classes where two vertices are equivalent if a path exists between them, and inducing the subhypergraph on each class while excluding empty hyperedges.^[25] The number of such components, denoted \omega(H), measures the fragmentation of the hypergraph; for instance, in a disconnected hypergraph with multiple isolated vertices, \omega(H) exceeds 1.^[25] For directed hypergraphs, where hyperedges have designated source and target sets, strong connectivity requires that for every pair of distinct vertices u and v, there exists a directed path from u to v and from v to u.^[26] This mutual reachability extends the undirected case and underpins algorithms for transitive closure and shortest hyperpaths in applications like database query optimization.^[26] The diameter of a connected hypergraph is the maximum length of the shortest paths between any pair of vertices, formally \operatorname{diam}(H) = \max_{u,v \in V} d(u,v), where d(u,v) is the minimum path length from u to v. This metric quantifies the hypergraph's "spread," with smaller diameters indicating more efficient vertex interconnectivity; for example, in a complete uniform hypergraph, the diameter is 1.

Cycles and Acyclicity

In hypergraphs, cycles generalize the concept from graphs, capturing dependencies among vertices through hyperedges. The most fundamental notion is the Berge cycle, introduced by Claude Berge, which consists of an alternating sequence of distinct vertices v_1, v_2, \dots, v_k and distinct hyperedges e_1, e_2, \dots, e_k (with indices modulo k) such that for each i, the vertices v_i and v_{i+1} both belong to the hyperedge e_i. This definition allows hyperedges to contain additional vertices beyond the two consecutive ones in the sequence, making Berge cycles a loose analog to graph cycles. A stricter variant, particularly relevant for uniform hypergraphs, is the tight cycle. In a k-uniform hypergraph, a tight cycle of length \ell (with \ell \geq k) is a cyclic sequence of \ell distinct vertices v_0, v_1, \dots, v_{\ell-1} such that every consecutive k-tuple (v_i, v_{i+1}, \dots, v_{i+k-1}) (indices modulo \ell) forms a hyperedge, with no extraneous vertices in those hyperedges.^[27] Tight cycles emphasize exact coverage of consecutive vertices, contrasting with the permissiveness of Berge cycles, and are central to studies of Hamiltonicity in uniform hypergraphs. A hypergraph is acyclic if it contains no Berge cycles; such structures are known as Berge-acyclic hypergraphs.^[28] The absence of Berge cycles implies that the bipartite incidence graph—connecting vertices to the hyperedges containing them—is itself acyclic (a forest).^[28] Connected Berge-acyclic hypergraphs are termed hypertrees, generalizing graph trees, while disconnected ones form hyperforests as disjoint unions of hypertrees. In the special case of linear hypergraphs (where any two hyperedges intersect in at most one vertex), a connected Berge-acyclic hypergraph is a linear hypertree satisfying |E| = |V| - 1, mirroring the edge count in graph trees.^[28] A finer notion of acyclicity is \alpha-acyclicity, which refines Berge-acyclicity by imposing a chordal condition: every Berge cycle of length greater than 3 contains a chord, defined as a hyperedge that intersects the cycle in at least two non-consecutive vertices from the sequence.^[28] Equivalently, a hypergraph is \alpha-acyclic if and only if it admits a join tree: a tree whose nodes are the hyperedges, such that for every vertex, the subtrees induced by hyperedges containing it form a connected subtree.^[28] This property ensures structural simplicity, facilitating efficient algorithms in database query optimization and constraint satisfaction. The girth of a hypergraph is the length of its shortest Berge cycle, providing a measure of local cyclicity analogous to graph girth.^[27] Hypergraphs of large girth are sparse and cycle-free over short lengths, with applications in coding theory and extremal combinatorics.

Representations and Models

Incidence Structures

In a hypergraph H = (V, E), the incidence relation is a binary relation between the vertex set V and the edge set E, where a vertex v \in V is incident to an edge e \in E if and only if v \in e. This relation captures the fundamental membership structure of the hypergraph, generalizing the adjacency in ordinary graphs where edges connect exactly two vertices.^[4] The incidence graph (also known as the Levi graph) of a hypergraph H is the bipartite graph G = (V \cup E, F) with bipartition (V, E) and edge set F = \{\{v, e\} \mid v \in e, v \in V, e \in E\}.^[4]^[29] This construction embeds the hypergraph's incidence structure into a standard graph framework, allowing many hypergraph properties to be analyzed via bipartite graph theory. For instance, the incidence graph is connected if and only if the hypergraph is connected, assuming no empty edges.^[21] Moreover, problems on hypergraphs, such as connectivity or matching, can often be reformulated and solved using corresponding graph algorithms on the incidence graph.^[4] In the case of multi-hypergraphs, where multiple edges between the same pair of vertices are permitted or where the same subset may appear more than once as an edge, the incidence relation allows for multiple incidences between a vertex and an edge.^[30] This corresponds to parallel edges in the incidence graph, enabling the modeling of weighted or repeated connections while preserving the bipartite structure.^[4] The adjacency matrix of the incidence graph is precisely the unsigned incidence matrix of the hypergraph, a |V| + |E| by |V| + |E| matrix with zero blocks on the diagonal and the |V| by |E| incidence matrix (entries 1 if incident, 0 otherwise) in the off-diagonal blocks.^[4]^[31]

Matrix Representations

Hypergraphs can be represented algebraically using matrices that capture the incidence relations between vertices and hyperedges, facilitating computational analysis and theoretical investigations in linear algebra. The primary such representation is the incidence matrix M, a |V| \times |E| matrix where rows correspond to vertices and columns to hyperedges, with entries M_{v,e} = 1 if vertex v belongs to hyperedge e, and $0 otherwise.^[15] This unsigned matrix encodes the structure of an undirected hypergraph and serves as a foundation for deriving other matrix forms. For directed hypergraphs, where hyperedges possess an orientation (e.g., distinguishing tails and heads among vertices), signed variants of the incidence matrix are employed; entries may be +1 for vertices in the head set, -1 for those in the tail set, and $0 otherwise, enabling analysis of directed interactions. Complementing the incidence matrix, the adjacency matrix provides pairwise relations among vertices or hyperedges. The vertex adjacency matrix A is a |V| \times |V| symmetric matrix where A_{u,v} equals the number of hyperedges containing both vertices u and v (with A_{u,u} counting hyperedges incident to u).^[15] Dually, the edge adjacency matrix captures overlaps between hyperedges, with entries A^e_{e,f} denoting the size of the intersection |e \cap f| for distinct hyperedges e and f.^[32] These matrices extend the graph-theoretic adjacency concept to higher-order relations, allowing the study of co-occurrence patterns. Key properties of the incidence matrix arise in linear algebraic contexts over hypergraphs. The degree vector \mathbf{d}, whose v-th entry is the degree of vertex v (the number of incident hyperedges), is computed as \mathbf{d} = M \mathbf{1}_E, where \mathbf{1}_E is the all-ones vector of length |E|.^[15] Similarly, the dual degree vector for hyperedges is \mathbf{d}^E = M^T \mathbf{1}_V. Laplacian-like matrices, generalizing the graph Laplacian, are constructed using the incidence matrix; one common form is L = D_v - A, where D_v is the diagonal degree matrix for vertices, though more sophisticated variants incorporate the incidence structure as L = I - D_v^{-1/2} M M^T D_v^{-1/2} to normalize for hyperedge sizes.^[33] These enable spectral properties analogous to graphs, such as eigenvalue analysis for structural insights. Matrix representations support computational techniques, particularly spectral analysis, where eigenvalues of adjacency or Laplacian-like matrices reveal expansion properties of hypergraphs. For instance, the second-largest eigenvalue of the normalized adjacency matrix bounds the Cheeger constant, quantifying how well the hypergraph expands from subsets of vertices to hyperedges, with applications in clustering and optimization.^[34] Such tools, rooted in the incidence matrix, underpin algorithms for hypergraph partitioning and embedding in machine learning contexts.^[35]

Geometric and Visual Models

Geometric models for hypergraphs involve embedding vertices as points in Euclidean space and representing hyperedges as geometric regions, such as convex hulls or simplices, that enclose the corresponding vertices while minimizing visual clutter and overlaps.^[36] This approach extends traditional graph drawing by allowing hyperedges to connect arbitrary subsets, often visualized as "blobs" or closed curves containing multiple vertices, with algorithms designed to position vertices to reduce edge-region intersections and enhance readability.^[37] For instance, in subset-based drawings, each hyperedge is depicted as a connected region enveloping its vertices, ensuring no unintended inclusions of extraneous points.^[38] Simplicial complexes provide a structured geometric realization of certain hypergraphs, particularly those that are downward-closed (i.e., if a set is an edge, all its subsets are edges), where hyperedges of rank k correspond to (k-1)-dimensional simplices glued along shared faces.^[39] The geometric realization of such a complex is the topological space formed by embedding these simplices in \mathbb{R}^d for sufficient d, preserving incidence relations and enabling analysis of higher-order connectivity through topological invariants like homology.^[40] This model is foundational in combinatorial topology, allowing hypergraphs to be visualized as polyhedral complexes, with uniform hypergraphs of rank d+1 realized as d-dimensional simplicial assemblies.^[41] The crossing number of a hypergraph quantifies the minimum number of intersections between hyperedge representations in a drawing, analogous to graph planarity but generalized to region overlaps or boundary crossings.^[42] In rectilinear models, vertices are placed in general position in \mathbb{R}^d, and d-uniform hyperedges are drawn as (d-1)-simplices (convex hulls), with crossings counted only between disjoint hyperedges; for complete d-uniform hypergraphs on n vertices, this number is \Theta(n^{2d}).^[43] Techniques for minimizing crossings include force-directed layouts adapted for hypergraphs, where auxiliary nodes represent hyperedges to simulate repulsive forces between non-incident elements and attractions within edges, often transforming the structure into a proxy graph for standard algorithms.^[44] Dual drawings leverage incidence graphs—bipartite graphs with vertices on one side and hyperedges on the other—to visualize relationships, embedding the bipartite layout and then overlaying hyperedge regions as unions of adjacent vertex faces in a planar subdivision.^[45] This method ensures connected hyperedge areas while avoiding triple curve intersections, suitable for compact representations where bounded faces correspond to vertices.^[45] As an example, a 3-uniform hypergraph can be drawn as a collection of triangles (simplices) sharing vertices, with positions optimized via force-directed methods to minimize crossings and reveal structural patterns like overlapping triples.^[44]

Generalizations and Extensions

Coloring and Partitioning

In hypergraph theory, coloring extends the concept from graphs to handle higher-arity relations. A proper vertex coloring of a hypergraph H = (V, E) assigns colors from a set C to vertices in V such that no hyperedge in E is monochromatic, meaning every hyperedge contains at least two vertices of different colors.^[4] The chromatic number \chi(H) is the smallest integer k such that H admits a proper k-coloring. This definition generalizes graph coloring, where edges are 2-uniform, but allows for more flexible constraints in non-uniform hypergraphs. A strong coloring of H requires that no two vertices within the same hyperedge share a color, ensuring every hyperedge is rainbow (all vertices in it receive distinct colors).^[46] The strong chromatic number \chi_s(H) is the minimum number of colors needed for such a coloring, and it satisfies \chi_s(H) \geq \max_{e \in E} |e|, the size of the largest hyperedge. In uniform hypergraphs of rank r, \chi_s(H) = \chi(G), where G is the primal graph of H (with vertices V and edges between any pair of vertices sharing a hyperedge).^[46] Partitioning in hypergraphs often involves decomposing the structure into subhypergraphs while balancing sizes, analogous to equitable colorings in graphs. An edge partition divides the edge set E into subsets E_1, \dots, E_k forming subhypergraphs H_i = (V, E_i) that are edge-disjoint and cover E. Equitable partitions extend this by requiring the subhypergraphs or color classes to have nearly equal sizes, such as vertex sets differing by at most one; for colorings, an equitable k-coloring partitions V into k classes of sizes \lfloor |V|/k \rfloor or \lceil |V|/k \rceil, avoiding monochromatic hyperedges. In r-uniform hypergraphs, every strong r-coloring is equitable if the uniformity allows balanced distribution.^[47] Key theorems bound the chromatic number relative to structural parameters. For a hypergraph H with maximum degree \Delta (number of hyperedges containing a vertex) and minimum hyperedge size \delta \geq 2, let k = \lceil 2\Delta / \delta \rceil; then \chi(H) \leq k + 1, with equality to k if \delta \geq 3 and k \geq 3, providing a Brooks-type bound generalizing the graph case where \chi(G) \leq \Delta + 1.^[48] This improves on trivial bounds like \chi(H) \leq |V|. Such colorings find applications in scheduling problems, where hyperedges represent multi-party conflicts requiring diverse assignments.^[49]

Isomorphism and Symmetry

In hypergraph theory, two hypergraphs H = (V, E) and H' = (V', E') are isomorphic if there exists a bijection f: V \to V' such that for every subset S \subseteq V, S \in E if and only if f(S) \in E'.^[50] This bijection preserves the structure by mapping hyperedges to hyperedges exactly. For labeled hypergraphs, where vertices carry distinct labels, structural equality requires both the bijection and label preservation, whereas isomorphism allows relabeling while maintaining edge relations.^[50] The automorphism group of a hypergraph H = (V, E), denoted \operatorname{Aut}(H), consists of all bijections f: V \to V that map E to itself, forming a subgroup of the symmetric group on V.^[4] The order of \operatorname{Aut}(H), or |\operatorname{Aut}(H)|, quantifies the hypergraph's symmetry, with larger orders indicating higher degrees of structural invariance under vertex permutations.^[4] For example, the complete k-uniform hypergraph on n vertices, where E includes all k-subsets of V, has \operatorname{Aut}(H) \cong S_n, the full symmetric group, due to the invariance under any permutation of vertices.^[51] In contrast, path hypergraphs—linear sequences of overlapping hyperedges—exhibit limited symmetry, often with \operatorname{Aut}(H) isomorphic to the trivial group or \mathbb{Z}_2 (reflections only), depending on the path length and uniformity.^[52] Algorithmically, deciding hypergraph isomorphism is at least as hard as graph isomorphism (GI), since graphs are 2-uniform hypergraphs; for certain classes like β-acyclic hypergraphs, it is GI-complete under polynomial-time Turing reductions.^[53] Symmetry breaking techniques in hypergraph computations aim to reduce the impact of large automorphism groups by imposing constraints that eliminate redundant equivalent configurations, such as in distributed algorithms for maximal independent set selection where randomized labeling breaks vertex symmetries within hyperedges.^[54] These methods enhance efficiency in enumeration or optimization tasks by pruning isomorphic branches in search spaces.^[54] A subhypergraph of a hypergraph H = (V, E) is obtained by selecting a subset V' \subseteq V of vertices and a subset E' \subseteq E of edges, resulting in the hypergraph H' = (V', E'). This construction preserves the incidence relations between the chosen vertices and edges from the original hypergraph. An induced subhypergraph on a vertex subset A \subseteq V is specifically defined as H_A = (A, \{e \cap A \mid e \in E\}), where edges are the intersections of original edges with A, typically excluding empty sets to maintain non-trivial structure. These induced subhypergraphs are useful for analyzing local properties, as they capture all possible connections within the selected vertices based on the original incidences. The dual hypergraph H^T of a hypergraph H = (V, E) is constructed by interchanging the roles of vertices and edges: the vertex set of H^T is E, and the edge set consists of the stars of the original vertices, where the star of a vertex v \in V is the set \{e \in E \mid v \in e\}.^[55] Equivalently, the incidence matrix of H^T is the transpose of that of H, ensuring that duals preserve combinatorial properties like uniformity in certain cases. This duality relation highlights incidence symmetries and is foundational in hypergraph theory, as introduced in early works on the subject. The line hypergraph L(H) of a hypergraph H = (V, E) without isolated vertices has vertex set E and edge set \{\{e \in E \mid v \in e\} \mid v \in V\}, where each edge corresponds to the set of original edges incident to a common vertex v. This generalizes the line graph of ordinary graphs, transforming edge connectivity into vertex relations and revealing structural overlaps, such as shared incidences. Line hypergraphs are particularly relevant for studying edge-based properties and have been surveyed for their applications in recognizing hypergraph classes.^[56] For a vertex v \in V in a hypergraph H = (V, E), the section hypergraph at v (also called the star section or link hypergraph) has vertex set N(v) = \bigcup \{e \setminus \{v\} \mid v \in e \in E\} (the neighbors of v) and edge set \{e \setminus \{v\} \mid v \in e \in E\}, representing the traces or intersections of incident edges with the star of v.^[57] This structure isolates the local neighborhood around v, excluding v itself, and facilitates analysis of vertex degrees and connectivity in the context of the star \mathrm{St}(v) = \{e \in E \mid v \in e\}. A transversal, also known as a hitting set or vertex cover, of a hypergraph H = (V, E) is a subset T \subseteq V such that T \cap e \neq \emptyset for every e \in E.^[58] Minimal transversals are those where no proper subset satisfies this intersecting property, and they play a key role in optimization problems related to covering all edges with vertex selections. The transversal number \tau(H) denotes the size of the smallest such set, linking to concepts like degrees in basic properties.^[58]

Advanced Concepts and Generalizations

Tight and Berge Cycles

A Berge cycle of length k \geq 2 in a hypergraph H = (V, E) is defined as an alternating sequence of distinct vertices v_1, v_2, \dots, v_k \in V and distinct hyperedges h_1, h_2, \dots, h_k \in E such that v_i, v_{i+1} \in h_i for i = 1, \dots, k-1 and v_k, v_1 \in h_k.^[59] The length refers to the number of hyperedges (or vertices) in the sequence, and such cycles can be of odd or even length depending on k. Extensions to chordal structures include Berge-chordal hypergraphs, where every Berge cycle of length greater than 3 possesses a chord—a hyperedge that contains at least three vertices from the cycle, ensuring no induced long cycles.^[60] A hypergraph is Berge-acyclic if it contains no Berge cycles; connected Berge-acyclic hypergraphs are precisely hypertrees, generalizing tree structures to allow hyperedges while maintaining acyclicity in the incidence graph sense.^[60] Tight cycles provide a stricter notion of cyclicity, primarily defined for uniform hypergraphs. In a k-uniform hypergraph, a tight k-cycle of length \ell \geq k consists of vertices v_0, v_1, \dots, v_{\ell-1} and hyperedges \{v_i, v_{i+1}, \dots, v_{i+k-1}\} for all i = 0, \dots, \ell-1 (indices modulo \ell), where consecutive edges overlap in exactly k-1 vertices.^[61] This structure is characterized in uniform hypergraphs as the minimal cyclic configuration maximizing overlap, and it generalizes to linear spans in vector spaces by associating vertices with basis vectors and hyperedges with spans of consecutive basis elements, capturing dependencies in the incidence vector space over fields like \mathbb{R}.^[62] For example, in a 3-uniform hypergraph, a tight cycle of length 4 has edges forming a "tetrahedral" overlap without redundant vertices. β-acyclicity refines acyclicity by prohibiting β-cycles, defined as sequences (x_0, e_1, x_1, \dots, e_k, x_k = x_0) with k \geq 3, distinct x_i \in V, distinct e_i \in E, x_i \in e_i \cap e_{i+1} (with e_0 = e_k), and no x_i belonging to any other e_j in the sequence.^[60] Thus, β-acyclicity requires the absence of such cycles, where consecutive edges intersect solely at single distinct vertices. β-acyclicity and tight acyclicity are distinct refinement notions; β-cycles emphasize minimal (single-vertex) overlaps, while tight cycles focus on maximal (k-1 vertex) overlaps in uniform hypergraphs. β-acyclic hypergraphs relate to matroids through their incidence structures, where the absence of β-cycles ensures the hypergraph's line graph is chordal and supports integral polytopes like the multilinear polytope without fractional vertices.^[63] Key theorems illuminate these concepts. Every hypergraph admits a β-acyclic subhypergraph achieving the same rank, where rank is the size of the largest hyperedge, preserving structural complexity without introducing cycles.^[63] Theorems on hypergraph decompositions into acyclic factors exist under certain degree conditions, enabling partition of edges into Berge or tight cycles while maintaining uniformity. Detecting Hamiltonian tight cycles is NP-hard in general k-uniform hypergraphs for k \geq 3, as the problem subsumes reductions from graph Hamiltonicity.^[64]

Further Abstract Generalizations

Simplicial complexes constitute a fundamental abstraction of hypergraphs, characterized by the down-closure property: if a finite set e serves as a hyperedge (or simplex), then every nonempty subset of e is also a hyperedge. This closure under taking faces distinguishes simplicial complexes from general hypergraphs, enabling their use in capturing hierarchical or nested structures in combinatorial topology. Abstract simplicial complexes emphasize the combinatorial essence, defined as collections of finite sets closed under subsets without reference to embedding, whereas geometric simplicial complexes realize these sets as actual simplices in Euclidean space, such as triangles or tetrahedra, to study topological invariants like homology. The order complex of a partially ordered set (poset) associated with a hypergraph—where elements are ordered by inclusion or incidence—yields an abstract simplicial complex whose simplices correspond to chains in the poset, providing a topological lens for hypergraph subdivision and connectivity.^[65] Hypergraph homomorphisms generalize graph homomorphisms by preserving incidence relations: a function f from the vertex set of one hypergraph H to another H' qualifies as a homomorphism if, for every hyperedge e in H, the image f(e) is contained in some hyperedge of H', ensuring that vertex-edge incidences map to incidences. This structure-preserving map facilitates the study of embeddings and quotients in hypergraph theory. In a categorical perspective, hypergraphs can be modeled as small categories where the objects are the vertices and the hyperedges generate the morphisms, with each hyperedge e = \{v_1, \dots, v_k\} interpreted as a multi-morphism relating the involved objects, often via free generation or relational structures. This view integrates hypergraphs into broader categorical frameworks, allowing composition and functors that respect incidence, as explored in syntactic approaches to hypergraph semantics. Infinite hypergraphs extend the finite framework to vertex sets of arbitrary cardinality, but introduce compactness challenges in analytic properties such as coloring or covering. The de Bruijn–Erdős theorem generalizes to hypergraphs, asserting that an infinite hypergraph admits a proper k-coloring (where no hyperedge is monochromatic) if and only if every finite induced subhypergraph does, via compactness in the product topology over color assignments. This result underscores the finite-to-infinite transfer principle while highlighting potential pathologies in non-uniform or unbounded cases.

Modern Extensions

Modern extensions of hypergraphs have emerged since the early 2000s to address complex real-world scenarios involving weights, uncertainty, randomness, and time evolution, enabling more nuanced modeling in optimization and data analysis. These variants build on classical hypergraph theory by incorporating additional parameters to capture quantitative aspects of relationships among vertices.^[66] Weighted hypergraphs extend standard hypergraphs by assigning non-negative real-valued weights to hyperedges, which represent the strength or cost of multi-way interactions. This allows for the formulation of optimization problems such as the minimum cut, where the goal is to partition vertices into two sets while minimizing the total weight of hyperedges crossing the partition. Algorithms for approximating minimum cuts in weighted hypergraphs, including k-cuts, have been developed using branching processes and randomized contractions, achieving polylogarithmic approximation ratios for dense instances.^[67]^[68] Fuzzy hypergraphs generalize incidences by assigning membership degrees in the interval [0,1] to vertex-edge pairs, accommodating partial belongings and degrees of association. This framework is particularly suited for modeling uncertainty in decision-making and pattern recognition, where crisp boundaries are inadequate. Seminal work formalized fuzzy hypergraphs with fuzzy relations defining edge memberships, enabling operations like union and intersection while preserving fuzzy properties. Applications include social network analysis, where fuzzy memberships capture varying interaction strengths.^[66]^[69] Probabilistic hypergraphs introduce randomness by modeling hyperedge inclusions as independent Bernoulli random variables with given probabilities, facilitating the study of expected structural properties like connectivity and component sizes. These models extend Erdős–Rényi random graphs to higher-order interactions, revealing phase transitions in properties such as giant components. Research has established thresholds for connectivity in uniform random hypergraphs, where the expected degree influences the emergence of connected structures.^[70]^[71] Temporal hypergraphs capture the evolution of interactions over discrete or continuous time by associating timestamps or sequences with hyperedges, suitable for dynamic networks like collaboration systems or event streams. In this setting, hyperedges appear, persist, or disappear, allowing analysis of evolving motifs and community structures. Studies have explored ego-networks in temporal hypergraphs to track individual influence changes and consensus dynamics under time-varying topologies.^[72]^[73] Recent theoretical advances as of 2025 include sheaf hypergraphs, which incorporate local algebraic structures on hyperedges for topological data analysis, and enhanced models for directed hypergraphs addressing asymmetry in multi-way relations.^[74] A notable recent development is the hypergraph p-Laplacian, introduced around 2018, which generalizes the graph p-Laplacian to hypergraphs for semi-supervised learning tasks. This operator, viewed through differential geometry, encodes higher-order neighborhood information via nonlinear diffusion, enhancing clustering and classification on datasets with multi-relational structures. It has been applied to manifold-valued data interpolation, improving robustness in machine learning pipelines.^[75]^[76]

Applications

In Combinatorics and Geometry

Hypergraphs play a central role in extremal combinatorics, particularly through the Erdős–Ko–Rado theorem, which bounds the size of intersecting families in uniform hypergraphs. For an intersecting k-uniform hypergraph on n vertices where n ≥ 2k, the theorem states that the maximum number of edges is \binom{n-1}{k-1}, attained by the family of all k-subsets containing a fixed vertex. This result, originally proved using shifting arguments and double counting, has spurred extensive generalizations to non-uniform and weighted hypergraphs, highlighting the structural constraints on families with restricted intersections.^[77] In geometric settings, hypergraphs inherit the Helly property from convex set families, providing intersection theorems that underpin many results in combinatorial geometry. A hypergraph defined by convex sets in \mathbb{R}^d—where vertices are points and hyperedges are the convex sets—satisfies the Helly property if every collection of d+1 hyperedges with pairwise nonempty intersections has a common point, implying the entire collection intersects.^[78] This d-dimensional Helly number characterizes the intersection behavior of such geometric hypergraphs, enabling proofs of theorems on transversal numbers and piercing sets for families like disks or halfspaces.^[79] The Szemerédi regularity lemma extends to hypergraphs, facilitating the decomposition of k-uniform hypergraphs into equitable partitions where most hyperedges behave pseudorandomly across the parts. Specifically, for any \epsilon > 0, the vertex set can be partitioned into O_{\epsilon,k}(1) classes such that the density of hyperedges within most (k-1)-tuples of classes deviates from uniformity by at most \epsilon.^[80] This hypergraph analogue, established via analytic methods, supports applications like the multidimensional Szemerédi theorem on arithmetic progressions, by reducing dense configurations to counting lemmas in regular partitions.^[81] Design theory models balanced incomplete block designs (BIBDs) as regular uniform hypergraphs with balanced pairwise incidences. A (v,k,\lambda)-BIBD is a k-uniform hypergraph on v vertices where each vertex has degree r = \lambda(v-1)/(k-1), and every pair of vertices lies in exactly \lambda hyperedges, ensuring equitable coverage without the complete design.^[82] These structures, exemplified by projective planes as (q^2+q+1, q+1, 1)-BIBDs for prime powers q, capture symmetric and tactical configurations central to finite geometry and coding theory.^[83] A key geometric application arises in point-line incidences within arrangements, modeled as hypergraphs where vertices are points and hyperedges are lines (each containing multiple incident points). The Szemerédi–Trotter theorem bounds the total incidences I(P,L) between n points P and m lines L in the plane by

I(P,L) = O\left(n^{2/3}m^{2/3} + n + m\right),

with equality nearly achieved by grid-like configurations. This incidence bound controls the complexity of line arrangements as hypergraphs, limiting the number of rich hyperedges and informing extremal problems in discrete geometry.^[84]

In Computer Science and Databases

In relational databases, queries can be modeled as hypergraphs where vertices represent attributes and hyperedges correspond to relations in the query schema. This representation allows relational algebra operations, such as joins, to be interpreted as operations on the hypergraph structure, facilitating analysis of query dependencies and optimization strategies.^[85] For instance, the conjunctive query associated with a relational algebra expression forms a hypergraph whose hyperedges are the relations involved.^[86] Acyclic hypergraphs, in particular, enable efficient query processing through the construction of join trees, which decompose the query into a tree structure where each node represents a relation and edges indicate shared attributes. A join tree ensures that joins can be executed in linear time relative to the input size for acyclic queries, avoiding the combinatorial explosion typical of cyclic structures.^[85] This property, as explored in early database theory, underpins query optimizers that detect acyclicity to select optimal execution plans.^[86] As noted in discussions of cycles and acyclicity, the absence of cycles in the hypergraph guarantees the existence of such a join tree.^[85] In constraint satisfaction problems (CSPs), hypergraphs model the structure where vertices are variables and hyperedges represent constraints involving multiple variables. This hypergraph formulation captures the incidence between variables and constraints, enabling algorithms to exploit structural properties for solvability.^[87] Backtracking algorithms, a cornerstone of CSP solving, traverse the search space by assigning values to variables while checking hyperedge constraints; if a partial assignment violates a constraint, the algorithm backtracks to the last choice point. For hypergraphs with bounded treewidth or other tractable properties, such as being α-acyclic, backtracking can be augmented with decomposition techniques to achieve polynomial-time performance.^[87] Hypergraph partitioning finds application in VLSI design, where circuits are represented as hypergraphs with vertices as cells or modules and hyperedges as nets connecting multiple components. Partitioning minimizes the cut size—the number of hyperedges crossing partitions—to reduce inter-chip communication and wiring congestion.^[88] In channel routing, a subproblem of VLSI layout, hypergraph models assign nets to routing channels while minimizing overlaps and vias, treating multi-terminal nets as hyperedges to optimize track usage.^[88] Multilevel partitioning algorithms, which coarsen the hypergraph iteratively before refining partitions, have been shown to yield high-quality solutions for large-scale VLSI instances, improving routability by up to 20% in benchmark circuits.^[88] Algorithmic problems on hypergraphs include finding a transversal—a minimum set of vertices intersecting every hyperedge—known as the transversal number τ(H). This problem, equivalent to the hypergraph vertex cover, is NP-hard even for 3-uniform hypergraphs.^[89] The greedy algorithm, which iteratively selects the vertex covering the most uncovered hyperedges, achieves an approximation ratio of H_d ≈ ln d + 1, where d is the maximum hyperedge size, matching the inapproximability threshold up to constant factors. For k-uniform hypergraphs, general bounds remain logarithmic.^[90] Post-2015 developments in NoSQL databases leverage hypergraph covers for query optimization, where a hypergraph cover decomposes complex queries into subqueries aligned with denormalized document structures. In schema migration from relational to NoSQL systems, hypergraphs represent query patterns to identify denormalization opportunities, reducing join operations across shards. For example, the query-based denormalization using hypergraph (QBDNH) model transforms relational schemas into NoSQL collections by clustering attributes via hyperedges derived from frequent queries, achieving speedup factors up to 1.40 (about 40% faster) compared to existing models on workloads like TPC-H variants.^[91] This approach extends to polyglot persistence, using hypergraphs to manage metadata across SQL and NoSQL stores for optimized federated queries.^[92]

In Machine Learning and Networks

Hypergraph neural networks (HGNNs) extend graph neural networks to handle higher-order interactions by propagating information across hyperedges, enabling the modeling of complex relational data where multiple nodes interact simultaneously. In HGNNs, message passing occurs over hyperedges, aggregating features from all nodes within a hyperedge before updating node representations, which captures group-wise dependencies more effectively than pairwise edges. A seminal model, HyperGCN, introduced in 2019, approximates hypergraph convolutions by transforming the hypergraph into a bipartite graph for efficient semi-supervised learning on attributed hypergraphs, demonstrating superior performance on tasks like citation network classification compared to traditional graph convolutions.^[93] Subsequent developments have refined this paradigm, with surveys highlighting diverse architectures that incorporate hyperedge-specific aggregators to mitigate over-smoothing in deep layers.^[94] In higher-order network analysis, hypergraphs model multi-way group interactions beyond dyadic relations, particularly in social networks where pairwise graphs overlook collective behaviors. For instance, co-authorship networks represent papers as hyperedges connecting multiple authors, revealing collaboration cliques that influence information diffusion and community formation more accurately than simple graphs. Empirical studies on such networks show that hypergraph representations uncover emergent properties, such as faster contagion in group settings, with applications in predicting scientific impact through hyperedge centrality measures. This approach has been validated on large-scale datasets, where hypergraphs improve modularity detection by 10-20% over graph-based methods in capturing higher-order motifs.^[95] Spectral clustering in hypergraphs leverages the hypergraph Laplacian to partition nodes based on eigenvector decompositions, generalizing graph spectral methods to account for hyperedge connectivity. The Laplacian is constructed from the incidence matrix, with normalized variants enabling relaxation of the normalized cut objective for hypergraphs, leading to clusters that respect multi-way associations. Algorithms using the 1-Laplacian or p-Laplacian variants have shown robustness in partitioning datasets with edge-dependent weights, achieving lower normalized hypergraph cuts on benchmarks like image segmentation compared to subgraph approximations.^[96] This technique is particularly effective for data with inherent group structures, such as web communities, where it outperforms k-means by incorporating spectral gaps from the Laplacian's eigenvalues.^[97] Hypergraphs facilitate anomaly detection in domains with multi-way relations, identifying outliers through deviations in hyperedge patterns or spectral anomalies. In traffic networks, spatio-temporal hypergraph convolutions model intersections as hyperedges linking vehicles and sensors, detecting unusual flow disruptions with reconstruction errors from autoencoder-like HGNNs, outperforming graph-based detectors by capturing group congestion events.^[98] For biological networks, hypergraph models highlight anomalous genes or pathways by analyzing hyperedge centrality in protein interaction complexes, revealing critical disruptions in disease states like cancer, where 1-line graph projections identify outliers missed by pairwise analyses.^[99] Recent advances integrate transformers with hypergraphs to process hyper-relational data, enhancing attention mechanisms over hyperedges for scalable representation learning as of 2023-2025. Models like hierarchical hypergraph transformers employ multi-head attention on hyperedge projections to forecast multivariate time series, achieving up to 15% lower MSE on traffic prediction tasks by fusing local and global dependencies. In biomedical applications, hypergraph transformer networks fuse multi-omics data via granularity-level attention, improving disease classification accuracy by modeling high-order correlations in brain networks. These integrations, often pretrained on large hypergraph corpora, address limitations in vanilla HGNNs for long-range interactions.^[100]

References

[1]
[PDF] Hypergraph Similarity Measures
Hypergraphs are generalizations of graphs in which edges may connect any number of vertices, thereby representing multi-way relationships which are ubiquitous ...
[2]
Hypergraphs
Definition 5.6 (a) A hypergraph is a pair , where is a set of vertices and is a set of edges, an edge simply being a subset of . (b) A hypergraph is called - ...
[3]
GraphTheory
In a hypergraph, the edges (called hyperedges) are arbitrary nonempty sets of vertices. A k-hypergraph is one in which all such hyperedges connected exactly k ...<|control11|><|separator|>
[4]
[PDF] Hypergraph Theory - UC Davis Math
Hypergraphs are systems of finite sets and form, probably, the most general concept in discrete mathematics. This branch of mathematics has developed very.
[5]
Graphs and hypergraphs : Berge, Claude - Internet Archive
Jan 30, 2023 · Publication date: 1973 ; Topics: Graph theory, Hypergraphs ; Publisher: Amsterdam, North-Holland Pub. Co.; New York, American Elsevier Pub. Co.
[6]
(PDF) Hypergraphs: an introduction and review - ResearchGate
Feb 20, 2020 · PDF | Hypergraphs were introduced in 1973 by Berg\'e. This review aims at giving some hints on the main results that we can find in the ...
[7]
Applications of Hypergraph Theory: A Brief Overview - SpringerLink
Apr 18, 2013 · Moreover it well known now that hypergraph theory is a very useful tool to resolve optimization problems such as scheduling problems, location ...
[8]
Hypergraph Representation | Discrete Mathematics - GeeksforGeeks
Aug 2, 2024 · These structures find applications in various fields, including database design, social network analysis, and biological systems modeling.
[9]
Computing hypergraph homology
As a generalization of graphs and simplicial complexes, hypergraphs have various applications in chemistry, biology, computer science and data science.
[10]
https://doi.org/10.1007/978-3-319-00080-0
[11]
Introduction - SpringerLink
Jan 17, 2023 · Generally speaking, unless stated otherwise, hypergraphs have a nonempty vertex set and nonempty hyperedge set and do not contain empty ...<|separator|>
[12]
Hypergraphs : combinatorics of finite sets : Berge, Claude
Jan 28, 2023 · Publication date: 1989 ; Topics: Hypergraphs ; Publisher: Amsterdam ; New York : North Holland : Distributors for the U.S.A. and Canada, Elsevier ...
[13]
Hypergraph Representation Learning for Higher Order Tasks - arXiv
Jan 19, 2021 · Abstract page for arXiv paper 2101.07773: Learning over Families of Sets -- Hypergraph Representation Learning for Higher Order Tasks.
[14]
Fano Plane -- from Wolfram MathWorld
The Fano plane is the configuration consisting of the two-dimensional finite projective plane the Galois field of order 2 GF(2).
[15]
Mathematical Foundations of Hypergraph - SpringerLink
Jan 17, 2023 · By comparison of adjacency matrix and incidence matrix, a graph can be regarded as a 2-uniform hypergraph. In this case, each hyperedge can ...
[16]
https://www.tandfonline.com/doi/full/10.1080/25765299.2025.2555676
[17]
A Survey on Hypergraph Representation Learning
Aug 26, 2023 · Learning over families of sets - Hypergraph representation learning for higher order tasks. In Proc. of the 2021 SIAM Int. Conf. on Data ...
[18]
Hypergraph: an alternative graphical model for computing transfer ...
Hypergraphs are generalizations of graphs with applications in many areas, such as VLSI design and data mining. In this paper, we propose the use of ...
[19]
(PDF) The de Bruijn-Erdős Theorem for Hypergraphs - ResearchGate
Aug 7, 2025 · ... hypergraph His a collection of proper. subcliques that partition H ... This is often viewed as a statement in incidence geometry, in ...
[20]
[PDF] Eulerian properties of hypergraphs - arXiv
Aug 3, 2016 · The number of vertices |V | and number of edges |E| are called the order and size of the hypergraph, respectively. Often we denote n = |V | and ...
[21]
[PDF] Hypergraphs and Matroids
May 22, 2007 · The rank r(H) of a hypergraph is defined as the maximum number of nodes in one edge, r(H) = maxj |Ej|, and the anti-rank s(H) is defined ...
[22]
[PDF] A Survey on Hypergraph Products - arXiv
May 17, 2017 · A simple uniform hypergraph of rank r will be called r-uniform. A hypergraph with r(H) ≤ 2 is a graph. A 2-uniform hypergraph is usually known.
[23]
[PDF] Connection and separation in hypergraphs
A hypergraph H is regular of degree r. (or r-regular) if every vertex of H has degree r. The maximum (minimum) cardinality |e| of any edge e ∈ E is called the ...
[24]
[PDF] Sampling hypergraphs with given degrees - Hal-Inria
Dec 10, 2021 · In the hypergraph setting, m is the number of edges and d is the average degree of any ... formula for irregular, sparse bipartite graphs.
[25]
[PDF] On Duality Concepts regarding Hypergraphs and Propositional ...
The (set theoretical) dual hypergraph H∗ of H is defined as follows: For each x ∈ V let x∗ := {i ∈ I : x ∈ ei} be the dual (hyper)edge corresponding to x. Then ...
[26]
[PDF] Duality of hypergraphs
A hypergraph in which all edges have the same degree r ≥ 0 is called r-uniform. The rank of a hypergraph H is. D r( ) max | D | .
[27]
http://www.cs.wpi.edu/~gsarkozy/Cikkek/Rio08.pdf
[28]
Directed hypergraphs: Introduction and fundamental algorithms—A ...
Jan 7, 2017 · Directed hypergraphs: Introduction and fundamental algorithms—A survey ... View PDFView articleView in Scopus. [16]. G. Gallo, G. Longo, S ...
[29]
[PDF] Cycles in Hypergraphs
Aug 13, 2008 · There are several natural definitions for a hypergraph cycle. We survey these different cycle notions and some results available for them.Missing: seminal | Show results with:seminal
[30]
[PDF] Degrees of Acyclicity for Hypergraphs and Relational Database ...
A hypergraph is Berge-cyclic if it has a Berge cycle; otherwise, it is Berge-acyclic. As an example, the hypergraph of Figure 6 is Berge-cyclic, because it ...
[31]
[PDF] Ubergraphs: A Definition of a Recursive Hypergraph Structure - arXiv
Apr 18, 2017 · Then the Levi graph is the bipartite graph G = (V ˙∪ E,E0), where. (vi,ej) ∈ E0 if and only if vi ∈ ej. Example 1. Let H be the hypergraph with ...
[32]
[PDF] Berge Saturation of Non-Uniform Hypergraphs - math kit
Sep 20, 2018 · If multiple hyperedges are allowed we say that the resulting struc- ture is a multi-hypergraph, i.e. the hyperedges in a multi-hypergraph form a ...
[33]
[PDF] An oriented hypergraphic approach to algebraic graph theory - CORE
Jul 12, 2012 · We define the adjacency, incidence, and Laplacian matrices of an oriented hypergraph and examine walk counting to extend classical matrix ...
[34]
[PDF] Adjacency and Tensor Representation in General Hypergraphs - arXiv
May 30, 2018 · In hypergraphs, adjacency is a 2-adjacency, while e-adjacency is a p-adic relationship, modeled by a tensor, unlike the pairwise relationship ...
[35]
[PDF] Intersection graphs of oriented hypergraphs and their matrices
The rank of H, denoted by r(H), is the maximum edge size in H. The incidence dual (or dual) of a hypergraph H = (V,E,I), denoted by H∗, is the hypergraph ...
[36]
[PDF] Spectra of random regular hypergraphs
May 18, 2019 · Hyperedge and vertex expansion are controlled by the second eigenvalue of the adjacency matrix. The mixing rate of the random walk is ...
[37]
[PDF] On the spectrum of hypergraphs - arXiv
Mar 27, 2019 · The diameter of a hypergraph is also bounded by the eigenvalues of its connectivity matrices. We characterize different properties of a ...
[38]
[PDF] Crossings in Geometric Hypergraphs - TCG Crest
Crossing number(Rectilinear) of a graph G, denoted by cr(G) (cr(G)), is minimum number of crossings among all good (Rectilinear) drawings of it. Page 3 ...
[39]
(PDF) How to draw a hypergraph - ResearchGate
Aug 10, 2025 · We introduce a practical method for drawing hypergraphs. The method is based on the spring algorithm, a well-known method for drawing normal graphs.
[40]
[PDF] Hypergraph Drawing by Force-directed Placement
Nov 25, 2020 · There are two basic methods for drawing a hypergraph. Subset based:- A hyperedge is drawn as a closed curve enveloping its vertices.
[41]
[PDF] The subdivision of hypergraphs - arXiv
Nov 15, 2023 · An (abstract) simplicial complex always has an underlying space or a geometric realization. Moreover, the simplicial approximation theorem ...
[42]
[PDF] arXiv:2409.18310v1 [math.AT] 26 Sep 2024
Sep 26, 2024 · Any abstract simplicial complex can be associated with a geometric realization, whose visualization may help the reader understand ...
[43]
[PDF] arXiv:2002.06895v3 [math.GR] 5 Jul 2023
Jul 5, 2023 · Abstract simplicial complexes are examples of hypergraphs ... geometric realization of the abstract cell complex of a hypercellular graph is.
[44]
On the rectilinear crossing number of complete uniform hypergraphs
In this paper, we consider a generalized version of the rectilinear crossing number problem of drawing complete graphs on a plane. The minimum number of ...
[45]
None
### Summary of Maximum Rectilinear Crossing Number for Uniform Hypergraphs
[46]
[PDF] Hypergraph Drawing by Force-directed Placement - ResearchGate
We propose and evaluate a family of algorithms for drawing hypergraphs. Each algorithm in the family transforms the hypergraph into a graph and can leverage ...
[47]
[PDF] Subdivision Drawings of Hypergraphs - Bettina Speckmann
A hypergraph H can also be drawn as a bipartite graph where one set of vertices corresponds to the vertices of H and the other set corresponds to the hyperedges ...
[48]
[PDF] Hypergraph colouring - arXiv
A hypergraph H is k-uniform if every edge e ∈ H satisfies |e| = k, and a graph is a 2-uniform hypergraph. A matching M ⊆ H in a hypergraph H is a set of ...
[49]
Hypergraph colouring (Chapter 11) - Topics in Chromatic Graph ...
In this introductory section we give the most important definitions required to study hypergraph colouring, and briefly survey the half-century history of this ...Missing: seminal | Show results with:seminal
[50]
[PDF] An Algebraic Formulation of Hypergraph Colorings
Sep 24, 2020 · Abstract. A hypergraph is properly vertex-colored if no edge contains vertices which are assigned the same color.
[51]
On the strong chromatic number of a random 3-uniform hypergraph
A vertex coloring is said to be strong for a hypergraph if every two vertices sharing a common edge are colored with distinct colors.
[52]
Partitions of hypergraphs under variable degeneracy constraints
May 5, 2020 · The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy.
[53]
[PDF] Hypergraph Isomorphism Computation - arXiv
Jul 26, 2023 · Abstract—The isomorphism problem is a fundamental problem in network analysis, which involves capturing both low-order and.
[54]
[PDF] Automorphism groups, isomorphism, reconstruction (Chapter 27 of ...
Jun 12, 1994 · In fact, their automorphism group often coincides with their group of definition (see the ... Each of these two hypergraphs is uniform by ...
[55]
(PDF) Hypergraph Automorphims - ResearchGate
Oct 27, 2020 · Our results constitute a general theory of automorphisms for oriented hypergraphs and describe the effect of automorphism group structure on ...
[56]
Complexity of Acyclic Hypergraph Isomorphism
Dec 12, 2018 · To complete the answer by Holf, it is claimed here DAM 145(3) that isomorphism is GI-complete in β-acyclic hypergraphs.Strongly Regular Graph and GI-CompletenessWhat evidence is there that Graph Isomorphism is not in $PMore results from cstheory.stackexchange.com
[57]
[1405.1649] Distributed Symmetry Breaking in Hypergraphs - arXiv
May 7, 2014 · In this paper, we study the distributed complexity of symmetry breaking in hypergraphs by presenting distributed randomized algorithms for a variety of ...Missing: computations | Show results with:computations
[58]
[PDF] Hypergraphs: connection and separation - arXiv
May 28, 2015 · The hypersubgraph of H induced by V / is called a connected component of H. We denote the number of connected components of H by ω(H).
[59]
(PDF) Line Hypergraphs: A Survey - ResearchGate
Aug 5, 2025 · A line hypergraph transforms each hyperedge into a vertex, connecting vertices via hyperedges that share at least one original vertex (cf. [39] ...
[60]
(PDF) A Method for Identifying Critical Elements of a Cyber-Physical ...
... is defined as a star. section hypergraph of. H. induced by. i. v. and its connected. edges.. Degree. Ci. is the degree of. i. v. , defined as the. number of ...
[61]
Upper transversals in hypergraphs - ScienceDirect.com
A subset of vertices in a hypergraph is a transversal (also called hitting set or vertex cover or blocking set in many papers) if has a nonempty intersection ...
[62]
https://epubs.siam.org/doi/10.1137/18M117741X
[63]
https://optimization-online.org/wp-content/uploads/2016/09/5652.pdf
[64]
[1711.07442] On tight cycles in hypergraphs - arXiv
Nov 20, 2017 · A tight k-uniform \ell-cycle, denoted by TC_\ell^k, is a k-uniform hypergraph whose vertex set is v_0, \cdots, v_{\ell-1}, and the edges are all the kMissing: definition seminal
[65]
On Tight Cycles in Hypergraphs - SIAM.org
A tight $k$-uniform $\ell$-cycle, denoted by $TC_\ell^k$, is a $k$-uniform hypergraph whose vertex set is $v_0, \ldots, v_{\ell-1}$, and the edges are all ...Missing: origin | Show results with:origin
[66]
[PDF] The Multilinear polytope for acyclic hypergraphs - Optimization Online
Let G = (V,E) be a hypergraph. The most restrictive type of acyclicity in hypergraphs is Berge-acyclicity. A hypergraph is Berge-acyclic when it contains no ...
[67]
General lemmas for Berge–Turán hypergraph problems
In this paper we prove two general lemmas concerning the maximum size of a Berge-free hypergraph and use them to establish new results and improve several old ...
[68]
Hamilton cycles in hypergraphs below the Dirac threshold
We also consider tight Hamilton cycles in k-uniform hypergraphs H for k ≥ 3 , giving a series of reductions to show that it is NP-hard to determine whether a k ...Missing: detecting | Show results with:detecting
[69]
[PDF] A Leisurely Introduction to Simplicial Sets
Abstract. Simplicial sets are introduced in a way that should be pleasing to the formally-inclined. Care is taken to provide both the geometric intuition.
[70]
Fuzzy Graphs and Fuzzy Hypergraphs
An elementary fuzzy hypergraph. 1t = (X, &) is a juzzy hypergraph where all fuzzy edges are elementary. Definition 4.5 Let 1t = (X, n be a fuzzy hypergraph.
[71]
Minimum Cut and Minimum k-Cut in Hypergraphs via Branching ...
Apr 15, 2023 · A minimum cut (or min-cut) of the graph is a minimum weight set of edges whose removal partitions the vertices into two connected components.Missing: seminal papers
[72]
[PDF] Near-Optimal Minimum Cuts in Hypergraphs at Scale - arXiv
Apr 30, 2025 · The hypergraph minimum cut problem aims to partition its vertices into two blocks while minimizing the total weight of the cut hyperedges.
[73]
Generalized fuzzy hypergraph for link prediction and identification of ...
Mar 15, 2024 · In a recent study, the present authors explored soft hypergraph to model global interactions in social media networks (Amini et al., 2022).Missing: seminal | Show results with:seminal
[74]
[PDF] INTRODUCTION TO RANDOM GRAPHS
Sep 1, 2025 · The cited paper deals with random hypergraphs and here we describe the simpler case of random graphs. Page 213. 9.5. Gn,r VERSUS Gn,p. 199.
[75]
[PDF] Connectivity of random hypergraphs with a given hyperedge size ...
Jul 11, 2022 · This paper studies random hypergraphs with varying hyperedge sizes, finding a threshold for connectivity and that average size characterizes it ...
[76]
[PDF] Hypergraph Ego-networks and Their Temporal Evolution - arXiv
Dec 7, 2021 · how they evolve over time. In this paper, we propose the study of hypergraph ego- networks, a structure that can be used to model higher-order.
[77]
[PDF] Temporal Hypergraph Motifs
Dec 16, 2022 · Temporal properties observed commonly in various time-evolving hypergraphs include (a) significant overlaps between temporally adjacent ...
[78]
Hypergraph p-Laplacian: A Differential Geometry View
Apr 29, 2018 · In this paper, we generalize the analogy between graph Laplacian and differential geometry to the hypergraph setting, and propose a novel ...Missing: 2018-2020 seminal
[79]
Hypergraph $p$-Laplacian equations for data interpolation ... - arXiv
Nov 19, 2024 · The simplified p-Laplacian equation suppresses spiky solutions in data interpolation and improves classification accuracy in semi-supervised learning.Missing: 2018-2020 seminal
[80]
[PDF] Old and New Proofs of the Erdős - UCSD Math
The Erdös Ko Rado Theorem is a central result of combinatorics which opened the way for the rapid development of extremal set theory. Proofs of it are reviewed ...
[81]
https://arxiv.org/abs/0710.3032
[82]
[PDF] Transversal Numbers for Hypergraphs Arising in Geometry
May 21, 2001 · Helly's theorem asserts that if F is a finite family of convex sets in Rd in which every d + 1 or fewer sets have a point in common then T F ...
[83]
[PDF] Hypergraph regularity and the multidimensional Szemerédi theorem
Very roughly, the regularity lemma asserts that every graph can be decomposed into a few pieces, almost all of which are random-like. The precise statement is ...
[84]
Hypergraph regularity and the multidimensional Szemerédi theorem
Oct 16, 2007 · Abstract: We prove analogues for hypergraphs of Szemerédi's regularity lemma and the associated counting lemma for graphs.
[85]
[PDF] 1 BALANCED INCOMPLETE BLOCK DESIGNS
In this introduction, we give some basic definitions, establish standard nota- tion, and present some fundamental "classical" results in combinatorial design.
[86]
[PDF] Characterization Tensors of Balanced Incomplete Block Designs
Aug 11, 2015 · A k-uniform hypergraph is called a r-regular k-uniform hypergraph if the degrees of its vertices are the same as r [3, 8]. Thus, a (v, k, λ)- ...
[87]
[PDF] DENSE ARRANGEMENTS ARE LOCALLY VERY ... - UBC Math
The Szemerédi–Trotter theorem [Combinatorica, 3 (1983), pp. 381–392] gives a bound on the maximum number of incidences between points and lines on the Euclidean ...
[88]
On the Desirability of Acyclic Database Schemes - ACM Digital Library
On the Desirability of Acyclic Database Schemes. Authors: Catriel Beeri.
[89]
Properties of acyclic database schemes - ACM Digital Library
Algorithms for acyclic database schemes. VLDB '81: Proceedings of the seventh international conference on Very Large Data Bases - Volume 7.
[90]
[PDF] A Tractable hypergraph properties for constraint satisfaction and ...
An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure ...
[91]
Multilevel hypergraph partitioning: application in VLSI domain
In this paper, we present a new hypergraph partitioning algorithmthat is based on the multilevel paradigm. In the multilevel paradigm,a sequence of ...Missing: channel routing
[92]
Identifying the Minimal Transversals of a Hypergraph and Related ...
The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance<|separator|>
[93]
[PDF] Inapproximability of H-Transversal/Packing - DROPS
We prove that if H is 2-connected, H-Transversal and H-Packing are almost as hard to approximate as general k-Hypergraph Vertex Cover and k-Set Packing, so it ...
[94]
Managing polyglot systems metadata with hypergraphs
In this paper, we propose a hypergraph-based approach for representing the catalog of metadata in a polyglot system.Missing: post- | Show results with:post-
[95]
HyperGCN: A New Method of Training Graph Convolutional ... - arXiv
Sep 7, 2018 · We propose HyperGCN, a novel GCN for SSL on attributed hypergraphs. Additionally, we show how HyperGCN can be used as a learning-based approach.
[96]
A Survey on Hypergraph Neural Networks: An In-Depth and Step-By ...
Aug 24, 2024 · We present the first survey dedicated to HNNs, with an in-depth and step-by-step guide. Broadly, the present survey overviews HNN architectures, training ...
[97]
Higher-order motif analysis in hypergraphs | Communications Physics
Apr 5, 2022 · Here we systematically investigate higher-order motifs, defined as small connected subgraphs in which vertices may be linked by interactions of any order.<|control11|><|separator|>
[98]
Spectral Clustering based on the 1-Laplacian - arXiv
Apr 30, 2023 · We propose a flexible framework for defining the 1-Laplacian of a hypergraph that incorporates edge-dependent vertex weights.
[99]
Hypergraphs with edge-dependent vertex weights: p-Laplacians ...
We study p-Laplacians and spectral clustering for a recently proposed hypergraph model that incorporates edge-dependent vertex weights (EDVW).Preliminaries · EDVW-based submodular... · Spectral clustering based on...
[100]
Traffic Anomaly Detection based on Spatio-Temporal Hypergraph ...
Traffic Anomaly Detection based on Spatio-Temporal Hypergraph Convolution Neural Networks ... biological sciences, medical diagnosis, surveillance, and traffic ...
[101]
Hypergraphs and centrality measures identifying key features in ...
Conclusion 1. This 1 -line graph also identifies an anomaly, a single gene ... Hypergraph models of biological networks to identify genes critical to pathogenic ...
[102]
A hypergraph transformer method for brain disease diagnosis
Nov 13, 2024 · This paper proposes a hypergraph transformer method for modeling high-order correlations between functional and structural brain networks.