# Existence of infinite subsequence of trees with a special condition

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.

• Does $f$ need to be injective ? Otherwise we can map every $v$ to the same vertex of $T_2$, the one with the maximum number of children. – Manuel Lafond May 14 '15 at 2:49
• You are right! It has to be injective. I will edit the question... – mirelon May 14 '15 at 6:46
• @dtldarek As it turned out, the operations on trees are totally irrevelant, maybe I should delete them from the question for clarity... what do you think? – mirelon May 16 '15 at 22:13

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$

• At the end, do you mean that there are only $2^{(n^*+1)(k^*+1)}$ possibilities for $\varphi_T$ restricted to $0\le n\le n^*$ and $0\le k\le k^*$, where $T\in S''$? – Brian M. Scott May 16 '15 at 7:52
• @BrianM.Scott You are right, but in fact $\phi(0,k)$ and $\phi(n,0)$ are always true. Besides I only care if the bound is finite, it could be $(n^*+1)^{k^*+1}$ or anything else, I just wanted so that it is clear why it is finite (hence, you guessed correctly my intentions, fixed now). – dtldarek May 16 '15 at 8:19
• I was less worried about that than about your use of $\Phi_{S''}(n,k)$ where it seems that you really want $\varphi_T(n,k)$ for $T\in S''$. It really does seem to me that you’re talking about $\varphi_T$, not $\Phi_{S''}$, though I may be missing something. – Brian M. Scott May 16 '15 at 8:21
• @BrianM.Scott You are certainly right, thanks a lot! – dtldarek May 16 '15 at 8:26
• You’re welcome; nice answer! – Brian M. Scott May 16 '15 at 8:30