The order dimension of divisibility

Abstract

The Dushnik-Miller dimension of a partially-ordered set $P$ is the smallest $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 equal to $(\log n{)}^2(\log \log n{)}^{-\hat{I}˜(1)}$ as $n$ goes to infinity. We prove similar bounds for the $2$-dimension of divisibility in $\{1,\dots ,n\}$, where the $2$-dimension of a poset $P$ is the smallest $d$ such that $P$ is isomorphic to a suborder of the subset lattice of $[d]$. We also prove an upper bound for the $2$-dimension of posets of bounded degree and show that the $2$-dimension of the divisibility poset on the set $(\hat{I}\pm n,n]$ is $\hat{I}{˜}_{\hat{I}}\pm (\log n)$ for $\hat{I}\pm \in (0,1)$. At the end we pose several problems.

13 pages