REAL

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

[img]
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

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 12 Jan 2019 14:41
Last Modified: 12 Jan 2019 14:41
URI: http://real.mtak.hu/id/eprint/89782

Actions (login required)

Edit Item Edit Item