2018/07/12 by Alexandr Kostochka, Kostochka, Alexandr, Ruth Luo +1 · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1807.04683
openalex publication_date 2018/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for each k≥ 4 and n>r≥ k+1, every n-vertex r-uniform hypergraph with no Berge cycle of length at least k has at most ((k-1)(n-1))/(r) edges. The bound is exact, and we describe the extremal hypergraphs. This implies and slightly refines the theorem of Győri, Katona and Lemons that for n>r≥ k≥ 3, every n-vertex r-uniform hypergraph with no Berge path of length k has at most ((k-1)n)/(r+1) edges. To obtain the bounds, we study bipartite graphs with no cycles of length at least 2k, and then translate the results into the language of multi-hypergraphs.