Better bounds for poset dimension and boxicity

Alex D Scott, David R Wood

Research output: Contribution to journalArticleResearchpeer-review

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 languageEnglish
Pages (from-to)2157-2172
Number of pages16
JournalTransactions of the American Mathematical Society
Volume373
Issue number3
DOIs
Publication statusPublished - Mar 2020

Cite this