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

be a partial order. Define , .

Let and where . We define an contraction operation , such that

If we interpret as a directed graph, then this operation is contracting the vertices in into one vertex , and then take the transitive closure.

There is a cute characterization of when is also a partial order.

Theorem1

is a partial order if and only if . In particular, the map is order-preserving.

Proof

If , then by definition. We just have to prove is a partial order.

If , let . There is such that . and but . is not a partial order.

If ,

  1. For all , .

  2. If and then . This can be shown by a few case work from the definition.

  3. , , then .

    • , then . Assume not, then and . because . This implies , a contradiction. Thus implies .

    • If and , and we also have and . This shows .

    • 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 doesn’t introduce directed cycles if and only if the set of vertices reachable from and can reach are a subset of .

Posted by Chao Xu on .
Tags: random.