Homeomorphic embedding of a rooted tree ( $T ⪯ S$ )

For finite rooted trees in the ancestor partial order, a rooted-tree homeomorphic embedding is an injective vertex map preserving lowest common ancestors:

h (u \land v) = h (u) \land h (v)

. The image of the source root need not be the host root. Edge paths and branching are preserved, while paths may be subdivided in the larger tree.

Table of contents

Natural-sum ordinal rank of a finite rooted tree ( $o (T) = #_{U child subtree} ω^{o (U)}$ )

Give a leaf rank zero, and use Hessenberg natural sum over the immediate rooted subtrees. Every rank is below epsilon zero; conversely repeated exponentiation and finite summation encode every Cantor normal form below it. A rooted-tree homeomorphic embedding implies nondecrease of the rank. When roots match, child subtrees embed into distinct branches and exponentiation and natural sum preserve their inequalities. When the source root maps below the host root, its rank is bounded by that of a proper subtree, strictly below the host rank.

Adjacency-preserving rooted-tree embedding ( $T \leq_{adj} S$ )

An adjacency-preserving rooted-tree embedding is an injective vertex map preserving the root and every adjacency. Because each root-to-vertex path maps to a simple path of the same length, vertex depths are preserved. This is more restrictive than a homeomorphic embedding of a rooted tree, which may stretch edges into paths. The branching-depth antichain of rooted trees shows that the adjacency relation is not a well-quasi-ordering.

Branching-depth antichain of rooted trees ( $T_{1}, T_{2}, \dots$ )

Let

T_{m}

consist of a rooted path of

m \geq 1

edges followed by two leaves at its far end. Its only vertex with two children has depth

m

. An adjacency-preserving rooted-tree embedding must preserve this depth, so

T_{m}

embeds into

T_{n}

only when

m = n

. This gives an infinite bad sequence, while rooted-tree homeomorphic embeddings can stretch the stems.

Label-monotone tree embedding ( $T ⪯_{Q} S$ )

For rooted trees labelled in a preorder

Q

, a label-monotone tree embedding is a homeomorphic embedding of a rooted tree whose vertex map satisfies

ℓ_{T} (v) \leq_{Q} ℓ_{S} (h (v))

. The root need not map to the host root. For ordered child lists, require in addition that the map preserve the relative order of distinct branches.

 Ancestors (6)

 Incoming links (4)

 Synonyms (1)

codex/rooted-tree-homeomorphic-embedding

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version