2
$\begingroup$

Let $R$ be a reflexive binary relation and $R^*$ be its reflexive transitive closure. The question is what is the equivalent condition in terms of $R$ to $R^*$ being a partial order.

Intuitively, a reflexive transitive closure adds reflexivity and transitivity to the original relation. But just because $R$ is antisymmetric doesn't mean $R^*$ is a partial order.

$\endgroup$
2
  • 1
    $\begingroup$ $R$ (not counting the loops) must not have any directed cycles. $\endgroup$
    – Srivatsan
    Dec 13, 2011 at 10:10
  • $\begingroup$ Does it have a special name? $\endgroup$
    – Pteromys
    Dec 14, 2011 at 11:52

1 Answer 1

1
$\begingroup$

Directed acyclic graph (often abbreviated to DAG).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .