## Topological sort of partial order into sorted sets

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 – Gerhard Paseman Apr 14 2011 at 23:11
Thanks for the reply. Yes, I meant S_i to form a partition. BTW, I have rewritten condition 1.  – Steven Apr 14 2011 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. – Omar Antolín-Camarena Apr 15 2011 at 23:03

## 2 Answers

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.

-

Thanks for the answer. I just realized I did not properly formulate the problem and have fixed condition 1. So if there is an element that is incomparable to everything else, then you can place it in any existing set in the sorted list.  – Steven Apr 14 2011 at 23:18
Or consider a pentagon-shaped partial order, with one vertex having out degree 2 and indegree 0, and a vertex two edges away having indegree 2 and outdegree 0, with remaining vertices ghavin in and out degree 1.  That will not admit a partition of the desired form.  Gerhard "Ask Me About System Design" Paseman, 2011.04.14 – Gerhard Paseman Apr 14 2011 at 23:21
Hi Gerhard, I'm not completely understanding the example (you mean diamond shape, not pentagon, right?). So if we have a partial relation A->B, A->C, C->D, B->D, then I can create the sorted list [{A},{B,C},{D}]. Let me know if I got this wrong.  – Steven Apr 14 2011 at 23:39
I think Gerhard truly means pentagon.  A->B, B->C, C->D, A->E, and E->D. – Andreas Blass Apr 14 2011 at 23:50
But in the pentagon with the notation in my previous comment, [{A}, {B,E}, {C}, {D}] seems to satisfy the requirements.   – Andreas Blass Apr 14 2011 at 23:54
show 4 more comments

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 10, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8901463747024536, "perplexity_flag": "middle"}