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.
@article{10_37236_3851,
author = {David Ellis and Nathan Linial},
title = {On regular hypergraphs of high girth},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3851},
zbl = {1300.05198},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3851/}
}
TY - JOUR
AU - David Ellis
AU - Nathan Linial
TI - On regular hypergraphs of high girth
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3851/
DO - 10.37236/3851
ID - 10_37236_3851
ER -
%0 Journal Article
%A David Ellis
%A Nathan Linial
%T On regular hypergraphs of high girth
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3851/
%R 10.37236/3851
%F 10_37236_3851
David Ellis; Nathan Linial. On regular hypergraphs of high girth. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3851
