Improved bounds for the dimension of divisibility

Abstract

The dimension of a partially-ordered set $P$ is the smallest integer $d$ such that one can embed $P$ into a product of $d$ linear orders. We prove that the dimension of the divisibility order on the interval $\{1,\dots ,n\}$ is bounded above by $C(\log n{)}^2(\log \log n{)}^{-2}\log \log \log n$ as $n$ goes to infinity. This improves a recent result by Lewis and the first author, who showed an upper bound of $C(\log n{)}^2(\log \log n{)}^{-1}$ and a lower bound of $c(\log n{)}^2(\log \log n{)}^{-2}$, asymptotically. To obtain these bounds, we provide a refinement of a bound of Füredi and Kahn and exploit a connection between the dimension of the divisibility order and the maximum size of $r$-cover-free families.

arXiv comment12 pages, improved exposition

References in corpus (1)

• The order dimension of divisibility