Saturation in three-uniform Berge hypergraphs: the five-star spectrum and the K4 saturation number
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≥7, every integer from ⌈4n/3⌉−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-K4-saturated hypergraph on n≥7 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≤ n≤95. 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 K4, 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.
Related
- Turán problems with bounded matching number in k-uniform hypergraphs
- Phase transition of random non-uniform hypergraphs
- Irregular Triads in 3-Uniform Hypergraphs
- Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
- On the growth of weak regular partitions in k-uniform hypergraphs
BibTeX
@misc{cao2026saturation,
title = {{Saturation in three-uniform Berge hypergraphs: the five-star spectrum and the $K_4$ saturation number}},
author = {XuanYu Cao and Yuan Lai and Chunxiang Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32353},
eprint = {2610.32353},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32353},
}
RIS
TY - UNPB
TI - Saturation in three-uniform Berge hypergraphs: the five-star spectrum and the K_4 saturation number
AU - XuanYu Cao
AU - Yuan Lai
AU - Chunxiang Wang
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.32353
UR - https://arxiv.org/abs/2610.32353
AB - 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≥7, every integer from ⌈4n/3⌉−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≥7 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≤ n≤95. 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.
ER -