Saturation in three-uniform Berge hypergraphs: the five-star spectrum and the $K_4$ saturation number

Source abstract

For a graph $G$, a hypergraph is Berge-$G$-saturated if it contains no Berge copy of $G$, but adding any missing hyperedge creates one. We determine the complete saturation spectrum of three-uniform Berge five-stars for every order. For $n\ge7$, every integer from $\lceil4n/3\rceil-3$ to $2n-5$ occurs; the additional values depend only on $n$ modulo five. The structural ingredient is a sharp bound on the remainder after deleting all complete five-vertex components: for an $n$-vertex, $m$-edge Berge-five-star-saturated hypergraph, this remainder has at most $15(2n-m)/7$ vertices. We characterize all equality cases. We also prove that every three-uniform Berge-$K_4$-saturated hypergraph on $n\ge7$ vertices has at least $n$ edges. Together with known constructions, this determines its saturation number for every order and settles the conjecture of Chen, He, and Xie; the new lower bound covers the previously unresolved orders $9\le n\le95$. Both arguments use the distinct representatives forced by saturation to obtain local incidence constraints. For five-stars these constraints bound the size of the remainder and characterize equality. For $K_4$, they reduce a putative counterexample to a configuration on at most eight vertices; incidence estimates and a sharp bound on the vertices covered by short cycles in a bipartite graph exclude all remaining cases.