Combinatorics, Probability and Computing

Paper

Hypergraphs with No Cycle of a Given Length

ERVIN GYŐRIa1 and NATHAN LEMONSa1

a1 Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest H-1364, PO box 127, Hungary (e-mail: ervin@renyi.hu, nathan@renyi.hu)

Abstract

Recently, the authors gave upper bounds for the size of 3-uniform hypergraphs avoiding a given odd cycle using the definition of a cycle due to Berge. In the present paper we extend this bound to m-uniform hypergraphs (for all m ≥ 3), as well as m-uniform hypergraphs avoiding a cycle of length 2k. Finally we consider non-uniform hypergraphs avoiding cycles of length 2k or 2k + 1. In both cases we can bound |h| by O(n1+1/k) under the assumption that all h ∈ ε() satisfy |h| ≥ 4k2.

(Received March 31 2011)

(Revised November 10 2011)

(Online publication February 02 2012)

Footnotes

Research partially supported by the Hungarian OTKA Grant NK 78439 and by ToK project FIST of the Rényi Institute in the sixth framework programme of the European Union.

Research partially supported by ToK project FIST of Rényi Institute in the sixth framework programme of the European Union.