Hypergraph Based Berge Hypergraphs

Martin Balko; Dániel Gerbner; Dong Yeap Kang; Younjin Kim; Cory Palmer

doi:10.1007/s00373-021-02419-1

Hypergraph Based Berge Hypergraphs

Martin Balko, Dániel Gerbner, Dong Yeap Kang, Younjin Kim, Cory Palmer

Mathematical Sciences

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

2 Scopus citations

Abstract

Fix a hypergraph F. A hypergraph H is called a Berge copy of F or Berge-F if we can choose a subset of each hyperedge of H to obtain a copy of F. A hypergraph H is Berge-F-free if it does not contain a subhypergraph which is Berge copy of F. This is a generalization of the usual, graph-based Berge hypergraphs, where F is a graph. In this paper, we study extremal properties of hypergraph based Berge hypergraphs and generalize several results from the graph-based setting. In particular, we show that for any r-uniform hypergraph F, the sum of the sizes of the hyperedges of a (not necessarily uniform) Berge-F-free hypergraph H on n vertices is o(n^r) when all the hyperedges of H are large enough. We also give a connection between hypergraph based Berge hypergraphs and generalized hypergraph Turán problems.

Original language	English
Article number	11
Journal	Graphs and Combinatorics
Volume	38
Issue number	1
DOIs	https://doi.org/10.1007/s00373-021-02419-1
State	Published - Feb 2022

Funding

M. Balko was supported by the Grant No. 19-04113Y of the Czech Science Foundation (GAČR) and by the Center for Foundations of Modern Computer Science (Charles University project UNCE/SCI/004). D. Gerbner was supported in part by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office - NKFIH under the Grants K 116769, KH 130371 and SNN 12936. D. Kang was supported by the Institute for Basic Science, No. IBS-R029-C1, and the research leading to these results was also supported by the EPSRC, grant nos. EP/N019504/1. Y. Kim was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1A6A3A04005963). C. Palmer was supported by a grant from the Simons Foundation #712036.

Funders	Funder number
Simons Foundation	712036
UNCE/SCI/004
Engineering and Physical Sciences Research Council	EP/N019504/1
Ministry of Education	2017R1A6A3A04005963
Institute for Basic Science	IBS-R029-C1
K 116769, SNN 12936, KH 130371

Keywords

Berge hypergraphs
Sypergraph Turán problems

Access to Document

10.1007/s00373-021-02419-1

Cite this

@article{8a13103455b74f29b59f8ff606682207,

title = "Hypergraph Based Berge Hypergraphs",

abstract = "Fix a hypergraph F. A hypergraph H is called a Berge copy of F or Berge-F if we can choose a subset of each hyperedge of H to obtain a copy of F. A hypergraph H is Berge-F-free if it does not contain a subhypergraph which is Berge copy of F. This is a generalization of the usual, graph-based Berge hypergraphs, where F is a graph. In this paper, we study extremal properties of hypergraph based Berge hypergraphs and generalize several results from the graph-based setting. In particular, we show that for any r-uniform hypergraph F, the sum of the sizes of the hyperedges of a (not necessarily uniform) Berge-F-free hypergraph H on n vertices is o(nr) when all the hyperedges of H are large enough. We also give a connection between hypergraph based Berge hypergraphs and generalized hypergraph Tur{\'a}n problems.",

keywords = "Berge hypergraphs, Sypergraph Tur{\'a}n problems",

author = "Martin Balko and D{\'a}niel Gerbner and Kang, \{Dong Yeap\} and Younjin Kim and Cory Palmer",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.",

year = "2022",

month = feb,

doi = "10.1007/s00373-021-02419-1",

language = "English",

volume = "38",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Hypergraph Based Berge Hypergraphs

AU - Balko, Martin

AU - Gerbner, Dániel

AU - Kang, Dong Yeap

AU - Kim, Younjin

AU - Palmer, Cory

PY - 2022/2

Y1 - 2022/2

N2 - Fix a hypergraph F. A hypergraph H is called a Berge copy of F or Berge-F if we can choose a subset of each hyperedge of H to obtain a copy of F. A hypergraph H is Berge-F-free if it does not contain a subhypergraph which is Berge copy of F. This is a generalization of the usual, graph-based Berge hypergraphs, where F is a graph. In this paper, we study extremal properties of hypergraph based Berge hypergraphs and generalize several results from the graph-based setting. In particular, we show that for any r-uniform hypergraph F, the sum of the sizes of the hyperedges of a (not necessarily uniform) Berge-F-free hypergraph H on n vertices is o(nr) when all the hyperedges of H are large enough. We also give a connection between hypergraph based Berge hypergraphs and generalized hypergraph Turán problems.

AB - Fix a hypergraph F. A hypergraph H is called a Berge copy of F or Berge-F if we can choose a subset of each hyperedge of H to obtain a copy of F. A hypergraph H is Berge-F-free if it does not contain a subhypergraph which is Berge copy of F. This is a generalization of the usual, graph-based Berge hypergraphs, where F is a graph. In this paper, we study extremal properties of hypergraph based Berge hypergraphs and generalize several results from the graph-based setting. In particular, we show that for any r-uniform hypergraph F, the sum of the sizes of the hyperedges of a (not necessarily uniform) Berge-F-free hypergraph H on n vertices is o(nr) when all the hyperedges of H are large enough. We also give a connection between hypergraph based Berge hypergraphs and generalized hypergraph Turán problems.

KW - Berge hypergraphs

KW - Sypergraph Turán problems

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

U2 - 10.1007/s00373-021-02419-1

DO - 10.1007/s00373-021-02419-1

M3 - Article

AN - SCOPUS:85121426691

SN - 0911-0119

VL - 38

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 1

M1 - 11

ER -

Hypergraph Based Berge Hypergraphs

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this