On r-uniform hypergraphs with circumference less than r

Research output: Contribution to journalArticlepeer-review

Abstract

We show that for each k≥4 and n>r≥k+1, every n-vertex hypergraph with edge sizes at least r and no Berge cycle of length at least k has at most [Formula presented] edges. The bound is exact, and we describe the extremal hypergraphs. This implies and slightly refines the theorem of Győri, Katona and Lemons that for n>r≥k≥3, every n-vertex r-uniform hypergraph with no Berge path of length k has at most [Formula presented] edges. To obtain the bounds, we study bipartite graphs with no cycles of length at least 2k, and then translate the results into the language of multi-hypergraphs.

Original languageEnglish (US)
Pages (from-to)69-91
Number of pages23
JournalDiscrete Applied Mathematics
Volume276
DOIs
StatePublished - Apr 15 2020

Keywords

  • Cycles and paths
  • Extremal hypergraph theory
  • Turán problem

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On r-uniform hypergraphs with circumference less than r'. Together they form a unique fingerprint.

Cite this