Graph Theory · Mathematics

Hypergraphs: Introduction

Graph theory is the study of graphs, which can be used to model relationships, routes, etc. People understands a lot about graphs. However, there is a generalisation of graph theory that we can talk about – the hypergraphs!
Like graph theory, hypergraphs contains vertices, denoted by V, and edges which we call hyperedges, denoting E. Instead of connecting two vertices u,v \in V, a hyperedge e \in E connects any subset of V, i.e. e is an element of the power set of the vertices.

Intuitively, hypergraphs are just a set of vertices, and hyperedges are lines that connects some vertices together. For instance, the n \times n grid is a hyper graph, with n^2 vertices and 2n hyperedges. In the n \times n grid, each pair of hyperedges, e,e' \in E intersects at a vertex v \in V uniquely. Another example of a hypergraph is the Fano plane, which is the hypergraph below

Fano Plane

As we can see, there are seven vertices in total in the hypergraph above. There are also seven hyperedges in the hypergraph above, each hyperedge is represented by a unique colour itself.

We can also talk about the properties of a hypergraph just as we do in normal graphs. Recall that in a graph, we say that a graph is k-regular if each vertex has exactly degree k. Similarly, a hypergraph is k-regular if for each vertex in the hypergraph, the degree of the vertex (number of lines that pass through a vertex) is exactly degree k. So a n \times n-grid is 2-regular, and the Fano plane is 3-regular.

Another interesting property that we want to inherit from graph theory is the dual. Amazingly, basic properties of duality that we learn from normal graph theory is also true for hypergraphs. Perhaps the most important such property is that G^{**} \cong G for any hypergraph G, where G^* denotes the dual graph of the graph G. This is another post for another time.

There are many other types of hypergraphs, and they are used in many ways. Hopefully this post helps you with some intuition in hypergraphs.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s