Suppose $(S, \leq)$ is a poset. Let $C$ be a maximal chain in $S$. Suppose that the largest antichain of $S$ is of size $M$. Now consider the poset $(S \setminus C, \leq)$. Is it possible that the largest antichain in $S \setminus C$ is still of size $M$?

I am trying to find it in $\mathcal P(X)$ for some non-empty set $X$ when the partially ordered relation is "$\subseteq$". But I couldn't find one such. Please give me some example (if any).

Thank you very much.

  • $\begingroup$ @Asaf Karagila I think we cannot have such an example due to Dilwarth's theorem. It is not very hard to see that if we want to cover $S$ by minimum number of disjoint chains then each chain can contain at most one element of the largest antichain of $S$. But Dilwarth's theorem guarantees that each such chain will contain exactly one element of the largest antichain of $S$. Since the collection of chains is minimal I think each chain in the collection is maximal. So when we eliminate one such chain from $S$ the size of the largest antichain of $S$ will go down by $1$. Please verify my argument. $\endgroup$ – Dbchatto67 Aug 7 '18 at 8:02
  • 2
    $\begingroup$ I think this is an example unless I'm defining some term differently: take four elements $a, b, c, d$, ordered so that $a < b, c < b, c < d$, and all other pairs incomparable. I believe $\{a, d\}$ is a maximal antichain that is disjoint from maximal chain $\{b, c\}$. $\endgroup$ – Doug McLellan Aug 7 '18 at 15:29
  • $\begingroup$ How do you claim that "$<$" is a partially ordered relation? $\endgroup$ – Dbchatto67 Aug 7 '18 at 17:32
  • 1
    $\begingroup$ You can replace $<$ in my comment by $\leq$ -- sorry, I was using $a < b$ as shorthand for "$a \leq b$ and $a \neq b$" which may have been confusing since I didn't say that explicitly. To define my example more explicitly: let $S = \{a, b, c, d \}$, and let $\leq$ be a 2-place relation on $S$ that is reflexive ($a \leq a$, $b \leq b$ etc.), such that $a \leq b, c \leq b,$ and $c \leq d$; and such that $\leq$ holds for no other ordered pair of distinct elements. I believe $\leq$ is a partial order, and has the chain and antichain I specified in my previous comment. $\endgroup$ – Doug McLellan Aug 7 '18 at 18:28
  • $\begingroup$ Thanks @Douglas McLellan your thought works superbly. Consider the set $S=\{\{1\}, \{2\},\{1,2\}, \{2,3,4 \} \}$. Then it has the above property as you have mentioned where the underlying partially ordered relation is "$\subseteq$". Thank you very much for your help. $\endgroup$ – Dbchatto67 Aug 7 '18 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.