{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-12","reactions":{}}