{
  "id": "2001.08549",
  "version": "v1",
  "published": "2020-01-23T14:24:50.000Z",
  "updated": "2020-01-23T14:24:50.000Z",
  "title": "The order dimension of divisibility",
  "authors": [
    "David Lewis",
    "Victor Souza"
  ],
  "comment": "12 pages",
  "categories": [
    "math.CO",
    "math.NT"
  ],
  "abstract": "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, \\dotsc, 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, \\dotsc, 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 $\\{\\alpha n, \\dotsc, n\\}$ is $\\Theta_\\alpha(\\log n)$ for $\\alpha \\in (0,1)$. At the end we pose several problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-01-23T14:24:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "order dimension",
      "linear orders",
      "dushnik-miller dimension",
      "similar bounds",
      "subset lattice"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}