Linear growth conjecture for Berge saturation numbers

Let kk be fixed, and let F\mathcal{F} be any fixed finite family of graphs. Write satk(n,Berge-F)\operatorname{sat}_k(n,\text{Berge-}\mathcal{F}) for the minimum number of edges in a kk-uniform hypergraph on nn vertices that is Berge-F\mathcal{F}-saturated. Linear growth conjecture for Berge saturation numbers. For any fixed finite family of graphs F\mathcal{F},

satk(n,Berge-F)=O(n).\operatorname{sat}_k(n,\text{Berge-}\mathcal{F})=O(n).

Classical graph saturation numbers are known to be linear in nn, whereas general kk-uniform hypergraph saturation has the upper bound O(nk1)O(n^{k-1}). The conjecture proposes linear growth for the Berge-saturation setting, but the paper does not establish it in general.

Sources & referencesView supporting material

Primary source

Sean English, Nathan Graber, Pamela Kirkpatrick, Abhishek Methuku and Eric C. Sullivan, “Saturation of Berge Hypergraphs”, arXiv:1710.03735 (2017).

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.