Back to Search Start Over

$t$-Wise Berge and $t$-Heavy Hypergraphs

Authors :
Balázs Patkós
Dániel Gerbner
Máté Vizer
Dániel T. Nagy
Source :
SIAM Journal on Discrete Mathematics. 34:1813-1829
Publication Year :
2020
Publisher :
Society for Industrial & Applied Mathematics (SIAM), 2020.

Abstract

In many proofs concerning extremal parameters of Berge hypergraphs one starts with analyzing that part of that shadow graph which is contained in many hyperedges. Capturing this phenomenon we introduce two new types of hypergraphs. A hypergraph $\mathcal{H}$ is a $t$-heavy copy of a graph $F$ if there is a copy of $F$ on its vertex set such that each edge of $F$ is contained in at least $t$ hyperedges of $\mathcal{H}$. $\mathcal{H}$ is a $t$-wise Berge copy of $F$ if additionally for distinct edges of $F$ those $t$ hyperedges are distinct. We extend known upper bounds on the Tur\'an number of Berge hypergraphs to the $t$-wise Berge hypergraphs case. We asymptotically determine the Tur\'an number of $t$-heavy and $t$-wise Berge copies of long paths and cycles and exactly determine the Tur\'an number of $t$-heavy and $t$-wise Berge copies of cliques. In the case of 3-uniform hypergraphs, we consider the problem in more details and obtain additional results.<br />Comment: 20 pages

Details

ISSN :
10957146 and 08954801
Volume :
34
Database :
OpenAIRE
Journal :
SIAM Journal on Discrete Mathematics
Accession number :
edsair.doi.dedup.....b1f2187a7d2fac54a64ce76f4f9afcd3