TY - JOUR

T1 - On r-uniform hypergraphs with circumference less than r

AU - Kostochka, Alexandr

AU - Luo, Ruth

N1 - Funding Information:
Research of this author is supported in part by NSF grant DMS-1600592 and grants 18-01-00353A and 16-01-00499 of the Russian Foundation for Basic Research.Research of this author is supported in part by Award RB17164 of the Research Board of the University of Illinois at Urbana-Champaign.
Publisher Copyright:
© 2019 Elsevier B.V.

PY - 2020/4/15

Y1 - 2020/4/15

N2 - 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.

AB - 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.

KW - Cycles and paths

KW - Extremal hypergraph theory

KW - Turán problem

UR - http://www.scopus.com/inward/record.url?scp=85070073872&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85070073872&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.07.011

DO - 10.1016/j.dam.2019.07.011

M3 - Article

AN - SCOPUS:85070073872

SN - 0166-218X

VL - 276

SP - 69

EP - 91

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -