An Erdős–Gallai type theorem for uniform hypergraphs

Akbar Davoodi, Ervin Győri, Abhishek Methuku, Casey Tompkins

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)159-162
Number of pages4
JournalEuropean Journal of Combinatorics
Volume69
DOIs
StatePublished - Mar 2018
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'An Erdős–Gallai type theorem for uniform hypergraphs'. Together they form a unique fingerprint.

Cite this