{
  "id": "1004.3733",
  "version": "v2",
  "published": "2010-04-21T16:06:00.000Z",
  "updated": "2010-05-22T19:48:06.000Z",
  "title": "Hypergraphs do jump",
  "authors": [
    "Rahil Baber",
    "John Talbot"
  ],
  "comment": "11 pages, 1 figure, 42 page appendix of C++ code. Revised version including new Corollary 2.3 thanks to an observation of Dhruv Mubayi",
  "categories": [
    "math.CO"
  ],
  "abstract": "We say that $\\alpha\\in [0,1)$ is a jump for an integer $r\\geq 2$ if there exists $c(\\alpha)>0$ such that for all $\\epsilon >0 $ and all $t\\geq 1$ any $r$-graph with $n\\geq n_0(\\alpha,\\epsilon,t)$ vertices and density at least $\\alpha+\\epsilon$ contains a subgraph on $t$ vertices of density at least $\\alpha+c$. The Erd\\H os--Stone--Simonovits theorem implies that for $r=2$ every $\\alpha\\in [0,1)$ is a jump. Erd\\H os showed that for all $r\\geq 3$, every $\\alpha\\in [0,r!/r^r)$ is a jump. Moreover he made his famous \"jumping constant conjecture\" that for all $r\\geq 3$, every $\\alpha \\in [0,1)$ is a jump. Frankl and R\\\"odl disproved this conjecture by giving a sequence of values of non-jumps for all $r\\geq 3$. We use Razborov's flag algebra method to show that jumps exist for $r=3$ in the interval $[2/9,1)$. These are the first examples of jumps for any $r\\geq 3$ in the interval $[r!/r^r,1)$. To be precise we show that for $r=3$ every $\\alpha \\in [0.2299,0.2316)$ is a jump. We also give an improved upper bound for the Tur\\'an density of $K_4^-=\\{123,124,134\\}$: $\\pi(K_4^-)\\leq 0.2871$. This in turn implies that for $r=3$ every $\\alpha \\in [0.2871,8/27)$ is a jump.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-05-22T19:48:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05"
    ],
    "keywords": [
      "hypergraphs",
      "razborovs flag algebra method",
      "os-stone-simonovits theorem implies",
      "turan density",
      "upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1004.3733B"
    }
  }
}