Timeline for Multivariate Generating Function Related to Lambert $W$ Function and Counting Trees with a Certain Property
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 4, 2017 at 8:28 | vote | accept | Jon Noel | ||
| Jul 3, 2017 at 17:44 | answer | added | esg | timeline score: 1 | |
| Jun 7, 2017 at 17:03 | comment | added | esg | You're right (and my assumption above probably false). The branching process perspective suggests that the limiting distribution of the no. of nodes in the highest level should be a discrete distribution concentrated on positive integers (maybe even degenerate). This might be known, if so, it can possibly be found in Pavlov's book "Random Forests". Else you'll have to analyse the g.f. yourself (using the saddle point method). I would first try to find the asymptotic distribution of the number of nodes in height $k$ in a random tree of height $k$ for fixed $k$ and then try to extend. | |
| Jun 6, 2017 at 19:14 | comment | added | Jon Noel | It seems unlikely to me that a random tree would have $\sqrt{n}$ vertices in its highest level. If you think of it as a branching process (I don't claim that this is the correct intuition) it seems that, out of a set of $\sqrt{n}$ vertices, it is quite likely that at least one of them will have a child. I would actually guess that the average number of vertices in the last level converges to a constant as $n$ tends to infinity (but this is a guess). In particular, it might be the case that the probability that a random tree has $k$ vertices in the last level decays exponentially with $k$. | |
| Jun 6, 2017 at 18:43 | comment | added | esg | (1) True, but it shows that the order of the no. of nodes at maximal height is not higher than $\sqrt{n}$. (2) It is plausible that $\sqrt{n}$ is the correct order, since by the results of Stepanov (see epubs.siam.org/doi/10.1137/1114007) and Meir&Moon (see cms.math.ca/10.4153/CJM-1978-085-0) asymptotically each layer (stratum) at height $x\sqrt{n}$ of a rooted random tree with $n$ nodes contains of order $\sqrt{n}$ nodes, moreover asymptotically a randomly chosen node lies at a height of order $\sqrt{n}$. Question: how precise do you need this information to be made? | |
| Jun 5, 2017 at 22:19 | comment | added | Jon Noel | Perhaps... But this doesn't seem to tell me how many vertices are at maximum distance from the root. | |
| Jun 3, 2017 at 15:56 | comment | added | esg | The height $H_n$ of a random rooted Cayley tree with $n$ nodes is of order $\sqrt{n}$, more precisely: the distribution of $H_n/\sqrt{n}$ converges to the Kolmogorov-Smirnov distribution as $n\longrightarrow \infty$. This is a special case of the results here epubs.siam.org/doi/10.1137/1128044. | |
| Jun 2, 2017 at 22:34 | comment | added | Jon Noel | @SergeyDovgal Thanks. Yes, I have come across that paper. This one cambridge.org/core/services/aop-cambridge-core/content/view/… by Renyi and Szekeres is actually even more relevant (in fact, the function $F_k(x,z)$ appears in that paper; see equation (2.9)). It looks to me like their methods probably can't be directly applied here. However, I'm not completely sure... I am not an expert in analytic methods and find their paper really tough to read... also the same goes for the Flajolet and Odlyzko paper... really tough. | |
| Jun 2, 2017 at 13:38 | comment | added | Sergey Dovgal | Did you take a look at "The average height of binary trees and other simple trees" by Flajolet and Odlyzko? hal.archives-ouvertes.fr/inria-00076505/document This is not exactly the same model, but might be relevant | |
| Jun 2, 2017 at 10:11 | history | edited | Jon Noel | CC BY-SA 3.0 |
edited tags
|
| Jun 2, 2017 at 10:02 | history | edited | Jon Noel |
edited tags
|
|
| Jun 2, 2017 at 8:04 | history | edited | Jon Noel | CC BY-SA 3.0 |
added 24 characters in body
|
| Jun 2, 2017 at 7:48 | history | asked | Jon Noel | CC BY-SA 3.0 |