Hostname: page-component-7c8c6479df-p566r Total loading time: 0 Render date: 2024-03-29T08:19:44.169Z Has data issue: false hasContentIssue false

Hypergraphs with No Cycle of a Given Length

Published online by Cambridge University Press:  02 February 2012

ERVIN GYŐRI
Affiliation:
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)
NATHAN LEMONS
Affiliation:
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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bollobás, B. and Győri, E. (2008) Pentagons vs. triangles. Discrete Math. 308 43324336.CrossRefGoogle Scholar
[2]Bondy, J. A. and Simonovits, M. (1974) Cycles of even length in graphs. J. Combin. Theory Ser. B 16 97105.CrossRefGoogle Scholar
[3]Erdős, P. and Gallai, T. (1959) On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hungar. 10 337356.CrossRefGoogle Scholar
[4]Gyárfás, A., Jacobson, M., Kézdy, A. and Lehel, J. (2006) Odd cycles and Theta-cycles in hypergraphs. Discrete Math. 306 24812491.CrossRefGoogle Scholar
[5]Győri, E. (2006) Triangle-free hypergraphs. Combin. Probab. Comput. 15 185191.CrossRefGoogle Scholar
[6]Győri, E. and Lemons, N. 3-uniform hypergraphs avoiding a given odd cycle. Combinatorica, to appear.Google Scholar
[7]Kostochka, A. and Verstraete, J. (2005) Even cycles in hypergraphs. J. Combin. Theory Ser. B 94 173182.CrossRefGoogle Scholar