Better bounds for poset dimension and boxicity

We prove that the dimension of every poset whose comparability graph has maximum degree $\mathrm{\Delta }$ is at most $\mathrm{\Delta }{\log }^{1+o(1)}\mathrm{\Delta }$. This result improves on a 30-year old bound of F"uredi and Kahn, and is within a ${\log }^{o(1)}\mathrm{\Delta }$ factor of optimal. We prove this result via the notion of boxicity. The “boxicity” of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $\mathrm{\Delta }$ has boxicity at most $\mathrm{\Delta }{\log }^{1+o(1)}\mathrm{\Delta }$, which is also within a ${\log }^{o(1)}\mathrm{\Delta }$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $\mathrm{\Theta }(\sqrt{g\log g})$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor.