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
|
| _version_ | 1826261942920019968 |
|---|---|
| author | Scott, A Wood, DR |
| author_facet | Scott, A Wood, DR |
| author_sort | Scott, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T19:28:31Z |
| format | Journal article |
| id | oxford-uuid:1ca270d1-5e74-46b3-abd5-ccbec2943d41 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:28:31Z |
| publishDate | 2019 |
| publisher | American Mathematical Society |
| record_format | dspace |
| spelling | oxford-uuid:1ca270d1-5e74-46b3-abd5-ccbec2943d412022-03-26T11:06:40ZBetter bounds for poset dimension and boxicityJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:1ca270d1-5e74-46b3-abd5-ccbec2943d41EnglishSymplectic Elements at OxfordAmerican Mathematical Society2019Scott, AWood, DRThe 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. |
| spellingShingle | Scott, A Wood, DR Better bounds for poset dimension and boxicity |
| title | Better bounds for poset dimension and boxicity |
| title_full | Better bounds for poset dimension and boxicity |
| title_fullStr | Better bounds for poset dimension and boxicity |
| title_full_unstemmed | Better bounds for poset dimension and boxicity |
| title_short | Better bounds for poset dimension and boxicity |
| title_sort | better bounds for poset dimension and boxicity |
| work_keys_str_mv | AT scotta betterboundsforposetdimensionandboxicity AT wooddr betterboundsforposetdimensionandboxicity |