You're reading: Aperiodvent

Aperiodvent, Day 6: The Panarboreal Formula

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!

One Response to “Aperiodvent, Day 6: The Panarboreal Formula”

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>