The relaxation complexity of the standard simplex is logarithmic

Abstract

For a set $X$ of integer points, the relaxation complexity $\mathrm{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 $\hat{I}{”}_d=\{0,{\mathbf{e}}_1,\dots ,{\mathbf{e}}_d\}$. We show that $\mathrm{rc}(\hat{I}{”}_d)=O(\log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $\mathrm{rc}(\hat{I}{”}_d)=O(d/\sqrt{\log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2024) and matches an asymptotic lower bound by Averkov and Schymura (2022).

5 pages, simplified construction using free join