Better bounds for poset dimension and boxicity
share
We prove that the dimension of every poset whose comparability graph has maximum degree Δ is at most Δ^1+o(1)Δ. This result improves on a 30-year old bound of Füredi and Kahn, and is within a ^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 Δ^1+o(1)Δ, which is also within a ^o(1)Δ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus g is Θ(√(g g)), which solves an open problem of Esperet and Joret and is tight up to a O(1) factor.
READ FULL TEXT