2
$\begingroup$

For $X$ and $Y$ finite sequences of finite trees, let us say that $X$ is everywhere contained in $Y$ ($X\subseteq_{ec}Y$) iff, for every $y\in Y$, there is some $x\in X$ such that $x$ is a minor of $y$. Is $\subseteq_{ec}$ a well-quasiordering on the set of finite sequences of finite trees? (I.e.: Does every infinite set of finite sequences of finite trees contain two elements $X$ and $Y$ such that $X\subseteq_{ec}Y$?) Kruskal's theorem for labelled trees implies that this holds when all sequences in the set have the same length (or are of bounded length).

$\endgroup$

1 Answer 1

3
$\begingroup$

To reformulate your question, given a wqo $(A,\leq)$, here finite trees with the minor ordering, you ask whether $({\mathcal P}_\mathrm{fin}(A),\sqsubseteq)$ the set of finite subsets of $A$ with a `minoring' ordering is also a wqo: $X\sqsubseteq Y$ iff $\forall y\in Y.\exists x\in X.x\leq y$.

This is does not hold for arbitrary wqos: it fails for any wqo that contains an isomorphic copy of the Rado structure, see Jančar (1999). The wqos for which it holds are called $\omega^2$-wqos in a classification by Marcone (2001).

Coming back to your specific question about trees, Nash-Williams (1965) shows that trees under homeomorphic embedding have the much stronger notion of a better quasi order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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