Poset¶

First Problem¶

Suppose we have a set of natural numbers, say \(A\), and we want to find its largest subset, say \(B\), such that for any two members of \(B\) we consider, one is divisible by the other.

We can model this problem as a graph. For each member of \(A\), place a vertex in the graph, and for two vertices \(x,y\) such that \(x|y\), draw an edge from \(x\) to \(y\). Now the problem is equivalent to finding the longest path in this graph!

Chain and Antichain¶

A sequence of distinct vertices, such as \(u_1,...,u_k\), where for every \(i<j\), \(u_i\) has an edge to \(u_j\), is called a chain. Note that due to the poset property, it is sufficient that \(u_1, ... u_k\) form a path.

A subset of vertices where no two vertices have an edge between them is called an antichain.

In the following, we will examine the partition of a graph into chains or antichains (partition of the graph's vertices is intended).

Note that these definitions are used only in posets.

Pseudo-augmenting Path¶

Now, suppose our poset is a directed graph called \(P\). Call its equivalent bipartite graph \(G\). Consider a minimum partition into paths in \(P\). Let \(M\) be the set of directed edges present in our paths. We know that the edges in \(M\) are equivalent to the edges of a maximum matching in \(G\). The necessary and sufficient condition for a matching to be maximum was that there are no augmenting paths. We will examine what an equivalent of an augmenting path in our directed graph would look like. A free vertex in the first part of \(G\) corresponds to a vertex in \(P\) that is the end of a path. A free vertex in the second part of \(G\) corresponds to a vertex in \(P\) that is the start of a path.

So, we want to understand the equivalent of an augmenting path in \(G\) that starts from the first part and goes to the second part, in graph \(P\). We define a pseudo-augmenting path in \(P\) as follows:

A sequence of vertices \(u_1,u_2,...,u_{2k+1}\) such that \(u_1\) is the start and \(u_{2k+1}\) is the end of a selected path in the minimum partition. Also, for \(u_{2i-1},u_{2i}\) in \(P\), the edge \(u_{2i-1}u_{2i}\) must exist and not be a member of \(M\), and for \(u_{2i},u_{2i+1}\), the edge \(u_{2i+1}u_{2i}\) must be in \(M\)! (Pay attention to the change in order).

So now we can assume that we have partitioned the vertices of \(P\) into the minimum number of paths such that there is no pseudo-augmenting path in \(P\).

Algorithm¶

Now our goal is to select exactly one vertex from each chain such that the selected vertices form an antichain. In this case, we can achieve equality.

Consider the following algorithm:

• Consider the first vertices of the paths. If there are no edges between them, just select them. Otherwise, there exists an edge like \(uv\) where both \(u,v\) are the first vertices of two paths in our partition.

• Now we must remove vertex \(u\). Because, given that \(u\) has an edge to \(v\), and \(v\) is the first vertex of a path, by the poset property, it can be concluded that \(u\) has an edge to all vertices of the path starting with \(v\). So if we select \(u\) in the antichain, we cannot select any vertex from the path that starts with \(v\), and thus we cannot achieve our goal of selecting one vertex from each path. So, remove \(u\).

Continue this process until there are no edges between the first vertices of the paths (after removals) and we find an antichain of size equal to the number of paths. The only case that would spoil our work is if a path is completely removed (in which case the antichain would not be of the size of the initial number of paths).

No Path is Completely Removed¶

So we prove that none of the paths are completely removed during the algorithm. The idea of the proof is to assume, by contradiction, that a path is completely removed, and then find a pseudo-augmenting path in the original graph, which will contradict the minimality of our partition.

For each vertex \(a\), we call a vertex \(b\) the parent of \(a\) if \(a\) was removed in the algorithm due to the edge \(ab\). That is, at some stage of the algorithm, \(a,b\) are both the first vertices of two paths, and the edge \(ab\) is a member of \(P\), and according to the algorithm above, we remove vertex \(a\).

For each vertex \(a\), consider the path it is in, and call the vertex preceding \(a\) in that path (e.g., \(b\)) the chief of \(a\) (meaning \(ba\) is an edge in \(M\)).

Note that for any vertex \(a\), the time of \(a\)'s removal is after the time of removal of the chief of \(a\)'s parent. This is because when \(a\) is removed by its parent, it must be the first vertex of a path. This means the chief of the parent (if it exists) was removed before this.

Now suppose at some stage, vertex \(a\) is removed, which is the end of a path from our partition. Start from vertex \(a\) and place a marker on \(a\). At each step, if the marker is on \(u\), first move the marker to the parent of \(u\). If the parent of \(u\) is the start of one of the paths, we have found our pseudo-augmenting path. Otherwise, move the marker to the chief of the parent of \(u\). Note two things:

• The process terminates because, as we said, after each step, the marker is placed on a vertex whose removal time in the algorithm is earlier.

• At each step, the vertex with the marker has a parent. This is because this vertex is removed in our algorithm (because its removal time is earlier than \(a\)'s, and we said \(a\) is also removed).

Thus, we were able to find a pseudo-augmenting path. As we said, the resulting contradiction shows that no path is completely removed!