Improved bounds for the dimension of divisibility

DOI10.1016/J.EJC.2023.103912arXiv2202.04001MaRDI QIDQ6201893FDOQ6201893

Authors: Victor Souza, Leo Versteegen 

Publication date: 26 March 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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,dotsc,n$ is bounded above by $C(logn{)}^2(loglogn{)}^{-2}logloglogn$ as $n$ goes to infinity. This improves a recent result by Lewis and the first author, who showed an upper bound of $C(logn{)}^2(loglogn{)}^{-1}$ and a lower bound of $c(logn{)}^2(loglogn{)}^{-2}$, asymptotically. Our method exploits a connection between the dimension of the divisibility order and the maximum size of $r$-cover-free families.

Full work available at URL: https://arxiv.org/abs/2202.04001

Mathematics Subject Classification ID

Enumerative combinatorics (05Axx) Ordered sets (06Axx) Set theory (03Exx)

Cites Work

• On the order dimension of 1-sets versus \(k\)-sets
• Minimal scrambling sets of simple orders
• Concerning a Certain Set of Arrangements
• On the dimensions of ordered sets of bounded degree
• Families of finite sets in which no set is covered by the union of \(r\) others
• The dimension of two levels of the Boolean lattice
• The order dimension of divisibility

This page was built for publication: Improved bounds for the dimension of divisibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201893)