Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|$?)

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.