{
  "id": "1302.5090",
  "version": "v5",
  "published": "2013-02-20T20:00:41.000Z",
  "updated": "2017-07-12T19:53:18.000Z",
  "title": "On regular hypergraphs of high girth",
  "authors": [
    "David Ellis",
    "Nathan Linial"
  ],
  "comment": "A hole in the proof of Theorem 8 was recently pointed out by Eberhard [10]. In this version, we repair the hole, giving a slightly weaker bound. We use a very similar method to that of Eberhard in [10], where a slightly weaker variant of [13, Theorem 3] is proved; our original proof contained a similar hole to the original proof of [13, Theorem 3]",
  "categories": [
    "math.CO"
  ],
  "abstract": "We give lower bounds on the maximum possible girth of an $r$-uniform, $d$-regular hypergraph with at most $n$ vertices, using the definition of a hypergraph cycle due to Berge. These differ from the trivial upper bound by an absolute constant factor (viz., by a factor of between $3/2+o(1)$ and $2 +o(1)$). We also define a random $r$-uniform `Cayley' hypergraph on $S_n$ which has girth $\\Omega (n^{1/3})$ with high probability, in contrast to random regular $r$-uniform hypergraphs, which have constant girth with positive probability.",
  "revisions": [
    {
      "version": "v4",
      "updated": "2014-02-23T11:26:23.000Z",
      "abstract": "We give lower bounds on the maximum possible girth of an $r$-uniform, $d$-regular hypergraph with at most $n$ vertices, using the definition of a hypergraph cycle due to Berge. These differ from the trivial upper bound by an absolute constant factor (viz., by a factor of between $3/2+o(1)$ and $2 +o(1)$). We also define a random $r$-uniform `Cayley' hypergraph on $S_n$ which has girth $\\Omega (\\sqrt{\\log |S_n|})$ with high probability, in contrast to random regular $r$-uniform hypergraphs, which have constant girth with positive probability.",
      "comment": "22 pages. References added and exposition improved, thanks to the comments of an anonymous referee",
      "journal": null,
      "doi": null
    },
    {
      "version": "v5",
      "updated": "2017-07-12T19:53:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65"
    ],
    "keywords": [
      "regular hypergraph",
      "high girth",
      "trivial upper bound",
      "absolute constant factor",
      "lower bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.5090E"
    }
  }
}