pipette
ENEnglish

A linear upper bound for Berge saturation numbers

Tianying Xie

Preprint

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