The Dimension of Divisibility Orders and Multiset Posets

Abstract

The Dushnik--Miller dimension of a poset $P$ is the least $d$ for which $P$ can be embedded into a product of $d$ chains. Lewis and Souza showed that the dimension of the divisibility order on the interval of integers $[N/\kappa ,N]$ is bounded above by $\kappa (\log \kappa {)}^{1+o(1)}$ and below by $\Omega ((\log \kappa /\log \log \kappa {)}^2)$. We improve the upper bound to $O((\log \kappa {)}^3/(\log \log \kappa {)}^2).$ We deduce this bound from a more general result on posets of multisets ordered by inclusion. We also consider other divisibility orders and give a bound for polynomials ordered by divisibility.