Today’s entry is a Theorem of the Day:

The Panarboreal Theorem:

Let $T_n$ denote the set of all unlabelled trees on n edges and denote by $s(T_n)$ the minimum number of edges which an (n+1)-vertex graph must have in order that it contains every tree in $T_n$ as a subgraph. Then $s(T_n) \sim c\ n \ \log{n}$ where c is a constant satisfying $\frac{1}{2} \leq c \leq \frac{5}{log 4}$.

It’s thought that the upper bound on the value could be improved on – so there’s still work to be done on this problem. For more information, and some lovely diagrams of trees, see the full listing at Theorem of the Day: the Panarboreal Theorem.

This is part of the Aperiodical Advent Calendar. We’ll be posting a new surprise for you each morning until Christmas!

The tightly related question of the smallest induced universal graph for tree was recently resolved (asymptotically).

http://arxiv.org/abs/1504.02306