Saturation numbers for $3$-uniform Berge-$K_4$

Abstract

The saturation number ${\text{sat}}_r(n,\mathcal{F})$ is the minimum number of hyperedges in an $r$-uniform $\mathcal{F}$-saturated hypergraph on $n$ vertices. We determine this parameter for $3$-uniform Berge-$K_4$ hypergraphs, proving that ${\text{sat}}_3(n,\text{Berge-}{K}_4)=n$ for $n=5,7,8$ and $n\ge 96$, while ${\text{sat}}_3(6,\text{Berge-}{K}_4)=5$. This resolves a problem posed by English, Kritschgau, Nahvi, and Sprangel~\cite{EKNS2024} for large $n.$ Using a computer search, we classify all extremal hypergraphs for $5\le n\le 8.$ For $n\ge 96$, we further show the existence of many non-isomorphic extremal families. Our approach synthesizes structural insights with computational power.

22 pages, 2 figures