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.

  • 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