Higher-uniformity Berge saturation conjecture

About 8 years old · traced to

Let 3≤r<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 e∈E(F(r))e\in E(F^{(r)}). Let sat⁡k(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 3≤r<k3\leq r<k and every rr-uniform hypergraph F(r)F^{(r)},

sat⁡k(n,Berge-F(r))=O(nr−1).\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 r−1r-1 power growth for higher-uniformity forbidden hypergraphs; its general case remains open.

References

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.