
David Ellis

Nathan Linial
Keywords:
Hypergraph theory, girth
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 the symmetric group $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.