Erd{o}s and S\'os initiated the study of the maximum size of a k-uniform set system, for k ≥ 4, with no singleton intersections $50$ years ago. In this work, we investigate the dual problem: finding the minimum size of a k-uniform hypergraph with no singleton intersections, such that adding any missing hyperedge forces a singleton intersection. These problems, known as saturation and semi-saturation, are typically challenging. Our focus is on an elementary-to-state case in the line of work by Erd{o}s, F\"uredi and Tuza. We establish tight linear bounds for $k=4$, marking one of the first non-obvious cases with such a bound.
No takes yet. Share an insight, caveat, or question.
Cambie et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: