×

The order dimension of divisibility. (English) Zbl 1498.06003

Summary: 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 )^{-\Theta(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 \((\alpha n, n]\) is \(\operatorname{\Theta}_\alpha(\log n)\) for \(\alpha \in(0, 1)\). At the end we pose several problems.

MSC:

06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angelo, R., A Cameron and Erdős conjecture on counting primitive sets, Integers, 18 (2018), A25 · Zbl 1441.11040
[2] Cameron, P. J.; Erdős, P., On the number of sets of integers with various properties, Number Theory, 1988, 61-80 (1990) · Zbl 0695.10048
[3] Dushnik, B., Concerning a certain set of arrangements, Proc. Am. Math. Soc., 1, 788-796 (1950) · Zbl 0040.29501
[4] Dushnik, B.; Miller, E. W., Partially ordered sets, Am. J. Math., 63, 600-610 (1941) · JFM 67.0157.01
[5] Füredi, Z.; Kahn, J., On the dimensions of ordered sets of bounded degree, Order, 3, 1, 15-20 (1986) · Zbl 0656.06005
[6] Kierstead, H., On the order dimension of 1-sets versus k-sets, J. Comb. Theory, Ser. A, 73, 2, 219-228 (1996) · Zbl 0834.06004
[7] Liu, H.; Pach, P. P.; Palincza, R., The number of maximum primitive sets of integers (2018)
[8] Novák, Vítězslav, On the well dimension of ordered sets, Czechoslov. Math. J., 19, 1, 1-16 (1969) · Zbl 0175.01203
[9] Scott, A.; Wood, D., Better bounds for poset dimension and boxicity, Trans. Am. Math. Soc. (2019) · Zbl 1433.05233
[10] Spencer, J., Minimal scrambling sets of simple orders, Acta Math. Hung., 22, 349-353 (1971) · Zbl 0242.05001
[11] Spencer, J., Asymptotic lower bounds for Ramsey functions, Discrete Math., 20, 69-76 (1977) · Zbl 0375.05033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.