{
  "id": "math/0608610",
  "version": "v2",
  "published": "2006-08-24T17:54:28.000Z",
  "updated": "2006-10-25T14:06:33.000Z",
  "title": "New lower bounds for the number of $(\\leq k)$-edges and the rectilinear crossing number of $K_n$",
  "authors": [
    "Oswin Aichholzer",
    "Jesús García",
    "David Orden",
    "Pedro Ramos"
  ],
  "comment": "14 pages, 4 figures, submitted to Discrete and Computational Geometry, fixed a gap in the proof of Theorem 10",
  "categories": [
    "math.CO"
  ],
  "abstract": "We provide a new lower bound on the number of $(\\leq k)$-edges of a set of $n$ points in the plane in general position. We show that for $0 \\leq k \\leq\\lfloor\\frac{n-2}{2}\\rfloor$ the number of $(\\leq k)$-edges is at least $$ E_k(S) \\geq 3\\binom{k+2}{2} + \\sum_{j=\\lfloor\\frac{n}{3}\\rfloor}^k (3j-n+3), $$ which, for $k\\geq \\lfloor\\tfrac{n}{3}\\rfloor$, improves the previous best lower bound in [J. Balogh, G. Salazar, Improved bounds for the number of ($\\leq k$)-sets, convex quadrilaterals, and the rectilinear crossing number of $K_n$]. As a main consequence, we obtain a new lower bound on the rectilinear crossing number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by $n$ points in the plane in general position. We show that the crossing number is at least $$ \\Bigl({41/108}+\\epsilon \\Bigr) \\binom{n}{4} + O(n^3) \\geq 0.379631 \\binom{n}{4} + O(n^3), $$ which improves the previous bound of $0.37533 \\binom{n}{4} + O(n^3)$ in [J. Balogh, G. Salazar, Improved bounds for the number of ($\\leq k$)-sets, convex quadrilaterals, and the rectilinear crossing number of $K_n$] and approaches the best known upper bound $0.38058\\binom{n}{4}$ in [O. Aichholzer, H. Krasser, Abstract order type extension and new results on the rectilinear crossing number].",
  "revisions": [
    {
      "version": "v2",
      "updated": "2006-10-25T14:06:33.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C35"
    ],
    "keywords": [
      "rectilinear crossing number",
      "convex quadrilaterals",
      "general position",
      "abstract order type extension",
      "best lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......8610A"
    }
  }
}