Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.