Linearity of Saturation for Berge Hypergraphs

English, Sean and Gerbner, Dániel and Methuku, Abhishek and Tait, Michael (2019) Linearity of Saturation for Berge Hypergraphs. European Journal of Combinatorics, 78. pp. 205-213.

Preview

Text 1807.06947.pdf Download (160kB) | Preview

Abstract

For a graph F, we say a hypergraph H is Berge-F if it can be obtained from F be 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 Berge-F. The k-uniform saturation number of Berge-F, satk(n, Berge-F) is the fewest number of edges in a Berge-F-saturated k-uniform hypergraph on n vertices. We show that satk(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

Actions (login required)

Edit Item