On regular hypergraphs of high girth (Q405152)

Summary: 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.