Let $T_n$ be a random tree on $n$ labelled vertices chosen equiprobably among all $n^{n - 2}$ trees, and $I(T)$ be the number of distinct independent sets of a tree $T$. I'm interested in the average number $\mathrm{E}I(T_n)$ of independent sets of a random tree, at least asymyptotically.

Here are the values for a few small values of $n$ (obtained by generating all trees and counting their independent sets with dynamic programming):

$\mathrm{E}I(T_1) = 2$

$\mathrm{E}I(T_2) = 3$

$\mathrm{E}I(T_3) = 5$

$\mathrm{E}I(T_4) = \frac{33}{4} = 8.25$

$\mathrm{E}I(T_5) = \frac{341}{25} = 13.64$

$\mathrm{E}I(T_6) = \frac{4873}{216} \sim 22.56...$

$\mathrm{E}I(T_7) = \frac{89615}{2401} \sim 37.324...$

$\mathrm{E}I(T_8) = \frac{2023745}{32768} \sim 61.7598...$

$\mathrm{E}I(T_9) = \frac{54315721}{531441} \sim 102.2046...$

$\mathrm{E}I(T_{10}) = \frac{1691484561}{10000000} \sim 169.148...$

Here are a few questions I have:

  1. The values of $\mathrm{E}I(T_n)$ seem to grow only so slightly faster than Fibonacci numbers. Naturally, we expect $\mathrm{E}I(T_n) \sim (\beta + o(1))^n$. What is the value of $\beta$? Is $\beta = \varphi = \frac{1 + \sqrt{5}}{2}$? UPD: numerically, $\beta$ seems to be around $1.657$.

  2. I cannot help but notice that the denominator of $\mathrm{E}I(T_n)$ is $n^{n - 3}$ for $n \geq 3$, that is, in the expression $S_n / n^{n - 2}$ (where $S_n$ is the total number of independent sets over all trees with $n$ vertices) exactly a factor of $n$ is cancelled out upon reduction to smallest terms. Moreover, after the cancellation we persistently observe $S_n / n \equiv 1 \pmod n$ for $n > 3$. Is all of this a coincidence that eventually goes away, or is there something special about values of $S_n$ that explains it? UPD: both patterns seem to persist for $n$ up to $100$.

  • $\begingroup$ See arxviv/0407456 by Bauer and Coulomb ; see also articles by Jennifer Zito. They both define the same useful 3-coloring of trees. $\endgroup$ – F. C. Oct 23 '17 at 9:19
  • $\begingroup$ see also mathoverflow.net/questions/102920 $\endgroup$ – F. C. Oct 26 '17 at 7:15

The exact average number of independent sets in a random labelled tree of $n$ vertices is $$ E_n = \sum_{k=0}^{n-1} \binom{n}{k} n^{1-k} (n-k)^{k-1}. $$

To prove this, use the Matrix Tree Theorem (or alternatively Ilya's method) to show that the number of labelled trees with a specified independent set of size $k$ is $n^{n-k-1} (n-k)^{k-1}$. This is certain to be a known formula.

It is unlikely that the sum has a closed form. To establish the asymptotics, one approach is to find the shape of the terms around the largest term. Apparently the largest term occurs when $k\approx cn$ where $c\approx 0.3075417$ is the solution to $$(1-c)^2 e^{-c/(1-c)}=c.$$ From this it follows that $$\lim_{n\to\infty} E_n^{1/n} = \frac{1}{(1-c)^{1-2c}\, c^c} \approx 1.655487913.$$

  • $\begingroup$ Indeed, since posting the question I have arrived at this formula myself. My estimations of asymptotics yield $\beta \approx 1.6554879$, anyone confirm this? $\endgroup$ – Mikhail Tikhomirov Oct 23 '17 at 1:48

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.