2018/07/18 by Sean English, Dániel Gerbner, English, Sean +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1807.06947
openalex publication_date 2018/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.