Id: arxiv/2602.11840 Url: https://arxiv.org/abs/2602.11840 Tags: math.CO Score: 0 Title: Improved Universal Graphs for Trees Domain: math.CO Source: arxiv Authors: Julian Becker, Konstantinos Panagiotou, Matija Pasch Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-12 Page: https://delphi.science/r/arxiv/2602.11840 A graph $G$ is universal for a class of graphs $\mathcal{C}$, if, up to isomorphism, $G$ contains every graph in $\mathcal{C}$ as a subgraph. In 1978, Chung and Graham asked for the minimal number $s(n)$ of edges in a graph with $n$ vertices that is universal for all trees with $n$ vertices. The currently best bounds assert that $n\ln n-O(n)\le s(n) \le C n\ln n+O(n)$, where $C = \frac{14}{5\ln 2} \approx 4.04$. We improve the upper bound to $c n\ln n + O(n)$, where $c = \frac{19}{6\ln 3} \approx 2.88$. In the proof we develop a strategy that, broadly speaking, is based on separating trees…