Abstract
A well-known theorem of Erdős and Gallai (1959) [1] asserts that a graph with no path of length k contains at most [Formula presented](k−1)n edges. Recently Győri et al. (2016) gave an extension of this result to hypergraphs by determining the maximum number of hyperedges in an r-uniform hypergraph containing no Berge path of length k for all values of r and k except for k=r+1. We settle the remaining case by proving that an r-uniform hypergraph with more than n edges must contain a Berge path of length r+1.
Original language | English (US) |
---|---|
Pages (from-to) | 159-162 |
Number of pages | 4 |
Journal | European Journal of Combinatorics |
Volume | 69 |
DOIs | |
State | Published - Mar 2018 |
Externally published | Yes |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics