1
$\begingroup$

Let isAncestor be a relation on binary tree nodes such that isAncestor x y means y can be reached from x in n steps from parent to child, where n may be zero. It is clear from this definition that isAncestor is a partial order. (Two nodes are mutual ancestors if and only if they are identical, and ancestors of ancestors are also ancestors.)

But on a second reflection, isAncestor is not just a partial order. For instance, it has the property forall x y z, isAncestor x z -> isAncestor y z -> ( isAncestor x y \/ isAncestor y x ), which I don't think is common to all partial orders.

Is there a kind of order that precisely designates isAncestor? Since binary trees are extensively studied in CS, I'm guessing there must be a name and a well known set of properties for this kind of relation.

$\endgroup$
  • 2
    $\begingroup$ This might be a better fit for Mathematics. But please don't double-post. If you don't get a satisfactory answer here, you can delete and repost over there or ask a Mod to migrate the question. $\endgroup$ – FrankW Sep 10 '14 at 10:35
  • 2
    $\begingroup$ Indeed, all ancestors of a given node form a linear order. Also, there is a root, the ancestor of everyone. I presume such an order is a tree, or can be defined as "nested sets". I do not know a special name? $\endgroup$ – Hendrik Jan Sep 10 '14 at 12:06
  • 1
    $\begingroup$ Note that a "precise" notion might not exist. Every relation has infinitely many properties and the class of all isomorphic relations (which share all these properties) might not be very interesting/rich. Common notions are common because they summarise a few frequently useful properties. $\endgroup$ – Raphael Sep 10 '14 at 13:07
0
$\begingroup$

Your condition is almost equivalent to the statement that the partial order is a tree.

Consider the following two conditions on a partial order $\ge$:

C1: There exists a top element $r$ (also called "the root") such that $\forall x . r \ge x$.

C2: For all $x,y,z$, $x \ge z \land y \ge z$ implies $x \ge y \lor y \ge x$ (this is your condition).

Notice that every tree satisfies both conditions (i.e., its isAncestor partial order satisfies both of these conditions).

Moreover, I claim that every partial order that satisfies both of these conditions has a Hasse diagram that is a tree.

Why? Well, if C1 is true, then C2 is equivalent to

C3: For all $v$, there is a single unique path from $v$ to the root $r$ in the Hasse diagram of $\ge$.

This is easy to prove by looking at the contrapositive: if there were two incomparable paths from $v$ to the root, then we could find a violation of C2 (let $x,y$ be two incomparable elements, each on one of the paths).

And if C1 and C3 is true, then the Hasse diagram is a tree.


Bottom line: there's no particular reason to expect any special name for your property. Your property almost characterizes trees, once we take into account the correspondence between a partial order and its Hasse diagram (which is a DAG).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.