0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Apr 14, 2011 at 23:11
  • $\begingroup$ Thanks for the reply. Yes, I meant S_i to form a partition. BTW, I have rewritten condition 1. $\endgroup$
    – Steven
    Apr 14, 2011 at 23:24
  • $\begingroup$ 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. $\endgroup$ Apr 15, 2011 at 23:03

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Apr 14, 2011 at 23:18
  • $\begingroup$ 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 $\endgroup$ Apr 14, 2011 at 23:21
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Apr 14, 2011 at 23:39
  • $\begingroup$ I think Gerhard truly means pentagon. A->B, B->C, C->D, A->E, and E->D. $\endgroup$ Apr 14, 2011 at 23:50
  • $\begingroup$ But in the pentagon with the notation in my previous comment, [{A}, {B,E}, {C}, {D}] seems to satisfy the requirements. $\endgroup$ Apr 14, 2011 at 23:54
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.