Discrete Math › Section C · Graph theory › Topic C.12

Partial orders

Some things can be ranked and some cannot. A course can require another, a file can depend on another, one set can sit inside another, yet many pairs are simply unrelated. Partial orders describe this kind of ranking precisely, and topological sorting turns one into a workable schedule.

Rankings with gaps

Take the courses in a degree programme and say one comes before another if it is a prerequisite, directly or through a chain. Introductory programming comes before data structures, which comes before algorithms. But a history elective and a statistics course may have no connection at all: neither comes before the other. Ordinary numbers never behave like that, since of two different numbers one is always smaller. A partial order is an ordering that allows such gaps, and it appears wherever there are dependencies, inclusions or priorities that only sometimes apply.

The definition

A partial order on a set \(A\) is a relation that is reflexive, antisymmetric and transitive, the properties from the topic on relations. A set with a partial order is a partially ordered set, or poset, and the order is often written \(\preceq\). Three standard examples: \(\le\) on the real numbers; \(\subseteq\) on the subsets of a set; and "divides" on the positive integers, where \(a \mid b\) means \(b\) is a whole-number multiple of \(a\). Antisymmetry is what separates a partial order from an equivalence relation: two different elements are never each below the other. The strict version, such as \(<\), drops the reflexive pairs, so under this definition it is not itself a partial order.

Comparable and incomparable

Two elements \(a\) and \(b\) are comparable if \(a \preceq b\) or \(b \preceq a\), and incomparable otherwise. Under "divides", 3 and 12 are comparable, but 4 and 6 are not: neither divides the other. Under \(\subseteq\), the sets \(\{1\}\) and \(\{2\}\) are incomparable. A total order, also called a linear order, is a partial order in which every pair is comparable, such as \(\le\) on the real numbers or alphabetical order on words. A chain is a set of pairwise comparable elements, and an antichain is a set of pairwise incomparable ones, such as \(\{4, 6, 9\}\) under "divides".

Hasse diagrams

Drawing every pair of a partial order as an arrow makes a cluttered picture, so we draw only what is essential. Say \(b\) covers \(a\) when \(a \prec b\) and nothing lies strictly between them. A Hasse diagram draws each element as a dot, places \(b\) higher than \(a\) whenever \(a \prec b\), and draws a line only for each covering pair. Loops are left out because reflexivity supplies them, and shortcuts are left out because transitivity supplies them. Since direction is shown by height, no arrowheads are needed: to read off \(a \preceq b\), look for an upward route from \(a\) to \(b\).

Worked example: divisors of 12

Draw the Hasse diagram of the divisors of 12, ordered by "divides". 1. The elements are 1, 2, 3, 4, 6 and 12. 2. The full relation has 18 pairs, including 6 loops. 3. Find the covers: 1 is covered by 2 and 3; 2 is covered by 4 and 6; 3 by 6; 4 and 6 by 12. Pairs such as 1 and 12, or 2 and 12, are left out because a route already passes through 4 or 6. 4. The diagram has 7 lines in four levels: 1 at the bottom; 2 and 3; 4 and 6; 12 at the top. 5. Check with an incomparable pair: 4 and 6 sit side by side, with no upward route between them.

Maximal, greatest, minimal, least

An element is maximal if nothing lies strictly above it, and greatest if everything lies at or below it. A greatest element is always maximal, and there is at most one, but a poset can have several maximal elements and no greatest. Minimal and least are defined the same way, looking downwards. Among the subsets of \(\{1, 2, 3\}\) under \(\subseteq\), the empty set is least and \(\{1, 2, 3\}\) is greatest. Among the divisors of 12, 1 is least and 12 is greatest. The next card shows a poset with neither.

Worked example: several maximal elements

Order \(\{2, 3, 4, 6, 8, 9\}\) by "divides". 1. Covering pairs: 2 is below 4 and 6; 3 is below 6 and 9; 4 is below 8. 2. Maximal elements: 6, 8 and 9, since none of them divides another element of the set. 3. Minimal elements: 2 and 3, since nothing else in the set divides them. 4. There is no greatest element: 6, 8 and 9 are pairwise incomparable, so no single element sits above all three. Likewise there is no least element, because 2 and 3 are incomparable. 5. Adding 72, a multiple of both 8 and 9, would create a greatest element.

Topological sorting

A topological sort lists the elements of a finite poset in a single sequence so that whenever \(a \prec b\), \(a\) comes before \(b\). It extends the partial order to a total order. Every finite poset has one, and a set of tasks has one exactly when its dependency graph has no directed cycle; a cycle such as A before B before A could never be scheduled. To build one, repeatedly list any element with nothing remaining below it, then remove it. Build systems compile files this way, spreadsheets recalculate cells this way, and package managers install software this way.

Worked example: scheduling courses

Course I comes before D and M; M comes before A; D comes before A and B. 1. Only I has no prerequisite, so list I first and remove it. 2. Now D and M are both free; choose D. 3. M and B are free; choose M. 4. A and B are free; choose B, then A. One valid order is I, D, M, B, A. 5. The choices in steps 2 to 4 mean there are several valid orders, 5 in all: I, D, M, A, B; I, D, M, B, A; I, D, B, M, A; I, M, D, A, B; and I, M, D, B, A. Any order with A before M, or B before D, breaks a prerequisite.

Lattices

An upper bound of \(a\) and \(b\) is an element at or above both, and their join is the least upper bound, if it exists. Lower bounds and the meet, the greatest lower bound, are defined the same way. A lattice is a poset in which every pair has both a join and a meet. Subsets under \(\subseteq\) form a lattice, with union as join and intersection as meet. Positive integers under "divides" form one with lcm as join and gcd as meet: the join of 4 and 6 is 12 and their meet is 2. But \(\{1, 2, 3\}\) under "divides" is not a lattice, because 2 and 3 have no upper bound in it.

Common mistakes to avoid

First, drawing transitive shortcuts or loops in a Hasse diagram; draw covering pairs only. Second, confusing maximal with greatest: \(\{2, 3, 4, 6, 8, 9\}\) has three maximal elements and no greatest. Third, treating a partial order as total, by assuming two elements must be comparable. Fourth, mixing up antisymmetric with "not symmetric" when checking the definition. Fifth, expecting a unique topological sort; there are usually many, and none exists if dependencies form a cycle.

Key takeaways

A partial order is reflexive, antisymmetric and transitive; a poset may contain incomparable pairs, and a total order has none. Hasse diagrams show only covering pairs, with larger elements higher. Maximal and minimal elements can be many; greatest and least elements, if they exist, are unique. A topological sort lists the elements so that every relation points forwards, and exists exactly when dependencies have no cycle. In a lattice every pair has a join and a meet, such as lcm and gcd for divisibility.

Flashcards

Flashcard

Partial order

A relation that is reflexive, antisymmetric and transitive

Some pairs may be incomparable.

Test your understanding

Question 1 of 5

Which relation is a partial order but not a total order?

Question 2 of 5

What are the maximal elements of {2, 3, 4, 6, 8, 9} ordered by "divides"?

Question 3 of 5

How many lines does the Hasse diagram of the divisors of 12, ordered by "divides", contain?

Question 4 of 5

Tasks: A before C, B before C, C before D, and B before E. Which order is a valid topological sort?

Question 5 of 5

Which statement about the subsets of {1, 2, 3} ordered by ⊆ is true?

← Previous topicNext topic →