English–Gordon–Graber–Methuku–Sullivan Berge saturation conjecture
For every integer and every finite family of finite simple graphs, each having at least one edge, there exists a constant such that, for all sufficiently large , . Here is the minimum number of hyperedges in a -uniform hypergraph on vertices that contains no Berge copy of any graph in , but such that adding any missing -vertex hyperedge creates a Berge copy of some graph in ; a Berge copy is an injective assignment of the edges of the graph to hyperedges containing their corresponding vertex pairs.
References
- A linear upper bound for Berge saturation numbers — arXiv — Tianying Xie
Source: arXiv
Progress summary
A new preprint claims the conjectured linear bound for each individual forbidden graph, but the broader finite-family version remains open.
The Berge saturation conjecture of English, Gordon, Graber, Methuku, and Sullivan asserts linear growth in the number of vertices for every fixed forbidden graph and uniformity. A 2018 paper established only the uniformities ; a new preprint claims the individual-forbidden-graph case in all uniformities.
Known results
- for every fixed graph and (English, Gerbner, Methuku, and Tait, 2018).
- Further linear cases include complete multipartite graphs, regular graphs, and graphs with adjacent vertices of the two smallest degrees (Gerbner, Patkós, Tuza, and Vizer, 2021).
October 2026 claimed generalization
Tianying Xie's preprint A linear upper bound for Berge saturation numbers, reported on October 8, claims for every fixed finite simple graph . This settles the individual-forbidden-graph case if correct, but the preprint is unrefereed and does not cover the finite-family formulation.
Current status (as of October 2026): The individual-forbidden-graph case is claimed solved by an unverified preprint, while the finite-family formulation remains open.
Solutions 0
No solutions have been posted yet.