## 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 Δ log^{1+}o^{(1)} Δ. 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^{1+}o^{(1)} Δ, 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.

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 |