The order dimension of divisibility

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:179

Article

Lewis, David¹  Souza, Victor² 

[1] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA

[2] IMPA, Estr Dona Castorina 110, BR-22460320 Rio De Janeiro, Brazil

关键词: Partially ordered sets;    Dimension;    Divisibility;   

DOI  :  10.1016/j.jcta.2020.105391

来源: Elsevier

【 摘 要 】

The Dushnik-Miller dimension of a partially-ordered set Pis the smallest dsuch that one can embed Pinto a product of dlinear orders. We prove that the dimension of the divisibility order on the interval {1, ..., n}, is equal to (logn)(2)(loglogn)(-Theta(1)) as ngoes to infinity. We prove similar bounds for the 2-dimension of divisibility in {1, ..., n}, where the 2-dimension of a poset Pis the smallest dsuch that Pis 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 (alpha n, n] is Theta(alpha)(log n) for alpha is an element of(0, 1). At the end we pose several problems. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free