1
$\begingroup$

This is a follow-up question to Complete sets of incompatible totally ordered down-set in a partially ordered set.

Let $(P,\leq)$ be a partially ordered set such that for every $p\in P$ the set $\{q\in P: q\leq p\}$ is finite. A down-set is a set $d\subseteq P$ such that $x\in d$ and $x'\in P, x'\leq x$ imply $x'\in d$. If the down-set is totally ordered, we say it is a totally ordered down-set (tods).

Let $d_1, d_2$ be tods. We say that they are incompatible if neither $d_1\subseteq d_2$ nor $d_2\subseteq d_1$ holds. A set of pairwise incompatible tods is called a bunch. A bunch $B$ said to be complete if for every maximal chain $m\subseteq P$ there is $b\in B$ such that $b\subseteq m$.

Given a finite tods $t$, is there a complete bunch $B$ also consisting of finite sets only, and $t\in B$?

(Motivation: the answer to the linked post shows that bunches consisting of finite tods cannot always be completed, but it is still possible that if you start out with a singleton bunch consisting of 1 finite tods, the singleton bunch can be completed.)

$\endgroup$
  • $\begingroup$ There is something wrong with the sentence where you define complete. Maybe $C = B$? $\endgroup$ – jmc Mar 2 '15 at 8:23
  • $\begingroup$ That's right, thanks for noticing - I just corrected it. $\endgroup$ – Dominic van der Zypen Mar 2 '15 at 8:29
  • $\begingroup$ Hmm, I think you need more assumptions. The integers do not contain a finite tods, right? This easily gives counter examples. So I think every maximal chain should have a minimal element. $\endgroup$ – jmc Mar 2 '15 at 8:37
  • $\begingroup$ Right - I need that below every element there are only finitely many. Will add this. Sorry for the inconvenience and thanks for your precise reading! $\endgroup$ – Dominic van der Zypen Mar 2 '15 at 8:51
3
$\begingroup$

I think that in this case there will always be a complete bunch $B$.

  • For every maximal chain $m$ with $m \cap t = \varnothing$, take the minimal element of $m$, and add it as tods to $B$.
  • If $m \cap t \ne \varnothing$, and $t \not\subset m$, then take the minimal element $x$ of $m \setminus t$, and add $\{x\} \cup (m \cap t)$ to $B$.
  • Finally, add $t$ to $B$, and now $B$ is complete.

$B$ is also a bunch of finite tods, because by construction all tods in $B$ are finite and pairwise incompatible.

$\endgroup$
  • $\begingroup$ Hang on - $t$ and $\{x\}\cup t$ are comparable, so $B$ is no longer a bunch, isn't it...? (Thanks to Joel Adler for noticing this.) $\endgroup$ – Dominic van der Zypen Mar 3 '15 at 12:56
  • $\begingroup$ @DominicvanderZypen — You are right, I made a typo. I'll fix it. Bjørn's answer is correct (and more concise.) $\endgroup$ – jmc Mar 3 '15 at 13:29
2
$\begingroup$

Yes. We can take the collection of all tods $ s $ such that $ s \backslash t $ is a singleton and $ s $ is incompatible with $ t $. Any maximal chain extends exactly one of these, or $ t $.

$\endgroup$
  • $\begingroup$ Ah, that's a very concise way of putting it. Nice. $\endgroup$ – jmc Mar 2 '15 at 9:05
  • $\begingroup$ @jmc thanks, you were 5 minutes faster though $\endgroup$ – Bjørn Kjos-Hanssen Mar 2 '15 at 15:01

Your Answer

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

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