A brief note on Hypergraphs

Mahdi
2 min readOct 31, 2021

Graphs in a traditional sense are made up of vertices and edges. Edges establish connections between two vertices. Graphs provide an abstraction layer that allows us to map out relationships between objects. These objects can represent taxis, train stops, people, grocery items, etc. Furthermore, we have the ability to assign attributes to nodes which paves the way for establishing more complex relationships.

Mapping out complex real-world relationships into pairwise ones can lead to the loss of important connections. One way of moving beyond pairwise relationships in graphs is to use a generalized version called a hypergraph. This new kind of graph is made up of vertices and edges, but the one major difference is that edges in hypergraphs are connected to multiple vertices. This mechanism allows hypergraphs to map out complex relationships that depend on each other for existence. Figure 1 shows an example of a hypergraph.

Figure 1: Hypergraph

Edges include:

e_1 = {v1, v2, v3}

e_2 = {v2, v3}

e_3 = {v3, v6, v5}

e_4 = {v4}

Hypergraphs' ability to map out complex relationships has led researchers in a wide variety of fields to take advantage of them. From studying quantom entanglement to mapping out movement of taxis in New York city to core data structures used by computer scientists we can find footprints of hypergraphs. This level of adoption in the scientific community shows the power of hypergraphs in modeling complexity and providing a mechanism for the extraction of subtle details traditional graphs miss out on.

--

--