Linearity of saturation for Berge hypergraphs

English, S. and Gerbner, Dániel and Methuku, Abhishek and Tait, M. (2019) Linearity of saturation for Berge hypergraphs. EUROPEAN JOURNAL OF COMBINATORICS, 78. pp. 205-213. ISSN 0195-6698

Preview

Text 1807.06947.pdf Download (159kB) | Preview

Abstract

For a graph F, we say a hypergraph H is a Berge-F if it can be obtained from F by replacing each edge of F with a hyperedge containing it. We say a hypergraph is Berge-F-saturated if it does not contain a Berge-F, but adding any hyperedge creates a copy of a Berge- F. The k-uniform saturation number of Berge-F, sat k (n,Berge-F) is the fewest number of hyperedges in a Berge-F-saturated k-uniform hypergraph on n vertices. We show that sat k (n,Berge-F)=O(n) for all graphs F and uniformities 3≤k≤5, partially answering a conjecture of English, Gordon, Graber, Methuku, and Sullivan. We also extend this conjecture to Berge copies of hypergraphs. © 2019 Elsevier Ltd

Actions (login required)

Edit Item