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 -