4
$\begingroup$

The question is in the title. Here "$P$ embeds into $Q$" means there is a function $f : P\to Q$ such that for all $p,p'\in P$, $p \le_P p'$ if and only if $f(p) \le_Q f(p')$. A well quasi order $W$ is a relation which is reflexive and transitive, such that for any infinite sequence $w_1,w_2,\ldots,w_n,\ldots$ taken from the universe of $W$, there are some $n < m$ such that $w_n \le_W w_m$.

My question is motivated by this other recent question. Laver proved that the countable linear orders form a wqo under embeddability. If this holds more generally for countable partial orders, then that would imply that the $\bar{\mathcal{O}}$ from the question above has no infinite descending chain or infinite antichain.

$\endgroup$
0
2
$\begingroup$

The class of countable partial orders quasi-ordered by embeddability is not well quasi-ordered. Here is a simple example of an infinite antichain taken from M. Pouzet, Applications of well quasi-ordering and better quasi-ordering, in Graphs and order (1985), the "crowns": enter image description here

As far as I know, in the literature, the largest class of countable partial orders known to be wqo (in fact, bqo, of course) under embeddability is the class of $N$-free partial orders, i.e. those partial orders in which

enter image description here

does not embed. This was proved by S. Thomassé in On better-quasi-ordering countable series-parallel orders, Trans. Amer. Math. Soc., 352 (2000), 2491--2505.

$\endgroup$
1
  • $\begingroup$ Great answer, thanks! $\endgroup$ – Paul McKenney Jul 3 '14 at 12:51

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.