Avoiding long Berge cycles II, exact bounds for all $n$

Let $\mathrm{EG}_r (n, k)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph with no Berge cycles of length $k$ or longer. In the first part of this work [5], we have found exact values of $\mathrm{EG}_r (n, k)$ and described the structure of extremal hypergraphs for the case when $k-2$ divides $n-1$ and $k \geq r+3$. In this paper we determine $\mathrm{EG}_r (n, k)$ and describe the extremal hypergraphs for all $n$ when $k \geq r+4$.

Keywords

Berge cycles, extremal hypergraph theory

2010 Mathematics Subject Classification

05C35, 05C38, 05C65, 05D05

Full Text (PDF format)

The first-named author’s research was supported in part by the Hungarian National Research, Development and Innovation Office NKFIH grant K116769, and by the Simons Foundation Collaboration Grant 317487.

The second-named author’s research was supported in part by NSF grant DMS-1600592 and grants 18-01-00353A and 16-01-00499 of the Russian Foundation for Basic Research.

The third-named author’s research was supported in part by Award RB17164 of the Research Board of the University of Illinois at Urbana-Champaign.

Received 17 July 2018

Accepted 7 May 2020

Published 16 July 2021