A Hasse diagram is a graphical representation of a partially ordered set, or poset, in which elements are shown as vertices and immediate order relations are shown as upward connections. Relations that follow by transitivity are omitted, as are the reflexive relations connecting each element to itself. For a finite poset, the entire order can be recovered from the diagram by following upward paths. Named after the German mathematician Helmut Hasse, these diagrams are widely used in order theory, combinatorics, and abstract algebra.
Definition
A partially ordered set consists of a set and a binary relation that is reflexive, antisymmetric, and transitive. Write when and .
An element covers an element , written , if
Thus, a cover is an immediate step in the order, not necessarily an immediate step in a numerical scale.
A Hasse diagram is drawn according to three conventions:
- Each element of is represented by a vertex.
- A connection is drawn between and exactly when covers .
- If covers , then is placed higher than .
Connections are commonly straight line segments, although upward curves may also be used. Arrowheads are unnecessary because the upward direction indicates increasing order.
For a finite poset,
The word upward is essential: a path that alternates between upward and downward steps does not establish an order relation between its endpoints.
Reading a diagram
The vertical placement of vertices supports the drawing convention, but height alone does not determine comparability. One vertex may lie above another without an upward path connecting them.
Several important order-theoretic features can be read from a finite Hasse diagram:
- A minimal element has no element strictly below it; it has no downward cover connection.
- A maximal element has no element strictly above it; it has no upward cover connection.
- A least element lies below every element.
- A greatest element lies above every element.
Minimal and least are not interchangeable. A poset can have several minimal elements, but it can have at most one least element. The corresponding distinction holds between maximal and greatest elements.
A chain is a subset whose elements are pairwise comparable. An antichain is a subset whose distinct elements are pairwise incomparable. Vertices placed on the same horizontal level are necessarily incomparable under the usual upward drawing convention, but an antichain need not be drawn on a single level.
Crossing lines do not indicate an additional element or connection unless a vertex is explicitly marked at the crossing.
Examples
A finite total order
For the set with its ordinary numerical order, the diagram is a vertical chain:
4
|
3
|
2
|
1
Only consecutive elements are connected. Although and , those relations already follow from upward paths and therefore receive no separate edges.
Subsets ordered by inclusion
Consider the power set of , ordered by set inclusion:
{a,b}
/ \
{a} {b}
\ /
∅
The bottom vertex is the empty set, and the top vertex is . The sets and are incomparable.
More generally, for subsets of a finite set, covers precisely when is obtained from by adding one element. Subsets are therefore naturally arranged in levels according to their cardinality. This order forms a finite Boolean algebra.
Divisibility
Let
with defined to mean that divides . Its cover relations are
Here and are incomparable even though in the ordinary numerical order. The relation represented is divisibility, not numerical magnitude.
Cover relations also depend on the underlying set. Within this , covers . Within the smaller divisibility poset , covers , because no intermediate element belongs to that poset.
Connection with directed graphs
Orienting every connection upward produces a directed acyclic graph. A directed cycle would contradict the strict increase required along each edge.
For a finite poset, the directed cover graph is the transitive reduction of the directed graph containing an edge for every strict relation . Transitive reduction removes edges whose reachability is already supplied by longer directed paths. For finite directed acyclic graphs, this reduction is unique.
Conversely, any finite directed acyclic graph defines a partial order by reachability, together with equality. However, the graph is itself a Hasse diagram only after redundant edges have been removed and its vertices have been arranged consistently with the order.
The underlying undirected graph alone generally does not determine the poset. The upward orientation is part of the information conveyed by a Hasse diagram.
Lattices and algebraic applications
A lattice is a poset in which every pair has a greatest lower bound, called its meet , and a least upper bound, called its join .
In a Hasse diagram, common upper bounds are vertices reachable upward from both elements. Their join, when it exists, is the least such upper bound. The meet is defined dually using common lower bounds. These are order-theoretic properties, not measurements of geometric distance in the drawing.
For the subset example,
For the positive divisors of a fixed positive integer, ordered by divisibility, the meet is the greatest common divisor and the join is the least common multiple.
Other important uses include displaying subgroup inclusion in group theory, inclusion among ideals in ring theory, and refinement relations among set partitions. Such diagrams can reveal intermediate structures and whether particular elements are comparable.
Construction and layout
For a finite poset whose full order relation is known, a direct construction examines every strict pair . The pair is retained as an edge only if there is no satisfying
A straightforward implementation uses time for elements when individual order tests take constant time. Other methods can exploit graph structure or a more compact representation of the order.
Once the cover relations are established, a layout must place every upper endpoint above its lower endpoint. Different drawings can represent exactly the same poset: horizontal positions, edge lengths, and angles are normally not mathematical data.
Some posets admit a rank function that increases by one along every cover relation, allowing vertices to be placed in natural horizontal layers. Not every finite poset admits such a ranking. Nevertheless, every finite poset can be drawn with all cover edges directed upward.
Avoiding edge crossings is a separate problem. A Hasse diagram may require crossings, and planarity of its underlying undirected graph does not by itself guarantee a crossing-free drawing that also respects the upward order.
Infinite posets and limitations
The cover relation exists for infinite posets as well, but it need not determine the entire order.
For example, the integers under their usual order form an infinite chain in which covers . Every strict comparison can still be represented by a finite sequence of cover steps.
By contrast, the rational numbers under their usual order have no cover relations: whenever , another rational number lies strictly between them. A graph showing only covers would therefore contain no edges despite the order being total.
Thus, the familiar recovery rule using finite upward paths always works for finite posets, but requires additional conditions in infinite cases. It holds, for example, when every interval
is finite.
Even for finite orders, large diagrams can become difficult to interpret. They are effective representations of immediate order structure, but their usefulness depends on size, labeling, and layout.