Chains and antichains from Hasse diagram
Task number: 4153
Variant
Solution
Each longest chain has seven elements. One of the possible longest chains is marked in blue.
The arrangement can be covered by seven antichains, marked in red. There cannot be a longer chain in the arrangement, because by Dirichlet’s principle it would contain at least two elements from some antichain, and these would have to be comparable and incomparable at the same time. Note, however, that there are other coverages of the seven antichains and that it is not even necessary for the antichains to be disjoint.
The largest antichain is an eight-element one, is uique for this partial ordering, and is marked in red in the following figure.
The maximality of the chain length is proved similarly. The ordering can be covered by a total of eight chains, marked in blue, four of which are single-element circled. Therefore, it cannot contain an antichain of nine elements, since two elements of the antichain would lie in the same chain, and this is not possible.
Variant
Solution
The longest chain of length 6 and covered by six antichains is for example:
The longest antichain of length 10 and coverage by ten chains is, for example:
