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{1+o(1) Δ. This result improves on a 30-year old bound of Füredi and Kahn and is within a logo(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 Δ log1+o(1) Δ , which is also within a logo(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. [ABSTRACT FROM AUTHOR]