Extremal Results for Berge Hypergraphs

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 $\mathcal{H}$ be a hypergraph. We say that a hypergraph $\mathcal{H}$ is a Berge-$G$ if there is a bijection $f : E(G) \rightarrow E(\mathcal{H})$ such that for each $e \in E(G)$ we have $e \subset 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övári--Sós--Turán theorem. In case $G$ is $C_4$, we improve the bounds given by Györi and Lemons [Discrete Math., 312, (2012), pp. 1518--1520].

The authors' abstract, as published at the source. SIAM Journal on Discrete Mathematics, 2017 · DOI ↗