Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be an embedding of $T_{1}$ into $T_{2}$ in the usual graph-theoretical sense (i.e. a homeomorphism) with the extra condition that $l_{1}(x)=l_{1}(y)$ implies $l_{2}(f(x))=l_{2}(f(y))$ for all vertices $x,y$ of $T_{1}$ (where $l_{1}$, $l_{2}$ are the labelling function for $T_{1}$ and $T_{2}$, respectively). We say that $T_{1}$ is an equalitiy-preserving minor of $T_{2}$, written $T_{1}\prec_{ep}T_{2}$ iff there is an equality-preserving embedding $f:T_{1}\rightarrow T_{2}$. (Note that we do not demand that differently labelled vertices are mapped to differently labelled vertices.)

Is $\prec_{ep}$ a well-quasi-ordering or even a better-quasi-ordering on the set of finite trees labelled by natural numbers? (This holds, of course, by Kruskal's theorem if we replace $S$ with a finite set.)

Edit: Considering only well-quasi-orderings for the moment, one can also model this as follows: Given a tree $T$, we introduce for each label $c$ a new vertex $v_{c}$, join it to all vertices of $T$ that have this label and forget about the labels. That makes the question almost an instance of the graph minor theorem (stating that the finite graphs are wqo under the minor relation) but for the fact that the embeddings must map extra vertices to extra vertices and tree vertices to tree vertices. This would follow if the graph minor theorem would continue to hold for graphs coloured with finitely many (in fact merely $2$) colours.

• I don't understand your question. Isn't it true that every finite subset of the natural numbers is a special case of a finite set? – Tobias Schlemmer May 29 '14 at 14:48
• Sure. But here we have all natural numbers available as our colours, not just a finite set; so while each tree is of course coloured by finitely many colours only, all the trees together may have infinitely many different colours, so Kruskal (or Nash-Williams, for bqo) is not applicable (at least not obviously, or at least not obviously for me). – M Carl May 30 '14 at 8:31
• The label-free formulation of the question is that you consider finite trees endowed with an equivalence relation, and you quasiorder them by tree embeddings that are homomorphisms for the equivalence relations. – Emil Jeřábek May 31 '14 at 14:46
• By "embedding in the usual graph-theoretical sense" I guess you mean homeomorphic (rather than, say, homomorpic) embedding. Did I guess right? – bof May 31 '14 at 23:01
• Yes. I think that is the way the term "embedding" is usually understood in this context. – M Carl May 31 '14 at 23:21

2 Answers

Somewhat surprisingly, the answer is in fact no, even for paths.

Claim. There is an infinite antichain of coloured paths under $\prec_{ep}$.

Proof. Consider a path $P$ with $2k$ vertices, with vertices coloured from $[k]$. The first $k$ vertices of $P$ are coloured $1, \dots, k$, in that order, and the remaining $k$ vertices are coloured $1, \dots, k$, but in an arbitrary order. Thus, $P$ induces a permutation $\pi(P):[k] \to [k]$. Now given two such paths, $P$ and $Q$, observe that $P \prec_{ep} Q$ if and only if $\pi(P) \leq \pi(Q)$, where $\leq$ is the containment relation on permutations. That is, $\pi_1 \leq \pi_2$ if we can obtain $\pi_1$ from $\pi_2$ by deleting elements of $\pi_2$ and then renaming elements appropriately.

In this paper, Spielman and Bóna exhibit an infinite antichain of permutations, so we are done modulo a slight lie. The slight lie is that a path may embed in another path with the opposite orientation. However, we can fix this using two extra colours red and blue. We add three red vertices to the beginning of a path and four blue vertices at the end of a path. This fixes the orientation, so we really are just working with the permutation order as claimed.

This is joint with Luke Postle and Paul Wollan (possibly over beer).

I don't think your new model works. Consider two identical trees, $T_1$ and $T_2$. $T_1$ has a different colour at each vertex, and $T_2$ is monochromatic. Now $T_1 \preceq_{ep} T_2$ but the graph generated by $T_1$, which we can call $G_{T_1}$, is not a minor of $G_{T_2}$. You can fix the problem with your new statement by creating the new $v_c$ for each pair of equal vertices, rather than just for each colour.

The problem remains that the added vertices might be mixed up with the original vertices. I think you can fix this by duplicating each edge in the tree, at which point your done because, as you've said, the graph minor relation is a well-quasi-ordering by the Robertson-Seymour Theorem.

• I am not sure this will work since we actually want the trees to be topological minors of each other. If you apply the usual graph minor theorem to your auxiliary graphs, it might be that one tree embeds as a minor in another tree, and this isn't what we want. I think the way to get around this is to use the fact that graphs are WQO under immersion. This is proved in Graph Minors XXIII. Note that in Graph Minors XXIII, it is shown that graphs with WQO labels are WQO, but the notion is a bit different than what is required here. – Tony Huynh Jun 2 '14 at 13:55
• You are quite right, my approach would also force different labels to be mapped to different labels, which I explicitely didn't ask for. I will have a look at RSXXIII. Does anybody have an intuition on the bqo part of the question? Is it merely a variant of the analogue for trees or rather untractable? I understand that the finite graphs are expected to be bqo under minors (possibly also immersion?), but that this is a deep open question. – M Carl Jun 3 '14 at 11:04
• I think the BQO may be true but is likely intractable with the current machinery. For example, I tried to prove just the WQO using the main result from Graph Minors XXIII, and couldn't quite get it to work. It might be that one has to redo the argument from Graph Minors XXIII, which is a bit complicated. So, it looks like this result is closer to WQO graphs than WQO trees. That's why I say BQO is likely intractable. – Tony Huynh Jun 5 '14 at 15:29