# Topological sort of partial order into sorted sets

Given a partial order of elements, one can use topological sorting to produce a sorted list of elements. For example, if we have the partial order A->B and A->C, then the possible topological sort results are [A,B,C] and [A,C,B].

I am interested in producing a sorted list of sets [$S_1, \ldots, S_k$] that satisfy the partial order. (The sets $S_i$ partition the elements.) Here, the requirements are:

1. for $i = 1 \ldots k-1$, $\exists e_1 \in S_i,e_2 \in S_{i+1}$ s.t. $e_1 < e_2$

2. for each set $S_i$, $\nexists e_1, e_2 \in S_i$ such that $e_1 < e_2$ or $e_2 < e_1$

In our example, the only correct sorted list of sets is [{A},{B,C}]. Given a partial order, how many possible sorted lists of sets exist? Is there a name for this kind of sorting? Any pointers are appreciated.

• It is not clear whether the sets S_i form a partition of your original set. If they do, then (I think) you are looking for homomorphic images of your partial order, and that is bounded by the number of partitions of the set. If you allow an element to belong to different S_i, that changes things, but may still be tied to homomorphic images of the original partial order for connected partial orders. Gerhard "Ask Me About System Design" Paseman, 2011.04.14 Apr 14 '11 at 23:11
• Thanks for the reply. Yes, I meant S_i to form a partition. BTW, I have rewritten condition 1. Apr 14 '11 at 23:24
• This new version doesn't really sound like it's "sorted": look at the partial order A<B, C<D with no other comparable pairs; then [{A,D},{B,C}] satisfies the conditions even though D occurs in an earlier set than C. Apr 15 '11 at 23:03

We can take $S_1$ to be the set of minimal elements, then remove those and proceed inductively. Or go in the other direction, pealing off the maximal elements first. So in any case such lists do exist.