Topological sort of partial order into sorted sets - MathOverflow

Topological sort of partial order into sorted sets

2011-04-14T22:47:12Z

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:

for $i = 1 \ldots k-1$, $\exists e_1 \in S_i,e_2 \in S_{i+1}$ s.t. $e_1 < e_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.

Answer by Omar Antolín-Camarena for Topological sort of partial order into sorted sets

2011-04-14T23:00:12Z

EDIT: This answer was for a previous version of the question.

There is usually no such list: consider the case where some element is incomparable to everything else.

Answer by Johan Wästlund for Topological sort of partial order into sorted sets

2011-04-15T11:03:58Z

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.