Avoiding long Berge cycles

Zoltán Füredi; Alexandr Kostochka; Ruth Luo

doi:10.1016/j.jctb.2018.12.001

Avoiding long Berge cycles

Zoltán Füredi, Alexandr Kostochka, Ruth Luo

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let n≥k≥r+3 and H be an n-vertex r-uniform hypergraph. We show that if |H|>[Formula presented](k−1r) then H contains a Berge cycle of length at least k. This bound is tight when k−2 divides n−1. We also show that the bound is attained only for connected r-uniform hypergraphs in which every block is the complete hypergraph K _k−1 ^(r) .

Original language	English (US)
Pages (from-to)	55-64
Number of pages	10
Journal	Journal of Combinatorial Theory. Series B
Volume	137
DOIs	https://doi.org/10.1016/j.jctb.2018.12.001
State	Published - Jul 2019

Keywords

Berge cycles
Extremal hypergraph theory

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/j.jctb.2018.12.001

Library availability

Discover UIUC Full Text

Cite this

@article{6ec684832cdb4fb8931fe62cedabbc00,

title = "Avoiding long Berge cycles",

abstract = " Let n≥k≥r+3 and H be an n-vertex r-uniform hypergraph. We show that if |H|>[Formula presented](k−1r) then H contains a Berge cycle of length at least k. This bound is tight when k−2 divides n−1. We also show that the bound is attained only for connected r-uniform hypergraphs in which every block is the complete hypergraph K k−1 (r) .",

keywords = "Berge cycles, Extremal hypergraph theory",

author = "Zolt{\'a}n F{\"u}redi and Alexandr Kostochka and Ruth Luo",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier Inc.",

year = "2019",

month = jul,

doi = "10.1016/j.jctb.2018.12.001",

language = "English (US)",

volume = "137",

pages = "55--64",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Avoiding long Berge cycles

AU - Füredi, Zoltán

AU - Kostochka, Alexandr

AU - Luo, Ruth

PY - 2019/7

Y1 - 2019/7

N2 - Let n≥k≥r+3 and H be an n-vertex r-uniform hypergraph. We show that if |H|>[Formula presented](k−1r) then H contains a Berge cycle of length at least k. This bound is tight when k−2 divides n−1. We also show that the bound is attained only for connected r-uniform hypergraphs in which every block is the complete hypergraph K k−1 (r) .

AB - Let n≥k≥r+3 and H be an n-vertex r-uniform hypergraph. We show that if |H|>[Formula presented](k−1r) then H contains a Berge cycle of length at least k. This bound is tight when k−2 divides n−1. We also show that the bound is attained only for connected r-uniform hypergraphs in which every block is the complete hypergraph K k−1 (r) .

KW - Berge cycles

KW - Extremal hypergraph theory

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

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

U2 - 10.1016/j.jctb.2018.12.001

DO - 10.1016/j.jctb.2018.12.001

M3 - Article

AN - SCOPUS:85057994672

SN - 0095-8956

VL - 137

SP - 55

EP - 64

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Avoiding long Berge cycles

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this