pipette
ESEspañol

A linear upper bound for Berge saturation numbers

Tianying Xie

Preprint

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