Improved bounds for the dimension of divisibility
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910307012575232 |
|---|---|
| author | Souza, Victor Versteegen, Leo |
| author_facet | Souza, Victor Versteegen, Leo |
| contents | 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(\log n)^2 (\log \log n)^{-2} \log \log \log n$ as $n$ goes to infinity. This improves a recent result by Lewis and the first author, who showed an upper bound of $C(\log n)^2 (\log \log n)^{-1}$ and a lower bound of $c(\log n)^2 (\log \log n)^{-2}$, asymptotically. To obtain these bounds, we provide a refinement of a bound of Füredi and Kahn and exploit a connection between the dimension of the divisibility order and the maximum size of $r$-cover-free families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_04001 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Improved bounds for the dimension of divisibility Souza, Victor Versteegen, Leo Combinatorics Number Theory 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(\log n)^2 (\log \log n)^{-2} \log \log \log n$ as $n$ goes to infinity. This improves a recent result by Lewis and the first author, who showed an upper bound of $C(\log n)^2 (\log \log n)^{-1}$ and a lower bound of $c(\log n)^2 (\log \log n)^{-2}$, asymptotically. To obtain these bounds, we provide a refinement of a bound of Füredi and Kahn and exploit a connection between the dimension of the divisibility order and the maximum size of $r$-cover-free families. |
| title | Improved bounds for the dimension of divisibility |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2202.04001 |