6
$\begingroup$

It is a theorem of Otter, building on fundamental work of Pólya, that the number of unlabeled trees on $n$ vertices is $\approx C \alpha^{n} n^{-5/2}$, where $C = 0.534\ldots$ and $\alpha = 2.955\ldots$ (see https://en.wikipedia.org/wiki/Tree_(graph_theory)#Unlabeled_trees).

A naïve way to count unlabeled trees on $n$ vertices would be to take Cayley's formula for the number of labeled trees, $n^{n-2}$, and divide by $n!$ (this would be like assuming that every tree has a trivial automorphism group, which is of course not true). By Stirling's approximation, $n^{n-2}/n! \approx \frac{1}{\sqrt{2\pi}}e^{n}n^{-5/2}$, so we definitely do not get even approximately the right answer this way. However, the "power law correction" factor of $n^{-5/2}$ is still oddly correct.

Question: Is there a high level explanation for why this naïve division gives the "correct" factor of $n^{-5/2}$?

EDIT: The same factor of $n^{-5/2}$ apparently arises in the related enumeration of unlabeled outerplanar graphs (see https://doi.org/10.37236/984). I would be interested in some discussion of if this factor is a "universal power law correction" (as in e.g. self-avoiding walks in a given dimension - see https://en.wikipedia.org/wiki/Self-avoiding_walk#Universality).

EDIT 2: I think this phenomenon is discussed in the paper "Universal singular exponents in catalytic variable equations" by Michael Drmota and Marc Noy and Guan-Ru Yu (https://arxiv.org/abs/2003.07103).

Improve this question
$\endgroup$
2
  • $\begingroup$ The ratio between Otter's formula and the naive count should be the size of the automorphism group of the typical tree. I wonder if we can prove something about the structure of such automorphism groups . $\endgroup$
    – David E Speyer
    Commented Feb 14, 2022 at 14:43
  • 1
    $\begingroup$ From the statistical physics/probability point of view, the coincidence of the $n^{-5/2}$ reflects that uniform unlabeled trees and uniform labeled trees live in the same universality class as random metric spaces, namely that of Aldous' Continuum Random Tree (CRT). See Stufler, "The continuum random tree is the scaling limit of unlabeled unrooted trees" for the unlabeled case. The exponent $-5/2$ is related to the scaling of the Brownian excursion encoding a CRT. $\endgroup$
    – Timothy Budd
    Commented Feb 14, 2022 at 15:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .