This post is motivated by a problem I recently saw, Problem G of NCPC 2007. This is a standard problem that I'm sure many of you have seen before, but the general topic of partially ordered sets is not too well known.

Definitions

Let S be a set of elements and  ≤  be a partial ordering on the set. That is, for some elements x and y in S we may have x ≤ y. The only properties that  ≤  must satisfy are reflexivity (x ≤ x), antisymmetry (if x ≤ y and y ≤ x, then x = y), and transitivity (if x ≤ y and y ≤ z, then x ≤ z). Note that because it is a partial ordering, not all x and y are comparable.

An example of a partially ordered set (poset) is the set of points (x, y) in the Cartesian plane with the operator (x₁, y₁) ≤ (x₂, y₂) iff x₁ ≤ x₂ and y₁ ≤ y₂ (e.g. NCPC 2007 problem).

We define a chain C to be a subset of S such that the elements of C can be labelled x₁, x₂, ..., x_n such that x₁ ≤ x₂ ≤ ... ≤ x_n. A partition P is a set of chains where each element occurs in exactly one chain.

We define an antichain A to be a subset of S such that for any x and y in A we have neither x ≤ y nor y ≤ x. That is, no two elements of an antichain are comparable.

Dilworth's Theorem

We can define the width of a poset in two ways, which is the result of Dilworth's Theorem. One definition is the size of the maximum antichain; the other is the size of the minimum partition. It is easy to see that any partition must have at least as many chains as the size of the maximum antichain because every element of the antichain must be in a different chain. Dilworth's Theorem tells us that there exists a partition of exactly that size and can be proved inductively (see Wikipedia for proof).

Calculating the Width

So how does one calculate the width of a poset? To solve this problem in general, we can use maximum matching on a bipartite graph. Duplicate each element x in S as u_x and v_x and if x ≤ y (for x ≠ y) then add the edge . If you compute the maximum matching on this graph, this is equivalent to partitioning the elements into chains, where if the edge is chosen then x and y are in the same chain. In particular, if the size of the matching is m and |S| = n, then the number of partitions is n - m. Notice that this gives a bijection between partitions and matchings, so the maximum matching gives the minimum partition, which we know is equal to the width as given by Dilworth's Theorem.

Problem G of NCPC 2007

So now that we can calculate the width of a poset, we can just apply that to our problem, right? Not quite.

The bounds on our problem are up to 20, 000 so we can't use maximum matching. Luckily, points in the Cartesian plane are more structured than general posets, and we can use the other definition of width (maximum antichain) to solve this problem more efficiently. Consider iterating over the points sorted in order by x. We maintain a set of pairs (a, b) which indicates that there is an antichain of size b that ends at y-value a (among all points that have already been processed). Thus for any future point (x, y) we can insert (y, b + 1) into the set as long as y < a.

Notice, however, that if we have two points in the set (a, b) and (c, d) such that c ≤ a and d ≤ b then the latter is redundant (it is always worse) and we can remove it. In this way we keep the set small and only need to check a single element whenever we insert, which is (a, b) with minimal a such that a > y. All of this can be done with a C++ set, for example. At the end, the largest antichain we recorded is indeed the maximum one, and we are done.

Exercise

A recent Google Code Jam problem uses these ideas.