4
$\begingroup$

The width $w$ of a partial ordered set(poset) is defined as the cardinality of the maximum antichain. By Dilworth Theorem, we know it is equivalent to the minimum number of chains in any partition.

If we denote an antichain as $A$ and a partition into chains as $P$, then we know $|A| \leq |P|$. And Dilworth Theorem tells us that $\exists A_0, P_0$ s.t. $w = |A_0| = |P_0|$.

Similarly, if we denote a chain as $C$ and a partition into antichains as $Q$, then $\exists C_0, P_0$ s.t. the height $h = |C_0| = |Q_0|$.

Since $|A| \leq |P|$ always holds, to meet the equality, we try to decrease $|P|$, which means we partition the set into fewer chains. However, since the cardinality of the set is fixed, this will make (some of) the chains longer. This means we may increase $|C|$. And the question is, does there always exist $P = \{C_1, C_2, \dots, C_k\}$ s.t. $|P| = |P_0|$ and $|C_i| = |C_0|$ for some $i$?

(That is to say, does there always exist a partition into chains with minimum $|P|$ and maximum $|C|$?)

1 Answers 1

1

Counterexample: Consider the $6$-element poset $\{2,3,4,8,12,36\}$ ordered by divisibility.

The $4$-element chain $C_0=\{2,4,12,36\}$ and the partition $Q_0=\{\{2\},\{3,4\},\{8,12\},\{36\}\}$ into $4$ antichains show that the height is $h=|C_0|=|Q_0|=4$.

The $2$-element antichain $A_0=\{3,4\}$ and the partition $P_0=\{\{2,4,8\},\{3,12,36\}\}$ into $2$ chains show that the width is $w=|A_0|=|P_0|=2$.

It is easy to see that $P_0$ is the only possible partition of this poset into $2$ chains; thus no partition into $2$ chains contains a $4$-element chain.