General lemmas for Berge–Turán hypergraph problems

Dániel Gerbner; Abhishek Methuku; Cory Palmer

doi:10.1016/j.ejc.2020.103082

General lemmas for Berge–Turán hypergraph problems

Dániel Gerbner, Abhishek Methuku, Cory Palmer

Mathematical Sciences

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

28 Scopus citations

Abstract

For a graph F, a hypergraph H is a Berge copy of F (or a Berge-F in short), if there is a bijection f:E(F)→E(H) such that for each e∈E(F) we have e⊂f(e). A hypergraph is Berge-F-free if it does not contain a Berge copy of F. We denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by ex_r(n,Berge-F). In this paper we prove two general lemmas concerning the maximum size of a Berge-F-free hypergraph and use them to establish new results and improve several old results. In particular, we give bounds on ex_r(n,Berge-F) when F is a path (reproving a result of Győri, Katona and Lemons), a cycle (extending a result of Füredi and Özkahya), a theta graph (improving a result of He and Tait), or a K_2,t (extending a result of Gerbner, Methuku and Vizer). We establish new bounds when F is a clique (which implies extensions of results by Maherani and Shahsiah and by Gyárfás) and when F is a general tree.

Original language	English
Article number	103082
Journal	European Journal of Combinatorics
Volume	86
DOIs	https://doi.org/10.1016/j.ejc.2020.103082
State	Published - May 2020

Funding

We are grateful to the two anonymous referees for their helpful remarks. The research of Dániel Gerbner was supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office — NKFIH, Hungary under the grants K 116769 , KH 130371 , SNN 129364 and FK 132060 . The research of Abhishek Methuku was supported by IBS, Republic of Korea - R029-C1 . We are grateful to the two anonymous referees for their helpful remarks. The research of D?niel Gerbner was supported by the J?nos Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office ? NKFIH, Hungary under the grants K 116769, KH 130371, SNN 129364 and FK 132060. The research of Abhishek Methuku was supported by IBS, Republic of Korea -R029-C1.

Funders	Funder number
Institute for Basic Science
K 116769, SNN 129364, KH 130371, FK 132060

Access to Document

10.1016/j.ejc.2020.103082

Cite this

@article{c30b6ce62de84974bd47ca6b94d865eb,

title = "General lemmas for Berge–Tur{\'a}n hypergraph problems",

abstract = "For a graph F, a hypergraph H is a Berge copy of F (or a Berge-F in short), if there is a bijection f:E(F)→E(H) such that for each e∈E(F) we have e⊂f(e). A hypergraph is Berge-F-free if it does not contain a Berge copy of F. We denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by exr(n,Berge-F). In this paper we prove two general lemmas concerning the maximum size of a Berge-F-free hypergraph and use them to establish new results and improve several old results. In particular, we give bounds on exr(n,Berge-F) when F is a path (reproving a result of Gy{\H o}ri, Katona and Lemons), a cycle (extending a result of F{\"u}redi and {\"O}zkahya), a theta graph (improving a result of He and Tait), or a K2,t (extending a result of Gerbner, Methuku and Vizer). We establish new bounds when F is a clique (which implies extensions of results by Maherani and Shahsiah and by Gy{\'a}rf{\'a}s) and when F is a general tree.",

author = "D{\'a}niel Gerbner and Abhishek Methuku and Cory Palmer",

note = "Publisher Copyright: {\textcopyright} 2020 Elsevier Ltd",

year = "2020",

month = may,

doi = "10.1016/j.ejc.2020.103082",

language = "English",

volume = "86",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

}

TY - JOUR

T1 - General lemmas for Berge–Turán hypergraph problems

AU - Gerbner, Dániel

AU - Methuku, Abhishek

AU - Palmer, Cory

PY - 2020/5

Y1 - 2020/5

N2 - For a graph F, a hypergraph H is a Berge copy of F (or a Berge-F in short), if there is a bijection f:E(F)→E(H) such that for each e∈E(F) we have e⊂f(e). A hypergraph is Berge-F-free if it does not contain a Berge copy of F. We denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by exr(n,Berge-F). In this paper we prove two general lemmas concerning the maximum size of a Berge-F-free hypergraph and use them to establish new results and improve several old results. In particular, we give bounds on exr(n,Berge-F) when F is a path (reproving a result of Győri, Katona and Lemons), a cycle (extending a result of Füredi and Özkahya), a theta graph (improving a result of He and Tait), or a K2,t (extending a result of Gerbner, Methuku and Vizer). We establish new bounds when F is a clique (which implies extensions of results by Maherani and Shahsiah and by Gyárfás) and when F is a general tree.

AB - For a graph F, a hypergraph H is a Berge copy of F (or a Berge-F in short), if there is a bijection f:E(F)→E(H) such that for each e∈E(F) we have e⊂f(e). A hypergraph is Berge-F-free if it does not contain a Berge copy of F. We denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by exr(n,Berge-F). In this paper we prove two general lemmas concerning the maximum size of a Berge-F-free hypergraph and use them to establish new results and improve several old results. In particular, we give bounds on exr(n,Berge-F) when F is a path (reproving a result of Győri, Katona and Lemons), a cycle (extending a result of Füredi and Özkahya), a theta graph (improving a result of He and Tait), or a K2,t (extending a result of Gerbner, Methuku and Vizer). We establish new bounds when F is a clique (which implies extensions of results by Maherani and Shahsiah and by Gyárfás) and when F is a general tree.

UR - https://www.scopus.com/pages/publications/85078103547

U2 - 10.1016/j.ejc.2020.103082

DO - 10.1016/j.ejc.2020.103082

M3 - Article

AN - SCOPUS:85078103547

SN - 0195-6698

VL - 86

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103082

ER -

General lemmas for Berge–Turán hypergraph problems

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this