7
$\begingroup$

It is well known that the number of labelled trees on $n$ vertices is equal to $n^{n-2}$.

  1. We do not expect any such exact formula for the number of isomorphism types of trees on $n$ vertices. But what are the sharpest asymptotics, or best upper and lower bounds known, as $n \to \infty$?
  2. Has anyone studied the number of homeomorphism types of trees on $n$ vertices? Again, I don't expect an exact answer, and am mostly interested in the asymptotics as $n \to \infty$.
$\endgroup$

1 Answer 1

17
$\begingroup$

For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2} $ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics" (see p.481) with the main ingredients being singularity analysis and the relation $$I(z)=H(z)-\frac{1}{2}\left(H(z)^2-H(z^2)\right)$$ where $I$ is the generating function for unrooted unlabelled trees and $H$ is the generating function for rooted unlabelled trees. This is all originally from Otter's paper "The Number of Trees" from Annals of Mathematics, Vol 49, no.3 pp. 583-599.

For Q2, homeomorphism classes of trees on $n$ vertices correspond to homeomorphically irreducible trees (also sometimes called series-reduced tress, or topological trees, see OEIS) of at most $n$ vertices. This enumeration problem appears in the movie Good Will Hunting and there is even a numberphile video about it.

These were enumerated by Harary and Prins in

Frank Harary and Geert Prins, "The number of homeomorphically irreducible trees and other species" Acta Math., 101 (1959), 141-162

and for the asymptotics see

F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503

I also believe that both Q1 and Q2 are exposited in the book "Graphical Enumeration" by Harary and Palmer, but I'll have to check.

$\endgroup$
2
  • $\begingroup$ Huh, I've routinely heard the result from Q1 attributed to Polya. $\endgroup$ Jul 16, 2020 at 21:57
  • 1
    $\begingroup$ @SamHopkins It was originally investigated by (among others) Cayley, then Polya (rooted case), then finally Otter in the form I mention above. $\endgroup$ Jul 16, 2020 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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