Topological sort of partial order into sorted sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T09:58:22Z http://mathoverflow.net/feeds/question/61761 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61761/topological-sort-of-partial-order-into-sorted-sets Topological sort of partial order into sorted sets Steven 2011-04-14T22:47:12Z 2011-04-15T23:03:50Z <p>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]. </p> <p>I am interested in producing a sorted list of <strong>sets</strong> [$S_1, \ldots, S_k$] that satisfy the partial order. (The sets $S_i$ partition the elements.) Here, the requirements are: </p> <ol> <li><p>for $i = 1 \ldots k-1$, $\exists e_1 \in S_i,e_2 \in S_{i+1}$ s.t. $e_1 &lt; e_2$ </p></li> <li><p>for each set $S_i$, $\nexists e_1, e_2 \in S_i$ such that $e_1 &lt; e_2$ or $e_2 &lt; e_1$ </p></li> </ol> <p>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. </p> http://mathoverflow.net/questions/61761/topological-sort-of-partial-order-into-sorted-sets/61762#61762 Answer by Omar Antolín-Camarena for Topological sort of partial order into sorted sets Omar Antolín-Camarena 2011-04-14T23:00:12Z 2011-04-15T23:03:50Z <p>EDIT: This answer was for a previous version of the question.</p> <p>There is usually no such list: consider the case where some element is incomparable to everything else.</p> http://mathoverflow.net/questions/61761/topological-sort-of-partial-order-into-sorted-sets/61805#61805 Answer by Johan Wästlund for Topological sort of partial order into sorted sets Johan Wästlund 2011-04-15T11:03:58Z 2011-04-15T11:03:58Z <p>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.</p>