Hasse Diagrams

Hasse diagrams are the default visualization whenever a finite partial order needs to be understood structurally rather than merely listed as pairs. In abstract algebra, subgroup lattices and subfield lattices (e.g. in Galois theory, where the Hasse diagram of intermediate fields is dual to the Hasse diagram of subgroups) are drawn and reasoned about directly as covering diagrams. In combinatorics, Young's lattice (partitions ordered by containment of Young diagrams) and the Boolean lattice $\mathcal P(S)$ underlie generating-function and representation-theoretic arguments, and both are routinely manipulated via their Hasse diagrams. In computer science, Hasse diagrams model dependency orders: task scheduling (a task must finish before its covers can start), version-control commit DAGs restricted to covering edges, and type hierarchies in object-oriented programming, where the diagram shows only direct subtype/supertype links. In cryptography and coding theory, the subset-lattice structure underlying secret-sharing schemes and access structures is described by Hasse diagrams of authorized coalitions. In statistics and data science, ROC-like dominance relations and Pareto-optimality frontiers (multi-objective optimization) are organized as posets whose Hasse diagrams show the immediate dominance structure among candidate solutions. In every one of these, the same theorem underlies the practice: for a finite poset, drawing only the covers loses no information at all, so the diagram is simultaneously the cleanest and the most complete picture available.

Ask the tutor: How do Hasse diagrams reveal whether a poset is a lattice, and what does that look like in the divisor-of-60 example above?

Think of a poset as a "who dominates whom" relation, and imagine trying to draw every single relation as an arrow. If $1 \mid 2 \mid 4 \mid 8$, drawing $1 \to 4$ and $1 \to 8$ and $2\to 8$ on top of the chain $1\to2\to4\to8$ adds nothing: once the diagram has $1\to2$, $2\to4$, $4\to8$, every other relation among these four is forced by transitivity. The covering relation keeps exactly the "atomic steps" — the edges that cannot be explained away as a shortcut over some intermediate element — and throws away everything transitivity would reconstruct anyway. The upward convention replaces arrowheads with geometry: since we agree that a diagram is always read "bigger is higher," a plain undirected segment between two dots unambiguously tells us which one is the bigger element. This is why Hasse diagrams look like scaffolding or lattices of dots and struts — they are literally recording only the direct steps of the order, laid out so height itself encodes comparison.

Notice the edge $1 \to 3$ appears but $1 \to 6$ does not, even though $1 \mid 6$: it is omitted because $1 \mid 2 \mid 6$ and $1 \mid 3 \mid 6$ each give an intermediate divisor, so $1$ does not cover-relate to $6$ directly. Similarly $1 \mid 4$ is implied by the path $1 \to 2 \to 4$, so no direct edge is drawn.

Example 1: Divisors of 60, ordered by divisibility. Let $P = \{1,2,3,4,5,6,10,12,15,20,30,60\}$, the twelve divisors of $60 = 2^2 \cdot 3 \cdot 5$, ordered by $a \le b \iff a \mid b$. We build the Hasse diagram by computing covers directly from the definition, not by guessing. First, note $a \lessdot b$ in this poset iff $a \mid b$ and $b/a$ is prime. Indeed, if $b/a$ is prime, any $z$ with $a < z < b$ and $a \mid z \mid b$ would force $z/a$ to be a nontrivial divisor of the prime $b/a$, impossible. Conversely if $b/a$ is composite, say $b/a = pq$ with $p$ prime and $q>1$, then $z = ap$ satisfies $a < z < b$, so $a$ does not cover $b$. Applying this criterion:

• $1 \lessdot 2, \ 1 \lessdot 3, \ 1 \lessdot 5$ (ratios $2,3,5$ are prime).
• $2 \lessdot 4, \ 2\lessdot 6, \ 2 \lessdot 10$ (ratios $2,3,5$).
• $3 \lessdot 6, \ 3 \lessdot 15$ (ratios $2,5$); note $3 \lessdot 9$ would need $9 \mid 60$, false, so no edge there.
• $5 \lessdot 10, \ 5 \lessdot 15$ (ratios $2,3$).
• $4 \lessdot 12, \ 4 \lessdot 20$ (ratios $3,5$).
• $6 \lessdot 12, \ 6\lessdot 30$ (ratios $2,5$).
• $10 \lessdot 20, \ 10 \lessdot 30$ (ratios $2,3$).
• $15 \lessdot 30$ (ratio $2$).
• $12 \lessdot 60, \ 20 \lessdot 60, \ 30 \lessdot 60$ (ratios $5,3,2$).

Count the covering pairs: $3 + 3 + 2 + 2 + 2 + 2 + 2 + 1 + 3 = 20$ covering edges. Notice what is excluded: $1$ and $4$ are related ($1\mid 4$) but not a cover, since $2$ sits strictly between; likewise $1$ and $60$ are related but nowhere near a cover. The diagram is the familiar "cube-like" shape of the divisor lattice of $2^2 \cdot 3\cdot 5$: three prime directions, exponent range $\{0,1,2\}$ for $2$ and $\{0,1\}$ for $3,5$, giving $3\times2\times2=12$ elements arranged as a $3\times2\times2$ grid — a rectangular box graph — matching our twelve divisors exactly.

Example 2: The power set of $\{a, b, c\}$ ordered by inclusion. Let $P = \mathcal{P}(\{a,b,c\})$, the $2^3 = 8$ subsets of $\{a,b,c\}$, ordered by $\subseteq$. We claim $X \lessdot Y$ iff $X \subsetneq Y$ and $|Y \setminus X| = 1$, i.e. $Y$ is obtained from $X$ by adding exactly one element. Proof of the criterion. If $|Y\setminus X|=1$, say $Y = X \cup \{e\}$, suppose $X \subsetneq Z \subsetneq Y$. Then $Z \setminus X$ is a nonempty proper subset of $Y \setminus X = \{e\}$, impossible since $\{e\}$ has no nonempty proper subset. So no such $Z$ exists and $X \lessdot Y$. Conversely if $|Y \setminus X| \ge 2$, pick $e \in Y\setminus X$ and set $Z = X \cup \{e\}$; then $X \subsetneq Z \subsetneq Y$ (strict on the right since $Y\setminus X$ has another element besides $e$), so $X$ does not cover $Y$. Listing the eight subsets by size (rank) $0,1,1,1,2,2,2,3$:

Covers go exactly between consecutive ranks with single-element difference: $\varnothing$ covers into each of the three singletons ($3$ edges); each singleton covers into the two doubletons containing it ($3\times2=6$ edges); each doubletons covers into the single top set ($3$ edges). Total $3+6+3=12$ covering edges — this is the familiar cube graph $Q_3$, and indeed the Hasse diagram of $\mathcal P(\{a,b,c\})$ is literally the graph of a 3-dimensional cube, with $\varnothing$ at the bottom vertex and $\{a,b,c\}$ at the top vertex. Observe again what is suppressed: $\varnothing \subseteq \{a,b\}$ holds but is not an edge, since $\{a\}$ (or $\{b\}$) sits strictly between. There are $\binom{3}{0}+\binom31\binom21+\binom32\cdot0$… more simply: the total number of related pairs $X \subsetneq Y$ in $\mathcal P(\{1,2,3\})$ is $3^3 - 2^3 = 27-8=19$ (each element independently in "only $Y$," "both," or "neither," minus the cases where no element is in "only $Y$"), yet only $12$ of these are covers — the diagram discards more than a third of the relation as redundant, exactly as the theorem promises it can, safely.