Poset¶
A partially ordered set (poset) is a set equipped with a partial order relation. This relation must satisfy three properties: reflexivity (every element is related to itself), antisymmetry (if two elements are mutually related, they must be equal), and transitivity (if element a is related to b, and b is related to c, then a is related to c).
Definition¶
A Poset (Partially ordered set) is defined as a directed graph possessing the following property:
If \(ab\) and \(bc\) are edges of this graph, then \(ac\) must also be an edge of this graph.
Since many mathematical concepts can be represented as posets, their study proves particularly useful.
The First Problem¶
Suppose we have a set of natural numbers denoted as \(A\), and we want to find the largest subset \(B\) such that for any two members of \(B\), one is divisible by the other.
We can model this problem with a graph as follows: For each member of \(A\), create a vertex in the graph. For any two vertices \(x\) and \(y\) where \(x|y\) (x divides y), draw a directed 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\), there is an edge from \(u_i\) to \(u_j\), is called a chain. Note that due to the poset property, it suffices for \(u_1, ..., u_k\) to form a path.
A subset of vertices where no two vertices are connected by an edge is called an antichain.
Later, we will examine partitioning a graph into chains or antichains (vertex partitioning is intended here).
Note that these definitions are exclusively used in posets.
Maximum Chain = Minimum Partition into Antichains¶
Assume the size of the maximum chain is \(L\). Consider a maximum chain such as \(A\).
Any antichain can include at most one vertex from \(A\). Thus, the minimum partition into antichains is at least \(L\). Now we prove that equality is achievable.
Assign to each vertex \(u\) a number \(a_i\), which equals the size of the largest chain ending at \(u\). Observe that if \(a_i = a_j\), there cannot be an edge between \(i\) and \(j\). For example, if there is an edge from \(i\) to \(j\), then \(a_j \geq a_i+1\).
For each vertex \(u\), we call \(a_u\) the color of \(u\). According to the above proof, vertices with the same color form an antichain. The number of colors equals \(L\) (why?). Thus, we can partition the graph into \(L\) antichains.
This theorem is known as Mirsky’s theorem and was proposed in 1971. Interestingly, this theorem had already been recognized in 1940 by Dilworth, Gallai, Fulkerson, and others. Their sole reason for not publishing it was considering it "too obvious"!
Maximum Antichain = Minimum Partition into Chains¶
Similar to before, we can first conclude that the minimum partition into chains is at least the size of the maximum antichain (since each chain can contain at most one vertex from the maximum antichain). Now we aim to demonstrate an example where equality holds.
We discussed the problem of partitioning graph vertices into a minimum number of paths in section 4. It sufficed to represent the graph as a bipartite graph and find a maximum matching. Now we know that in posets, every chain corresponds to a path. Thus, the problem of minimum partition into chains is solved by finding the minimum vertex partition into paths.
# This is a sample code block, comments remain in Finglish
def test_function():
print("Hello World") # Another Finglish comment
Augmenting-like Path¶
Now suppose our poset is a directed graph named \(P\). Let \(G\) be its equivalent bipartite graph. Consider a minimal path decomposition in \(P\). Let \(M\) be the set of directed edges present in our paths. We know that the edges of \(M\) correspond to the edges of a maximum matching in \(G\). The necessary and sufficient condition for a matching to be maximum was the absence of an augmenting path. We examine what the equivalent of an augmenting path would be in our directed graph. A free vertex in the first partition of \(G\) corresponds to a vertex in \(P\) that is the end of a path. A free vertex in the second partition of \(G\) corresponds to a vertex in \(P\) that is the start of a path.
Thus, we want to understand the equivalent of an augmenting path in \(G\) (which starts in the first partition and ends in the second partition) within the graph \(P\). We define an augmenting-like 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 chosen path in the minimal decomposition. Additionally: - For each \(u_{2i-1},u_{2i}\) in \(P\), the edge \(u_{2i-1}u_{2i}\) exists and does not belong to \(M\). - For each \(u_{2i},u_{2i+1}\), the edge \(u_{2i+1}u_{2i}\) belongs to \(M\)! (Note the reversal of direction).
Therefore, we can assume that the vertices of \(P\) have been partitioned into the minimal number of paths such that no augmenting-like path exists in \(P\).
Algorithm¶
Our goal now is to select exactly one vertex from each chain such that the selected vertices form an antichain. In this case, we can achieve equality (i.e., meet the Dilworth number).
Consider the following algorithm:
Take the first vertices of all paths. If there are no edges between them, simply select them. Otherwise, there exists an edge like \(uv\) where \(u\) and \(v\) are the first vertices of two paths in our decomposition.
Now, we must eliminate vertex \(u\). Since \(u\) has an edge to \(v\), and \(v\) is the first vertex of a path, by the poset property, we can conclude that \(u\) has edges to all vertices in \(v\)'s path. Therefore, if we include \(u\) in the antichain, we cannot select any vertex from the path starting with \(v\), preventing us from achieving our goal of choosing one vertex from each path. Hence, eliminate \(u\).
Continue this process until there are no edges between the first vertices of the remaining paths (after eliminations), yielding an antichain of size equal to the number of paths. The only scenario that disrupts our process is when an entire path is eliminated (in this case, the antichain will not have the same size as the initial number of paths).
No Path is Completely Removed¶
We now prove that no path is entirely removed during the algorithm. The idea of the proof is to assume, for contradiction, that a path is completely removed, and then find a quasi-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 in the algorithm, \(a\) was removed due to the edge \(ab\). That is, at some stage of the algorithm, both \(a\) and \(b\) belonged to two paths, the edge \(ab\) was part of \(P\), and according to the algorithm, we removed vertex \(a\).
For each vertex \(a\), consider the path containing \(a\), and call the vertex preceding \(a\) in this path (such as \(b\)) the chief of \(a\). (This means the edge \(ba\) belongs to \(M\)).
Note that for every vertex \(a\), the time of \(a\)'s removal occurs after the removal time of the chief of its parent. This is because when \(a\) is removed by its parent, the parent must first belong to a path. Hence, the chief of the parent (if it exists) is removed before this deletion.
Now suppose at some stage, a vertex \(a\) is removed, which is the endpoint of a path in our partition. Start from vertex \(a\) and place a marker on \(a\). At each step, if the marker is on \(u\), first move it to the parent of \(u\). If the parent of \(u\) was originally part of one of the paths, we have found our quasi-augmenting path. Otherwise, move the marker to the chief of the parent of \(u\). Note two key points:
The process terminates because, as stated earlier, after each step, the marker moves to a vertex with an earlier removal time in the algorithm.
At every step, the vertex where the marker resides has a parent. This is because, in our algorithm, this vertex was removed (since its removal time is earlier than \(a\)'s, and we assumed \(a\) was removed).
Thus, we have found a quasi-augmenting path. As argued earlier, the resulting contradiction shows that no path is completely removed!
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
