{"id":"arxiv/2606.11852","url":"https://arxiv.org/abs/2606.11852","tags":["cs.DM","math.CO","math.OC"],"score":0,"title":"The relaxation complexity of the standard simplex is logarithmic","domain":"cs.DM","source":"arxiv","authors":["Gennadiy Averkov","Simon Keil","Stefan Weltge"],"reviews":0,"subject":"cs.DM","summary":"For a set $X$ of integer points, the relaxation complexity $\\operatorname{rc}(X)$ is the smallest number of facets of any polyhedron $P$ such that $P \\cap \\mathbb{Z}^d = X$. In this paper, we focus on the case where $X$ is the discrete standard simplex $Δ_d = \\{\\mathbf{0}, \\mathbf{e}_1, \\dots, \\mathbf{e}_d\\}$. We show that $\\operatorname{rc}(Δ_d) = O(\\log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $\\operatorname{rc}(Δ_d) = O(d / \\sqrt{\\log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2024) and matches an asymptotic lower bound…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}