Ma · Mathematics

How to Find Topological Orderings of a Divisibility Poset

Published By the 9to5Science editorial team

At a glance

  1. 1. Identify the order

    For positive integers, a is below b when a divides b.

  2. 2. Write the constraints

    Place a before b whenever a divides b and a is different from b.

  3. 3. Choose a minimal element

    Add an element with no remaining predecessors, then remove it from consideration.

  4. 4. Repeat and check

    Continue until every element is listed; different valid choices can give different orderings.

Advertisement

A topological ordering of a partially ordered set is a way to list its elements without violating the order relation. For the divisibility poset (A,∣)(A,\mid), the relation is that aa is below bb when aa divides bb. Thus each divisor must appear before the multiple it divides.

The title does not specify which set AA is being used, so there is no single ordering to list. The method below works for any finite AA of positive integers, followed by a concrete example.

What the ordering must satisfy

Assume AA is a finite set of positive integers and define the order by divisibility. A topological ordering is a sequence containing every element of AA exactly once such that

a∣b and a≠b⟹a appears before b.a\mid b\text{ and }a\ne b\quad\Longrightarrow\quad a\text{ appears before }b.

For example, if 2,4∈A2, 4\in A, then 22 must precede 44, because 2∣42\mid4. If neither a∣ba\mid b nor b∣ab\mid a, 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 aa to bb when aa must come before bb. 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 AA. 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

A={1,2,3,4,6,12}.A=\{1,2,3,4,6,12\}.

The divisibility constraints include 11 before every other element, 22 before 44 and 66, 33 before 66, and both 44 and 66 before 1212. Since 11 is the only element that must precede all the others, it must come first. Since every element of AA divides 1212, except that 1212 itself is not required to precede itself, 1212 must come last.

The remaining elements 2,3,4,62,3,4,6 must be arranged so that 22 comes before 44 and 66, and 33 comes before 66. These constraints allow five arrangements:

  • 2,3,4,62,3,4,6
  • 2,3,6,42,3,6,4
  • 2,4,3,62,4,3,6
  • 3,2,4,63,2,4,6
  • 3,2,6,43,2,6,4

Putting the forced first and last elements back gives the five topological orderings:

1,2,3,4,6,121,2,3,6,4,121,2,4,3,6,121,3,2,4,6,121,3,2,6,4,12.\begin{aligned} &1,2,3,4,6,12\\ &1,2,3,6,4,12\\ &1,2,4,3,6,12\\ &1,3,2,4,6,12\\ &1,3,2,6,4,12. \end{aligned}

For instance, 1,2,4,3,6,121,2,4,3,6,12 is valid: each number appears before every distinct multiple of it that belongs to AA. The relative position of 33 and 44 can vary because neither divides the other.

Common mistakes

  • Reversing the relation. If a∣ba\mid b, then aa comes before bb, 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, 22 must precede 1212 even if other numbers appear between them.
  • Including self-divisibility as a constraint. Since a∣aa\mid a, 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 aa, both a∣−aa\mid -a and −a∣a-a\mid a hold. Thus, if AA contains both aa and −a-a for some nonzero aa, 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 (A,∣)(A,\mid), first write down the elements of AA; those determine which choices and resulting orderings are possible.

References

  1. 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.