← All problems

English–Gordon–Graber–Methuku–Sullivan Berge saturation conjecture

For every integer k≥2k\ge 2 and every finite family F\mathcal{F} of finite simple graphs, each having at least one edge, there exists a constant C=C(k,F)C=C(k,\mathcal{F}) such that, for all sufficiently large nn, sat⁡k(n,Berge⁡-F)≤Cn\operatorname{sat}_k(n,\operatorname{Berge}\text{-}\mathcal{F})\le Cn. Here sat⁡k(n,Berge⁡-F)\operatorname{sat}_k(n,\operatorname{Berge}\text{-}\mathcal{F}) is the minimum number of hyperedges in a kk-uniform hypergraph on nn vertices that contains no Berge copy of any graph in F\mathcal{F}, but such that adding any missing kk-vertex hyperedge creates a Berge copy of some graph in F\mathcal{F}; a Berge copy is an injective assignment of the edges of the graph to hyperedges containing their corresponding vertex pairs.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 3≤k≤53 \le k \le 5; a new preprint claims the individual-forbidden-graph case in all uniformities.

Known results

  • sat⁡k(n,Berge⁡-F)=O(n)\operatorname{sat}_k(n,\operatorname{Berge}\text{-}F)=O(n) for every fixed graph FF and 3≤k≤53 \le k \le 5 (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 sat⁡k(n,Berge⁡-F)=OF,k(n)\operatorname{sat}_k(n,\operatorname{Berge}\text{-}F)=O_{F,k}(n) for every fixed finite simple graph FF. 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.

Sources

Solutions 0

No solutions have been posted yet.