Hasse Diagrams

Since a partial order is a binary relation, it can be represented by a digraph. When we deal with a partial order, we know that the relation must be reflexive, transitive, and antisymmetric. This allows to simplify the graphical representation of a partially ordered set by taking the following steps:

• Remove all self loops;
• Remove all transitive edges;
• Remove directions on edges assuming that they are oriented upwards. So if a ≼ b, then the vertex b appears above the vertex a.

The resulting graph looks far simpler and is called a Hasse diagram, named after the German mathematician Helmut Hasse (1898−1979).

As an example, consider the divisibility relation \(a \mid b\) on the set

The directed graph corresponding to this relation looks a bit messy:

We can easily convert the original digraph into a Hasse diagram by deleting all loops and transitive edges from the graph. Making sure that the terminal vertex is above the initial vertex, we also remove the arrows on the directed edges. The element \(9\) can be moved to the second level as it is an immediate successor of \(3\). Similarly, \(10\) is an immediate successor of \(2\) and \(5,\) so we also put it on the second level.

The number \(8\) remains on the \(3\text{rd}\) level as it is a direct successor of \(4.\)

The Hasse diagram of the partially ordered set \(\left( {A, \mid} \right)\) is shown in Figure \(3.\) Notice that the vertices in the Hasse diagram are represented by dots rather than by circles.

As you can see, the Hasse diagram is a useful tool which completely describes the associated partial order.