Abstract
We show that for each k≥4 and n>r≥k+1, every n-vertex hypergraph with edge sizes at least r and no Berge cycle of length at least k has at most [Formula presented] 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 [Formula presented] 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.
Original language | English (US) |
---|---|
Pages (from-to) | 69-91 |
Number of pages | 23 |
Journal | Discrete Applied Mathematics |
Volume | 276 |
DOIs | |
State | Published - Apr 15 2020 |
Keywords
- Cycles and paths
- Extremal hypergraph theory
- Turán problem
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics