Existence of infinite subsequence of trees with a special condition

Question

For rooted trees, define $children(v)$ as the number of children of the vertex $v$.

Assume two operations on rooted trees:

1. contract an edge: choose an edge $E$, join two vertices adjacent to $E$
2. grow a leaf: choose any vertex and connect it to a new leaf

Starting with any rooted tree, using these operations we get an infinite sequence of trees.

Does the sequence always contain a tree $T_1$ such that there is an infinite subsequence of trees such that for each tree $T_2$ in that subsequence there is an injective mapping of vertexes $f: V(T_1) \rightarrow V(T_2)$ such that for each vertex $v \in V(T_1)$ the corresponding vertex $f(v)$ has at least that number of children? ($children(f(v)) \geq children(v)$)

It is a variation of question Existence of infinite subsequence of trees assuming two tree operations with relaxed condition on tree relation - more general mapping on vertexes instead of a subgraph. This variation now maybe could relate to The hydra game.

Answer 1

Let $\phi_T : \mathbb{N}\times\mathbb{N} \to \mathbb{B}$ be defined as

$$\phi_T(n,k) \iff \text{in tree } T \text{ there are at least } n \text{ nodes }\text{with at least } k \text{ children each},$$

and define $\Phi_S : \mathbb{N}\times\mathbb{N} \to \mathbb{B}$

\begin{align}\Phi_S(n,k) \iff & \phi_T(n,k) \text{ is true for infinitely many trees } T \text{ of }S\\ \iff &\text{in }S \text{ there are infinitely many trees with } \\ &\text{at least } n \text{ nodes } \text{with at least } k \text{ children each.} \end{align}

Both functions are monotonic (non-increasing) in both $n$ and $k$. Now, let $M$ be the biggest number such that $\Phi_S(M,M)$ is true, that is

$$M = \sup\{m \in \mathbb{N} \mid \Phi_S(m,m) = \mathtt{true} \}.$$

We would like to show that either $\Phi_S$ is always true (case $M = \infty$) or looks roughly like this:

$\hspace{50pt}$

If $M = \infty$, then we are done, because any tree $T$ is a candidate for $T_1$, hence, we can assume that $M < \infty$.

Let $N$ be the biggest number such that $\Phi_S(N,k)$ is true for all $k$, that is,

$$N = \max \{n \in \mathbb{N} \mid \forall k \in \mathbb{N}.\ \Phi_S(n,k) = \mathtt{true}\}.$$

Such number $N$ exists, because $0 \leq N \leq M$. Now select a subsequence $S'$ of $S$ such that $$\max\{k \mid \phi_{T_i}(N,k)\} > \max \{\deg(v) \mid v \in T_{i-1}\}.$$ (If $N = 0$, then $S' = S$.)

Now set $K$ to be the biggest number such that $\Phi_{S'}(n,K)$ is true for all $n$, i.e.

$$K = \max\{k \in \mathbb{N} \mid \forall n.\ \Phi_{S'}(n,K) = \mathtt{true}\},$$

and pick a subsequence $S''$ of $S'$ such that $$\max\{n \mid \phi_{T_i}(n,K)\} > |T_{i-1}|.$$ (Similarly $S'' = S'$ if $K = 0$.)

Set $n^*$ and $k^*$ to be the biggest finite $n$ and $k$ (for $K+1$ and $N+1$ respectively), then there are only at most $2^{(n^*+1)(k^*+1)}$ possible options for valuations of $\phi_{T}(n,k)$ for $0 \leq n \leq n^*$ and $0 \leq k \leq k^*$ and any $T\in S''$, so one of these has to represent infinitely many trees. Let $S'''$ be the subsequence of $S''$ constrained to that set.

Finally, the sequence $S'''$ is an ascending sequence of trees.

I hope this helps $\ddot\smile$