{
  "id": "math/0601767",
  "version": "v1",
  "published": "2006-01-31T12:40:07.000Z",
  "updated": "2006-01-31T12:40:07.000Z",
  "title": "Empty Rectangles and Graph Dimension",
  "authors": [
    "Stefan Felsner"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider rectangle graphs whose edges are defined by pairs of points in diagonally opposite corners of empty axis-aligned rectangles. The maximum number of edges of such a graph on $n$ points is shown to be 1/4 n^2 +n -2. This number also has other interpretations: * It is the maximum number of edges of a graph of dimension $\\bbetween{3}{4}$, i.e., of a graph with a realizer of the form $\\pi_1,\\pi_2,\\ol{\\pi_1},\\ol{\\pi_2}$. * It is the number of 1-faces in a special Scarf complex. The last of these interpretations allows to deduce the maximum number of empty axis-aligned rectangles spanned by 4-element subsets of a set of $n$ points. Moreover, it follows that the extremal point sets for the two problems coincide. We investigate the maximum number of of edges of a graph of dimension $\\between{3}{4}$, i.e., of a graph with a realizer of the form $\\pi_1,\\pi_2,\\pi_3,\\ol{\\pi_3}$. This maximum is shown to be $1/4 n^2 + O(n)$. Box graphs are defined as the 3-dimensional analog of rectangle graphs. The maximum number of edges of such a graph on $n$ points is shown to be $7/16 n^2 + o(n^2)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-01-31T12:40:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "68R10",
      "06A07"
    ],
    "keywords": [
      "maximum number",
      "graph dimension",
      "empty rectangles",
      "empty axis-aligned rectangles",
      "rectangle graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......1767F"
    }
  }
}