Higher-uniformity Berge saturation conjecture

Let 3r<k3\leq r<k be integers and let F(r)F^{(r)} be an rr-uniform hypergraph. A kk-uniform hypergraph HH is Bergek-F(r)\text{Berge}_k\text{-}F^{(r)} if there is a bijection

ϕ:E(F(r))E(H)\phi:E(F^{(r)})\to E(H)

such that eϕ(e)e\subseteq\phi(e) for every eE(F(r))e\in E(F^{(r)}). Let satk(n,Berge-F(r))\operatorname{sat}_k(n,\text{Berge-}F^{(r)}) denote the minimum number of hyperedges in a kk-uniform hypergraph on nn vertices that is free of this configuration but becomes non-free after adding any kk-edge.

Higher-uniformity Berge saturation conjecture. For every 3r<k3\leq r<k and every rr-uniform hypergraph F(r)F^{(r)},

satk(n,Berge-F(r))=O(nr1).\operatorname{sat}_k(n,\text{Berge-}F^{(r)})=O(n^{r-1}).

This generalizes the earlier conjecture that Berge saturation numbers are linear when the forbidden object is a graph, corresponding to r=2r=2. The conjecture predicts the natural r1r-1 power growth for higher-uniformity forbidden hypergraphs; its general case remains open.

Sources & referencesView supporting material

Primary source

Sean English, Dániel Gerbner, Abhishek Methuku and Michael Tait, “Linearity of Saturation for Berge Hypergraphs”, arXiv:1807.06947 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.