1
$\begingroup$

Can anyone tell me if there's a term for this concept?

Given a DAG $D=(V,A)$, I have a collection of subsets of $V$. Let's call that collection $C = \{ S_1, S_2, \ldots, S_n \}$.

($S_1 \cup S_2 \cup \dots \cup S_n$) could be any (improper) subset of $V$. However, the sets contained within $C$ are all mutually disjoint.

Is there a name for the kind of thing that "$C$" is?

If the members of $C$ collectively covered all of the DAG then I would call $C$ a "partition".

  • 1
    What kind of graph does DAG refer to, I'm curious?2012-11-25
  • 0
    I suspect "directed acyclic graph".2012-11-25
  • 0
    Maybe just "a partition of a subset of $V$".2012-11-25
  • 0
    The graph structure $A$ seems to play no role at all in this question. One could have said simply "Given a set $V$, I have a collection of subsets of $V$.", etc.2012-11-25
  • 0
    I don't know the answer, but if I'm not being overly hasty, I think I see a simple bijective proof that there are exactly as many partitions of subsets of $V$ as there are partitions of a set of size $|V|+1$.2012-11-25

0 Answers 0