Journal of Combinatorics

Volume 7 (2016)

Number 1

On $3$-uniform hypergraphs without linear cycles

Pages: 205 – 216

DOI: http://dx.doi.org/10.4310/JOC.2016.v7.n1.a8

Authors

András Gyárfás (Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary)

Ervin Gyori (Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary)

Miklós Simonovits (Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary)

Abstract

We explore properties of $3$-uniform hypergraphs $H$ without linear cycles. It is surprising that even the simplest facts about ensuring cycles in graphs can be fairly complicated to prove for hypergraphs. Our main results are that $3$-uniform hypergraphs without linear cycles must contain a vertex of strong degree at most two and must have independent sets of size at least $\frac{2 \lvert V (H) \rvert}{5}$.

Keywords

cycles in hypergraphs, independent sets in hypergraphs, linear cycles

2010 Mathematics Subject Classification

05B07, 05C65, 05D05

Full Text (PDF format)

Published 9 December 2015