{
  "id": "1609.03101",
  "version": "v1",
  "published": "2016-09-10T23:58:13.000Z",
  "updated": "2016-09-10T23:58:13.000Z",
  "title": "Hamilton cycles in hypergraphs below the Dirac threshold",
  "authors": [
    "Frederik Garbe",
    "Richard Mycroft"
  ],
  "comment": "49 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We establish a precise characterisation of $4$-uniform hypergraphs with minimum codegree close to $n/2$ which contain a Hamilton $2$-cycle. As an immediate corollary we identify the exact Dirac threshold for Hamilton $2$-cycles in $4$-uniform hypergraphs. Moreover, by derandomising the proof of our characterisation we provide a polynomial-time algorithm which, given a $4$-uniform hypergraph $H$ with minimum codegree close to $n/2$, either finds a Hamilton $2$-cycle in $H$ or provides a certificate that no such cycle exists. This surprising result stands in contrast to the graph setting, in which below the Dirac threshold it is NP-hard to determine if a graph is Hamiltonian. We also consider tight Hamilton cycles in $k$-uniform hypergraphs $H$ for $k \\geq 3$, giving a series of reductions to show that it is NP-hard to determine whether a $k$-uniform hypergraph $H$ with minimum degree $\\delta(H) \\geq \\frac{1}{2}|V(H)| - O(1)$ contains a tight Hamilton cycle. It is therefore unlikely that a similar characterisation can be obtained for tight Hamilton cycles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-09-10T23:58:13.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65",
      "G.2.2"
    ],
    "keywords": [
      "uniform hypergraph",
      "tight hamilton cycle",
      "minimum codegree close",
      "exact dirac threshold",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 49,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}