A linear upper bound for Berge saturation numbers
In the authors' words
For a graph with at least one edge, a -uniform hypergraph is Berge--saturated if it contains no Berge-, but adding any missing hyperedge creates a Berge-. The saturation number is the minimum number of edges in such a hypergraph on vertices. English, Gordon, Graber, Methuku and Sullivan conjectured a linear upper bound for every fixed finite family of forbidden graphs. We prove the single-graph case: for every fixed integer and every fixed finite simple graph with at least one edge. The proof combines a sparse construction with degree and matching arguments.
Main resultLimitation the authors admit
Appeared: Friday, October 9. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 9 pages, 1 figures