1
$\begingroup$

Let $D$ be some directed graph, and let $G$ and $G'$ be two acyclic subgraphs of $D$; let $E$ and $E'$ be their sets of edges. Is it possible to give a simple criterion on $E$ and $E'$ (sufficiency and necessity would be great, of course) for when the subgraph given by $E \cup E'$ is still acyclic?

(I can come up with [fairly trivial] necessary conditions, and also with [fairly elaborate] sufficient conditions, but all these are far from optimal.)

Thanks!

Edit: changed the wording and the title in response to Qiaochu Yuan's comments.

  • 1
    The union is always a DAG.2012-02-17
  • 0
    @QiaochuYuan: If $V = V' = \{a, b\}, E = \{(a, b)\}, E' = \{(b, a)\}$, then $(V, E)$ and $(V', E')$ are both acyclic, but $(V\cup V' = V, E \cup E' = \{(a, b), (b, a)\})$ is not acyclic.2012-02-17
  • 3
    I suspect that no better criterion can be given than "$E\cup E'$ contains no cycles." Just out of curiosity, can I ask why you are interested in the union operation on DAGs?2012-02-17
  • 1
    Oh, I didn't realize you weren't assuming that $V, V'$ are disjoint. I don't think it is good practice to call this operation the union of two DAGs. I would prefer that you call it the union of two sub-DAGs of some graph. (For me the union of two sets is either the disjoint union or it is only defined for subsets of a set. I don't like the union in the ZFC sense.)2012-02-17
  • 0
    @AlexKruckman: I'm learning about posets, and I wanted to understand better when the transitive closure of the union of two partial orders on the same underlying set is still antisymmetric. This question, in turn, arises from a looking at the partial orders induced on a set $Y$ by a partial order on some other set $X$ and two functions $X\to Y$.2012-02-17

0 Answers 0