Linear growth conjecture for Berge saturation numbers

At least 8 years old · documented by

Let kk be fixed, and let F\mathcal{F} be any fixed finite family of graphs. Write sat⁡k(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},

sat⁡k(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(nk−1)O(n^{k-1}). The conjecture proposes linear growth for the Berge-saturation setting, but the paper does not establish it in general.

References

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.