pith. sign in

arxiv: 1608.03241 · v2 · pith:W2QRY2YDnew · submitted 2016-08-10 · 🧮 math.CO

An ErdH{o}s-Gallai type theorem for uniform hypergraphs

classification 🧮 math.CO
keywords lengthpathuniformbergehyperedgeshypergraphhypergraphstheorem
0
0 comments X
read the original abstract

A well-known theorem of Erd\H{o}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\H{o}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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.