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

Let 1st1\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 nn0n\ge n_0, every Ks,tK_{s,t}-saturated nn-by-nn bipartite graph GG contains at least

(s+t2)n(s+t22)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.

Sources & referencesView supporting material

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.