On universal graphs for trees and treewidth $k$ graphs

Abstract

Let $s(n)$ be the minimum number of edges in a graph that contains every $n$-vertex tree as a subgraph. Chung and Graham [J. London Math. Soc. 1983] claim to prove that $s(n)⩽O(n\log n)$. We point out a mistake in their proof. The previously best known upper bound is $s(n)⩽O(n(\log n)(\log \log n{)}^2)$ by Chung, Graham and Pippenger [Proc. Hungarian Coll. on Combinatorics 1976], the proof of which is missing many crucial details. We give a fully self-contained proof of the new and improved upper bound $s(n)⩽O(n(\log n)(\log \log n))$. The best known lower bound is $s(n)⩾\hat{I}\text{c◯}(n\log n)$. We generalise these results for graphs of treewidth $k$. For an integer $k⩾1$, let $s_k(n)$ be the minimum number of edges in a graph that contains every $n$-vertex graph with treewidth $k$ as a subgraph. So $s(n)=s_1(n)$. We show that $\hat{I}\text{c◯}(kn\log n)⩽s_k(n)⩽O(kn(\log n)(\log \log n))$.