2025/08/05 by Kaul, Neel, Wood, David R. · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.03335
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)\leqslant O(nlog n). We point out a mistake in their proof. The previously best known upper bound is s(n)\leqslant O(n(log n)(loglog 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)\leqslant O(n(log n)(loglog n)). The best known lower bound is s(n)\geqslant Ω(nlog n). We generalise these results for graphs of treewidth k. For an integer k\geqslant 1, let sk(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)=s1(n). We show that Ω(k nlog n) \leqslant sk(n) \leqslant O(kn(log n)(loglog n)).