2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Manuel Lafond May 14 '15 at 2:49
  • $\begingroup$ You are right! It has to be injective. I will edit the question... $\endgroup$ – mirelon May 14 '15 at 6:46
  • $\begingroup$ @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? $\endgroup$ – mirelon May 16 '15 at 22:13
2
$\begingroup$

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}$how Phi looks like if M is finite

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$

$\endgroup$
  • $\begingroup$ 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''$? $\endgroup$ – Brian M. Scott May 16 '15 at 7:52
  • $\begingroup$ @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). $\endgroup$ – dtldarek May 16 '15 at 8:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott May 16 '15 at 8:21
  • $\begingroup$ @BrianM.Scott You are certainly right, thanks a lot! $\endgroup$ – dtldarek May 16 '15 at 8:26
  • $\begingroup$ You’re welcome; nice answer! $\endgroup$ – Brian M. Scott May 16 '15 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.