# What is a totally ordered sort of sets of a partial order called?

Given a DAG, which can represent a partial order and has at least one topological sort.

For example the graph

  >B
/  \
A    >D
\  /
>C


has two topological sorts "ABCD" and "ACBD".

My question is the following: Is there a name for the following total order sort of sets:

S: ( {A} , {B,C} , {D} )

The inductive definition is similar to constructing a topological sort:

1. Put the all the graph minima (nodes with no input edges) in set #i S: ( {A} )
2. Remove the graph minima from the graph. G:= G \ {A}
3. repeat step 1. with i := i+1 as long as the graph is non-empty

I find this in several computer science domains. For example method selection in CLOS (Common Lisp), a parallel scheduler of a DAG where nodes are tasks and edges dependencies, the list of all enabled sets in dataflow or petri-net model executions, etc. I haven't found a single nomenclature or even a reference for it though. It sounds simple and pervasive enough to merit one.

• I would just call it a greedy partition into antichains. Commented Aug 16, 2011 at 18:09
• alternately, you could call it a layered decomposition. Commented Aug 16, 2011 at 18:43