Abstract
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 Δ log1+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.
Original language | English |
---|---|
Pages (from-to) | 2157-2172 |
Number of pages | 16 |
Journal | Transactions of the American Mathematical Society |
Volume | 373 |
Issue number | 3 |
DOIs | |
Publication status | Published - Mar 2020 |