{
  "id": "math/0605246",
  "version": "v1",
  "published": "2006-05-10T18:43:17.000Z",
  "updated": "2006-05-10T18:43:17.000Z",
  "title": "On the Boxicity and Cubicity of Hypercubes",
  "authors": [
    "L. Sunil Chandran",
    "Naveen Sivadasan"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "For a graph $G$, its \\emph{cubicity} $cub(G)$ is the minimum dimension $k$ such that $G$ is representable as the intersection graph of (axis--parallel) cubes in $k$--dimensional space. Chandran, Mannino and Oriolo showed that for a $d$--dimensional hypercube $H_d$, $\\frac{d-1}{\\log d} \\le cub(H_d) \\le 2d$. In this paper, we show that $cub(H_d) = \\Theta(\\frac{d}{\\log d})$.The parameter \\emph{boxicity} generalizes cubicity: the boxicity $box(G)$ of a graph $G$ is defined as the minimum dimension $k$ such that $G$ is representable as the intersection graph of axis parallel boxes in $k$ dimensional space. Since $box(G) \\le cub(G)$ for any graph $G$, our result implies that $box(H_d) = O(\\frac{d}{\\log d})$. The problem of determining a non-trivial lower bound for $box(H_d)$ is left open.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-05-10T18:43:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "intersection graph",
      "dimensional space",
      "minimum dimension",
      "axis parallel boxes",
      "non-trivial lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......5246C"
    }
  }
}