On saturation of Berge hypergraphs

Dániel Gerbner; Balázs Patkós; Zsolt Tuza; Máté Vizer

paper

On saturation of Berge hypergraphs

arXiv:2103.08437

Abstract

A hypergraph $H = (V (H), E (H))$ is a Berge copy of a graph $F$ , if $V (F) \subset V (H)$ and there is a bijection $f : E (F) \to E (H)$ such that for any $e \in E (F)$ we have $e \subset f (e)$ . A hypergraph is Berge- $F$ -free if it does not contain any Berge copies of $F$ . We address the saturation problem concerning Berge- $F$ -free hypergraphs, i.e., what is the minimum number $s a t_{r} (n, F)$ of hyperedges in an $r$ -uniform Berge- $F$ -free hypergraph $H$ with the property that adding any new hyperedge to $H$ creates a Berge copy of $F$ . We prove that $s a t_{r} (n, F)$ grows linearly in $n$ if $F$ is either complete multipartite or it possesses the following property: if $d_{1} \leq d_{2} \leq \dots \leq d_{∣ V (F) ∣}$ is the degree sequence of $F$ , then $F$ contains two adjacent vertices $u, v$ with $d_{F} (u) = d_{1}$ , $d_{F} (v) = d_{2}$ . In particular, the Berge-saturation number of regular graphs grows linearly in $n$ .

9 pages