A linear upper bound for Berge saturation numbers
En palabras de los autores
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.
Resultado principalLimitación que admiten los autores
Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 9 pages, 1 figures