On Regular Hypergraphs of High Girth
Volume
21
Journal
Electronic Journal of Combinatorics
Issue
ISSN
1097-1440
Metadata
Show full item recordAbstract
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 Sn which has girth Ω(sqroot(log |S_n|)) with high probability, in contrast to random regular r-uniform hypergraphs, which have constant girth with positive probability.
Authors
ELLIS, DC; Linial, NURI
file:///C:/Users/ylw164/Downloads/3851-9721-1-PB.pdfhttp://qmro.qmul.ac.uk/xmlui/handle/123456789/15109
https://arxiv.org/pdf/1302.5090v4.pdf