Timeline for Number of paths through infinite trees with given "growth rates"
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2014 at 20:02 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
added 16 characters in body
|
| Nov 10, 2014 at 19:53 | history | edited | Emil Jeřábek | CC BY-SA 3.0 |
added 5309 characters in body
|
| Nov 9, 2014 at 21:16 | comment | added | Emil Jeřábek | My calculation indicates that this won’t work. That is, in the $f(n)\ge n$ case, there will always be a countable tree if $A$ is sparse enough and $\epsilon<1$. In the case where $f(n)$ is constant except for the multiplication steps, one needs $\epsilon\ge\varphi^{-1}$ to prohibit countable trees; but in this case there is not much point anyway, as doubling already gives the optimal result (one can get $f$ bounded by an arbitrary unbounded function). | |
| Nov 8, 2014 at 17:46 | comment | added | Joel David Hamkins | I think perhaps you don't need actually to double, but just ensure that a fixed proportion branch? For example, wouldn't it be fine if you multiplied by $(1+\epsilon)$ instead of 2, using my argument about measure to see that there is positive measure of branches (in the space of full-branching paths on those levels)? I'm not quite sure about this. | |
| Nov 8, 2014 at 17:12 | comment | added | Joel David Hamkins | That's fine. I think the OP is wrong to require $f(n)\geq n$, since there is an interesting phenomenon even without this, as the argument shows. One can make the growth rate arbitrarily low, below any increasing unbounded positive function, using the wait-long-enough-and-then-double idea, and still force that any tree with that growth pattern has continuum many branches. | |
| Nov 8, 2014 at 17:07 | comment | added | Emil Jeřábek | The "suitable" in the theorem is intended to mean what your last comment suggests, but I was hoping no one will press the point so that I can omit the distracting explanation. Re your previous comment: the question demands $f(n)\ge n$, which means I need $f(n+1)\ge2n$ at the doubling points (and that what I wrote above about $f(n+1)=f(n)$ is not quite correct). With imperfect doubling, I can get $f_c(n)\le\max\{2n-c,n\}$ for any constant $c$. | |
| Nov 7, 2014 at 15:51 | comment | added | Joel David Hamkins | Another silly point is that it should be part of your theorem that indeed there is a binary tree with growth rate $f$, because otherwise the theorem could become vacuous by using a function that has at least one $n$ where $f(n+1)>2f(n)$, since in this case no binary tree $T$ could have growth rate $f$. | |
| Nov 7, 2014 at 15:49 | comment | added | Joel David Hamkins | In your theorem, can't you get your growth rate lower than what you state? I think you can get $f$ below any increasing unbounded positive function---just wait long enough before doubling. | |
| Nov 7, 2014 at 15:30 | comment | added | Emil Jeřábek | Hmm. At the very least $\liminf_n2f(n)-f(n+1)<+\infty$ guarantees that the tree has $2^\omega$ paths (as the liminf bounds the number of isolated paths), but this is clearly too strong a condition. | |
| Nov 7, 2014 at 15:03 | comment | added | Emil Jeřábek | I don’t have the time to think more about it at the moment, but it seems to me that the right parameter that decides whether there are countable trees should be something in the spirit of $\limsup_{n\to\infty}\frac{f(n+1)}{f(n)}$. | |
| Nov 7, 2014 at 15:01 | comment | added | Emil Jeřábek | Yes, $f(n+1)=f(n)$ works just the same, it’s just that I was under the unwarranted impression that the question insisted on $f(n+1)>f(n)$. | |
| Nov 7, 2014 at 12:27 | comment | added | Joel David Hamkins | It also seems natural to define $f_A(n+1)=f_A(n)$ in your second case, rather than $f_A(n)+1$ as you have done. This gets the same effect, but now the point is that the tree would have full splitting at levels $n\in A$, and no splitting at levels not in $A$. | |
| Nov 7, 2014 at 12:20 | comment | added | Joel David Hamkins | +1. It is interesting that any tree with growth rate exactly $f_A$ has continuum many branches, but the construction in my answer provides trees with growth rate exceeding $f_A$ (provided $A$ is co-infinite) with only countably many branches. So a tree can have a higher growth rate, but fewer branches. | |
| Nov 7, 2014 at 11:45 | history | answered | Emil Jeřábek | CC BY-SA 3.0 |