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 isibility 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Data Availibility Statement
This paper does not make use of any data.
References
Brightwell, G.R., Kierstead, H.A., Kostochka, A.V., Trotter, W.T.: The dimension of suborders of the Boolean lattice. Order 11, 127–134 (1994)
Dushnik, B.: Concerning a certain set of arrangements. Proceedings of the American Mathematical Society. 1(6), 788–796 (1950)
Dushnik, B., Miller, E.W.: Partially ordered sets. Am. J. Math. 63(3), 600–610 (1941)
Füredi, Z., Kahn, J.: On the dimensions of ordered sets of bounded degree. Order 3(1), 15–20 (1986)
Kierstead, H.A.: On the order dimension of 1-sets versus k-sets. Journal of Combinatorial Theory, Series A. 73(2), 219–228 (1996)
Kierstead, H.A.: The dimension of two levels of the Boolean lattice. Discret. Math. 201(1–3), 141–155 (1999)
Lewis, D., Souza, V.: The order dimension of divisibility. Journal of Combinatorial Theory, Series A. 179, 105391 (2021)
Nešetřil, J. and Pudlák, P.: A note on Boolean dimension of posets. In Irregularities of Partitions (pp. 137–140). Berlin, Heidelberg: Springer Berlin Heidelberg (1989)
Novák, V.: On the well dimension of ordered sets. Czechoslov. Math. J. 19(1), 1–16 (1969)
Robin, G.: Estimation de la fonction de Tchebychef \(\theta \) sur le k-ième nombre premier et grandes valeurs de la fonction \(\omega \) (n) nombre de diviseurs premiers de n. Acta Arith 42(4), 367–389 (1983)
Scott, A., Wood, D.: Better bounds for poset dimension and boxicity. Trans. Am. Math. Soc. 373(3), 2157–2172 (2020)
Souza, V. and Versteegen, L.: Improved bounds for the dimension of divisibility (2022). arXiv:2202.04001
Spencer, J.: Minimal scrambling sets of simple orders. Acta Math. Hungar. 22, 349–353 (1971)
Trotter, W.T.: Combinatorics and partially ordered sets (1992)
Acknowledgements
I would like to thank Noah Kravitz for helpful conversations and detailed feedback on earlier versions of this paper. Additionally, I am grateful to Victor Souza for bringing other divisibility orders to my attention, among other helpful comments. I would also like to thank Michael Ren and William Trotter for helpful conversations and Joe Gallian, Carl Schildkraut, Zach Hunter, and the anonymous reviewers for comments on earlier versions of this paper. Finally, I want to express my gratitude to Joe Gallian, Amanda Burcroff, Colin Defant, Noah Kravitz, and Yelena Mandelshtam for organizing the Duluth REU and the project suggestion.
Funding
Open Access funding provided by the MIT Libraries. This research was conducted at the University of Minnesota Duluth Mathematics REU and was supported, in part, by NSF-DMS Grant 1949884 and NSA Grant H98230-20-1-0009. Additional support was provided by the CYAN Mathematics Undergraduate Activities Fund.
Author information
Authors and Affiliations
Contributions
This is a single-author paper. All contributions are due to Milan Haiman.
Corresponding author
Ethics declarations
Conflict of Interest Statement
The author is not aware of any relevant conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix A. Computations for Theorem 1.7
In this appendix we show the following bound.
Proposition A.1
Let \(\textbf{v}=(\log 2,\log 3, \dots , \log p_n)\), where \(p_i\) is the ith prime. Let \(\kappa \ge 3\) be a real number, and let \(r=4\frac{\log \kappa }{\log \log \kappa }\). Then \(m(\textbf{v},r)\ge 2\log (\kappa )\).
Proof
We use [10], which provides bounds on the Chebyshev function \(\vartheta (x)=\sum _{p\le x}\log p\) (where the sum is over primes p). Note that \(m(\textbf{v},r)=\vartheta (p_{\lfloor {r}\rfloor })\). By [10, Theorem 6], we have that
Now, let \(\lambda =\log \kappa >1\) and note that \(\frac{\lambda }{\log \lambda }\ge e\). So
Let \(\eta =1.076869\) and note that \(\eta <\log (3.5)\). Using the above bounds and \(\frac{\log \log \lambda }{\log \lambda }\le \frac{1}{e}\), we have that
So \(m(\textbf{v},r)\ge 2\log \kappa \), as desired.\(\square \)
Appendix B. Computations for Theorem 1.9
In this appendix we show bounds on irreducible polynomials in \(\mathbb {F}_q[x]\). Let \(n_i\) be the number of monic irreducible polynomials of degree i. Recall that the product of all monic irreducible polynomials of degree dividing i is \(x^{q^i}-x\). In particular, this means that \(n_i\le q^i/i\). In the notation of Section 6, we have that \(n=n_1+\dots +n_{\delta }\) and \(\textbf{v}\in \mathbb {R}^n\) is a vector with \(n_i\) entries being i.
Proposition B.1
We have \(n\le q^\delta \).
Proof
We have \(n_1=q\) and for \(i\ge 2\),
So
\(\square \)
Proposition B.2
Let \(r=4.6\frac{\delta \log q}{\log \delta }\). Then \(m(\textbf{v},r)\ge 2\delta \).
Proof
For each i, \(\textbf{v}\) has \(n_1+\dots +n_{i-1}\) entries that are less than i. Thus \(m(\textbf{v},r)\) has
terms that are at least i. Then for any \(d\in \mathbb {N}\) we have
We will apply this with \(d=\lfloor {\log \delta /\log q}\rfloor +1\). Since \(\frac{\delta }{\log \delta }\ge e\) and \(\log q\ge \log 2\),
Now we have
By rearrangement,
So we have
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Haiman, M. The Dimension of Divisibility Orders and Multiset Posets. Order (2023). https://doi.org/10.1007/s11083-023-09653-7
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11083-023-09653-7