MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 added 41 characters in body

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.

3 fixed condition 1

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. Here, the requirements are:

1. for each pair of sets $S_i$ and $S_j$ such that i < j= 1 \ldots k-1$,$\forall \exists e_1 \in S_i,e_2 \in S_j, 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.

2 removed inappropriate tags
1