Linearity of saturation for Berge hypergraphs
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. (C) 2019 Elsevier Ltd. All rights reserved.
WOS:000465187100014
2019-05-01
78
205
213
REVIEWED