We are given a family of sets $F=\{F_1,\ldots,F_n\}$ with each $F_i$ being a subset of a ground set $N=\{1,\ldots,n\}$. In addition, we assume for each $F_i$ that it's not the subset of another $F_j$ i.e. $F_i \subseteq F_j$ implies $F_i=F_j$.

An example: $F=\{\{1,3,5\}, \{1,2\}, \{2,4,6\}\}$. I noticed that I can represent $F$ as the set of paths of the directed acyclic graph below.

DAG representation of $F$

Is this DAG representation something known in the literature? In particular, the DAG representation I'm talking about is one in which no path results in a superset of family members. If so, is it known which are the necessary properties for $F$ that make it possible to represent it this way? Because I notice that e.g. $F'=\{\{1,2\}, \{1,3\}, \{2,3\}\}$ cannot be represented as the paths of a DAG.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.