Moshkovitz–Shapira's lower-bound conjecture for bipartite saturation

About 12 years old · traced to

Let 1≤s≤t1\le s\le t be integers. A bipartite graph is Ks,tK_{s,t}-saturated if it contains no copy of Ks,tK_{s,t}, but adding any missing edge between its color classes creates a copy of Ks,tK_{s,t}. Moshkovitz–Shapira's conjecture. There is an n0n_0 such that, whenever n≥n0n\ge n_0, every Ks,tK_{s,t}-saturated nn-by-nn bipartite graph GG contains at least

(s+t−2)n−⌊(s+t−22)2⌋(s+t-2)n-\left\lfloor\left(\frac{s+t-2}{2}\right)^2\right\rfloor

edges. This is the proposed additive-constant comparison with the ordered saturation number; the paper notes that the bound is tight by construction. The claim remains open in general, with the first open case being s=2s=2 and t=3t=3.

References

Primary source

Wenying Gan, Dániel Korándi and Benny Sudakov, “K_s,t-saturated bipartite graphs”, arXiv:1402.2471 (2014).

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.