Moshkovitz–Shapira's lower-bound conjecture for bipartite saturation
Moshkovitz–Shapira's lower-bound conjecture for bipartite saturation
Let be integers. A bipartite graph is -saturated if it contains no copy of , but adding any missing edge between its color classes creates a copy of . Moshkovitz–Shapira's conjecture. There is an such that, whenever , every -saturated -by- bipartite graph contains at least
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 and .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.