An Erdős-Gallai type theorem for uniform hypergraphs

Abstract

A well-known theorem of Erdős and Gallai asserts that a graph with no path of length $k$ contains at most $\frac{1}{2}(k-1)n$ edges. Recently Győri, Katona and Lemons 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$ hyperedges must contain a Berge path of length $r+1$.

Improved the writing following the suggestions of the referees. Published version available via http://www.sciencedirect.com/science/article/pii/S0195669817301658

Cited by in corpus (6)

• Counting copies of a fixed subgraph in $F$-free graphs
• On $r$-uniform hypergraphs with circumference less than $r$
• Minimum degree of 3-graphs without long linear paths
• On 2-connected hypergraphs with no long cycles
• A Dirac-type theorem for uniform hypergraphs
• Anti-Ramsey numbers of paths and cycles in hypergraphs