Linearity of Saturation for Berge Hypergraphs

Abstract

For a graph $F$, we say a hypergraph $H$ is Berge-$F$ if it can be obtained from $F$ be replacing each edge of $F$ with a hyperedge containing it. We say a hypergraph is Berge-$F$-saturated if it does not contain a Berge-$F$, but adding any hyperedge creates a copy of Berge-$F$. The $k$-uniform saturation number of Berge-$F$, ${\mathrm{sat}}_k(n,\text{Berge-}F)$ is the fewest number of edges in a Berge-$F$-saturated $k$-uniform hypergraph on $n$ vertices. We show that ${\mathrm{sat}}_k(n,\text{Berge-}F)=O(n)$ for all graphs $F$ and uniformities $3\le k\le 5$, partially answering a conjecture of English, Gordon, Graber, Methuku, and Sullivan. We also extend this conjecture to Berge copies of hypergraphs.