The Art Gallery Guardian

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,)(P,\leq) be a partial order. Define U(X)={pxp,xX,pP}\XU(X) = \{ p| x\leq p, x\in X, p\in P\}\backslash X, D(X)={ppx,xX,pP}\XD(X) = \{ p| p\leq x, x\in X, p\in P\}\backslash X.

Let ZPZ\subset P and Q=P\Z{q}Q=P\backslash Z \cup \{q\} where q∉Pq\not\in P. We define an contraction operation C(P,Z)=(Q,)C(P,Z)=(Q,\preccurlyeq), such that

abab or (aD(Z){q} and bU(Z){q})\displaystyle a\preccurlyeq b \Longleftrightarrow a\leq b \text{ or } (a\in D(Z)\cup \{q\} \text{ and } b\in U(Z)\cup \{q\})

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

There is a cute characterization of when (Q,)(Q,\preccurlyeq) is also a partial order.

Theorem1

C(P,Z)=(Q,)C(P,Z)=(Q,\preccurlyeq) is a partial order if and only if D(Z)U(Z)=D(Z)\cap U(Z) = \emptyset. In particular, the map f(x)={xxP\ZqxZ\displaystyle f(x) = \begin{cases} x & x\in P\backslash Z \\ q & x \in Z\end{cases} is order-preserving.

Proof

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

If D(Z)U(Z)D(Z)\cap U(Z) \neq \emptyset, let xD(Z)U(Z)x\in D(Z)\cap U(Z). There is z,zZz,z'\in Z such that zxzz\leq x\leq z'. xqx \preccurlyeq q and qxq \preccurlyeq x but xqx\neq q. (Q,)(Q,\preccurlyeq) is not a partial order.

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

  1. For all xQx\in Q, xxx\preccurlyeq x.

  2. If xyx\preccurlyeq y and yzy\preccurlyeq z then xzx\preccurlyeq z. This can be shown by a few case work from the definition.

  3. xyx\preccurlyeq y, yxy\preccurlyeq x, then x=yx=y.

    • xyx\leq y, then yxy\leq x. Assume not, then yD(Z){q}y\in D(Z)\cup \{q\} and xU(Z){q}x\in U(Z)\cup \{q\}. xD(z)x\in D(z) because xyx\leq y. This implies xD(Z)U(Z)x\in D(Z)\cap U(Z), a contradiction. Thus xyx\leq y implies x=yx=y.

    • If xD(Z){q}x\in D(Z)\cup \{q\} and yU(Z){q}y\in U(Z)\cup \{q\}, and we also have xU(Z){q}x\in U(Z)\cup \{q\} and yU(Z){q}y\in U(Z)\cup \{q\}. This shows x=q=yx=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 XX doesn't introduce directed cycles if and only if the set of vertices reachable from XX and can reach XX are a subset of XX.

Posted by Chao Xu on .
Tags: .