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).
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
