Extremal results for berge hypergraphs

Dániel Gerbner, Cory Palmer

Research output: Contribution to journalArticlepeer-review

Abstract

Let E(G) and V (G) denote the edge set and vertex set of a (hyper)graph G. Let G be a graph and H be a hypergraph. We say that a hypergraph H is a Berge-G if there is a bijection f : E(G) → E(H) such that for each e ϵ E(G) we have e ? f(e). This generalizes the established definitions of "Berge path" and "Berge cycle" to general graphs. For a fixed graph G we examine the maximum possible size of a hypergraph with no Berge-G as a subhypergraph. In the present paper we prove general bounds for this maximum when G is an arbitrary graph. We also consider the specific case when G is a complete bipartite graph and prove an analogue of the K?ovári-Sós-Turán theorem. In case G is C4, we improve the bounds given by Gy?ori and Lemons [Discrete Math., 312, (2012), pp. 1518-1520].

Original languageEnglish
Pages (from-to)2314-2327
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number4
DOIs
StatePublished - 2017

Keywords

  • Berge hypergraphs
  • Extremal graphs
  • Extremal hypergraphs

Fingerprint

Dive into the research topics of 'Extremal results for berge hypergraphs'. Together they form a unique fingerprint.

Cite this