📂Graph Theory

Definition of Hypergraph

Definition

1. A finite set $V \ne \emptyset$ is called a Hypervertex Set.
2. A Hyperedge refers to a subset of a hypervertex set, and the set of hyperedges $E$ is called a Hyperedge Set. In other words, a hyperedge set can be defined as a subset $E \subset 2^{V}$ of the power set of a hypervertex set.
3. The pair of hypervertices and hyperedges $G = (V, E)$ is called a Hypergraph.

Explanation ¹

Simply put, a hypergraph extends beyond the concept of a graph, which is interested in ‘relationships between two entities’, to encompass ‘relationships among multiple parties’. For example, in a social network, if $A$ and $B$, and $B$ and $C$ meet individually, but all three meet when $B$ is present even if $A, C$ do not meet otherwise, then $A, B, C$ is considered to be bound by a hyperedge of cardinality $3$.

As can be inferred from its broad definition, hypergraphs are less a generalization of graphs and more a novel representation of what we call sets or data. Unlike graphs, which can be visualized with points and lines, hypergraphs are not as straightforward to conceptualize and, conversely, can offer new perspectives on complex subjects.

While hypergraphs are certainly gaining attention in applied mathematics, theoretical research on hypergraphs themselves is said to be challenging to extend while maintaining the framework of graph theory. It’s understandable, considering that even concepts as basic as adjacency matrices would require tensors to be properly expressed.