How to Find Topological Orderings of a Divisibility Poset
At a glance
- 1. Identify the order
For positive integers, a is below b when a divides b.
- 2. Write the constraints
Place a before b whenever a divides b and a is different from b.
- 3. Choose a minimal element
Add an element with no remaining predecessors, then remove it from consideration.
- 4. Repeat and check
Continue until every element is listed; different valid choices can give different orderings.
A topological ordering of a partially ordered set is a way to list its elements without violating the order relation. For the divisibility poset , the relation is that is below when divides . Thus each divisor must appear before the multiple it divides.
The title does not specify which set is being used, so there is no single ordering to list. The method below works for any finite of positive integers, followed by a concrete example.
What the ordering must satisfy
Assume is a finite set of positive integers and define the order by divisibility. A topological ordering is a sequence containing every element of exactly once such that
For example, if , then must precede , because . If neither nor , the poset does not require one of them to precede the other; either order may work, as long as all other constraints are respected.
A finite poset can be represented by a directed acyclic graph: draw an arrow from to when must come before . A topological ordering of the graph is exactly a linear extension of the poset. For divisibility, it is enough to include arrows for the required comparisons; arrows for every divisor–multiple pair or just the immediate comparisons produce the same valid orderings.
A reliable way to construct an ordering
Repeatedly choose an element that has no unlisted predecessor. In the divisibility poset, this means choosing a remaining number that is not divisible by any other remaining, distinct element of . Add that number next in the list, remove it from the remaining set, and repeat.
This procedure works because a minimal remaining element has no required earlier element left to place. At least one such element exists in every nonempty finite poset. If there are several choices, each can lead to a different topological ordering.
Worked example
Let
The divisibility constraints include before every other element, before and , before , and both and before . Since is the only element that must precede all the others, it must come first. Since every element of divides , except that itself is not required to precede itself, must come last.
The remaining elements must be arranged so that comes before and , and comes before . These constraints allow five arrangements:
Putting the forced first and last elements back gives the five topological orderings:
For instance, is valid: each number appears before every distinct multiple of it that belongs to . The relative position of and can vary because neither divides the other.
Common mistakes
- Reversing the relation. If , then comes before , not after it.
- Assuming the ordering is unique. A partial order usually leaves incomparable elements free to switch places. The example has five valid orderings.
- Checking only consecutive pairs. The requirement applies to every comparable pair. For example, must precede even if other numbers appear between them.
- Including self-divisibility as a constraint. Since , the relation is reflexive, but this does not mean an element must appear before itself. Topological-sort graphs omit these self-loops.
- Ignoring the domain. Divisibility is a partial order on positive integers. On all integers, divisibility is not antisymmetric: for any nonzero integer , both and hold. Thus, if contains both and for some nonzero , the restricted relation is not a poset in the standard sense.
If you need every ordering
A topological-sort algorithm can produce one ordering, but to list all of them you must branch whenever there is more than one eligible minimal element. For each choice, place it next and continue recursively. To answer for a particular , first write down the elements of ; those determine which choices and resulting orderings are possible.
References
- Combinatorics and Partially Ordered Sets: Dimension Theory — William T. Trotter
Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.