Partial order under contraction

1 Real Life Problem

I want to make a program that allow users to maintain some information that has some inherent partial order structure. Each information can be represented by a node, and there are edges going between nodes. One of the operations is grouping multiple nodes and mark them as equivalent. Equivalent nodes can be shrink into one super node, and only expand it when the user want to inspect the inside. However, we still want a partial order in the global view. It would be nice to characterize when it is possible.

2 Formal Formulation

$(P, \leq)$ be a partial order. Define $U (X) = {p ∣ x \leq p, x \in X, p \in P} \ X$ , $D (X) = {p ∣ p \leq x, x \in X, p \in P} \ X$ .

Let $Z \subset P$ and $Q = P \ Z \cup {q}$ where $q \neq \in P$ . We define an contraction operation $C (P, Z) = (Q, ≼)$ , such that

$a ≼ b ⟺ a \leq b or (a \in D (Z) \cup {q} and b \in U (Z) \cup {q})$

If we interpret $(P, \leq)$ as a directed graph, then this operation is contracting the vertices in $Z$ into one vertex $q$ , and then take the transitive closure.

There is a cute characterization of when $(Q, ≼)$ is also a partial order.

Theorem1

$C (P, Z) = (Q, ≼)$ is a partial order if and only if $D (Z) \cap U (Z) = \emptyset$ . In particular, the map $f (x) = {x q x \in P \ Z x \in Z$ is order-preserving.

Proof

If $x \leq y$ , then $f (x) ≼ f (y)$ by definition. We just have to prove $(Q, ≼)$ is a partial order.

If $D (Z) \cap U (Z) \neq = \emptyset$ , let $x \in D (Z) \cap U (Z)$ . There is $z, z^{'} \in Z$ such that $z \leq x \leq z^{'}$ . $x ≼ q$ and $q ≼ x$ but $x \neq = q$ . $(Q, ≼)$ is not a partial order.

If $D (Z) \cap U (Z) = \emptyset$ ,

For all $x \in Q$ , $x ≼ x$ .
If $x ≼ y$ and $y ≼ z$ then $x ≼ z$ . This can be shown by a few case work from the definition.
$x ≼ y$ , $y ≼ x$ , then $x = y$ .
- $x \leq y$ , then $y \leq x$ . Assume not, then $y \in D (Z) \cup {q}$ and $x \in U (Z) \cup {q}$ . $x \in D (z)$ because $x \leq y$ . This implies $x \in D (Z) \cap U (Z)$ , a contradiction. Thus $x \leq y$ implies $x = y$ .
- If $x \in D (Z) \cup {q}$ and $y \in U (Z) \cup {q}$ , and we also have $x \in U (Z) \cup {q}$ and $y \in U (Z) \cup {q}$ . This shows $x = q = y$ .
- By symmetry, it take care of the remaining cases.

Again, if we interpret this in a graph theoretical sense, a contraction of a set of vertices $X$ doesn’t introduce directed cycles if and only if the set of vertices reachable from $X$ and can reach $X$ are a subset of $X$ .

Posted by Chao Xu on 2014-02-15.

Tags: random.