Better bounds for poset dimension and boxicity

The dimension of a poset P is the minimum number of total orders whose intersection is P. We prove that the dimension of every poset whose comparability graph has maximum degree Δ is at most Δ log¹⁺o⁽¹⁾ Δ. This result improves on a 30-year old bound of Füredi and Kahn and is within a log^o(1) Δ 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 Δ has boxicity at most Δ log¹⁺o⁽¹⁾ Δ, which is also within a log^o(1) Δ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus g is Θ(^√g log g), which solves an open problem of Esperet and Joret and is tight up to a constant factor.