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...
| Główni autorzy: | , |
|---|---|
| Format: | Journal article |
| Język: | English |
| Wydane: |
American Mathematical Society
2019
|