An Erdős–Gallai type theorem for uniform hypergraphs

Davoodi, A. and Győri, Ervin and Methuku, Abhishek and Tompkins, Casey (2018) An Erdős–Gallai type theorem for uniform hypergraphs. EUROPEAN JOURNAL OF COMBINATORICS, 69. pp. 159-162. ISSN 0195-6698

Preview

Text 1608.03241v2.pdf Download (79kB) | Preview

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. © 2017 Elsevier Ltd

Actions (login required)

Edit Item