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 $ \Delta $ is at most $ \Delta \log ^{1+o(1)} \Delta $. This result improves on a 30-year old bound of Füredi and Ka...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
American Mathematical Society
2019
|
| Summary: | 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 $ \Delta $ is at most $ \Delta \log ^{1+o(1)} \Delta $. This result improves on a 30-year old bound of Füredi and Kahn and is within a $ \log ^{o(1)}\Delta $ 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 $ \Delta $ has boxicity at most $ \Delta \log ^{1+o(1)} \Delta $, which is also within a $ \log ^{o(1)}\Delta $ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $ g$ is $ \Theta (\sqrt {g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a constant factor. |
|---|