Chains and antichains from Hasse diagram
Task number: 4153
For the partial order given by the following Hasse diagram, mark some of the longest chain and anti-chain. Argue why no longer can be found.
Solution
Each longest chain has seven elements. One of the possible longest chains is indicated by a thick line. The largest anti-chain is eight-element, unique for this partial order and it is marked with crosses.
The partial order can be covered by eight chains (the remaining seven are marked with ovals in the picture, four of which are single-element), so it cannot contain an anti-chain of nine elements: two elements of the anti-chain would lie in the same chain and this is not possible.
The maximum chain length could be argued similarly: the order can be covered by seven anti-chains, such as ‘layers’ in the diagram. (The ‘middle layer’ is the longest anti-chain indicated by the crosses.) Note, however, that there are other coverages by seven anti-chains and that it is not necessary to find disjoint anti-chains.
