{
  "id": "1708.08037",
  "version": "v1",
  "published": "2017-08-27T02:04:20.000Z",
  "updated": "2017-08-27T02:04:20.000Z",
  "title": "Thrackles: An Improved Upper Bound",
  "authors": [
    "Radoslav Fulek",
    "János Pach"
  ],
  "comment": "Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)",
  "categories": [
    "math.CO"
  ],
  "abstract": "A {\\em thrackle} is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of $n$ vertices has at most $1.3984n$ edges. {\\em Quasi-thrackles} are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an {\\em odd} number of times. It is also shown that the maximum number of edges of a quasi-thrackle on $n$ vertices is ${3\\over 2}(n-1)$, and that this bound is best possible for infinitely many values of $n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-27T02:04:20.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "upper bound",
      "common end vertex",
      "edges meet",
      "graph drawn",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}