Turán numbers for Berge-hypergraphs and related extremal problems

Cory Palmer, Michael Tait, Craig Timmons, Adam Zsolt Wagner

Research output: Contribution to journalArticlepeer-review

Abstract

Let F be a graph. We say that a hypergraph H is a Berge-F if there is a bijection f:E(F)→E(H) such that e⊆f(e) for every e∈E(F). Note that Berge-F actually denotes a class of hypergraphs. The maximum number of edges in an n-vertex r-graph with no subhypergraph isomorphic to any Berge-F is denoted ex r (n,Berge-F). In this paper, we investigate the case when F=K s,t and establish an upper-bound when r≥3, and a lower-bound when r=4 and t is large enough compared to s. Additionally, we prove a counting result for r-graphs of girth five that complements the asymptotic formula ex 3 (n,Berge-{C 2 ,C 3 ,C 4 })=[Formula presented]n 3∕2 +o(n 3∕2 ) of Lazebnik and Verstraëte (2003).

Original languageEnglish
Pages (from-to)1553-1563
Number of pages11
JournalDiscrete Mathematics
Volume342
Issue number6
DOIs
StatePublished - Jun 2019

Keywords

  • Berge-hypergraph
  • Turán number
  • extremal problems

Fingerprint

Dive into the research topics of 'Turán numbers for Berge-hypergraphs and related extremal problems'. Together they form a unique fingerprint.

Cite this