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$
0

2 Answers 2

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$
2
  • $\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$ Commented Mar 3, 2015 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
    Commented Mar 3, 2015 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$
2
  • $\begingroup$ Ah, that's a very concise way of putting it. Nice. $\endgroup$
    – jmc
    Commented Mar 2, 2015 at 9:05
  • $\begingroup$ @jmc thanks, you were 5 minutes faster though $\endgroup$ Commented Mar 2, 2015 at 15:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .