Improved bounds for the dimension of divisibility

DOI10.1016/J.EJC.2023.103912MaRDI QIDQ6201893zbMATH OpenFDO

Authors Victor Souza, Leo Versteegen

Publication date 26 March 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

Cites work

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

Cited in

(1)

• Boxicity and cubicity of a subclass of divisor graphs and power graphs of cyclic groups

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)