The strong saturation conjecture for bipartite graphs

Let Sn(p,q)S_n(p,q) be the minimum number of edges in an n×nn\times n bipartite graph such that adding any new edge between its two classes creates a copy of Kp,qK_{p,q}. Let Sn(p,q)\overrightarrow{S}_{n}(p,q) denote the directed analogue, where the copies of Kp,qK_{p,q} have their pp vertices in the first class and their qq vertices in the second class. Strong saturation conjecture. For every p,qp,q there is an integer n0n_0 such that for every nn0n\ge n_0,

Sn(p,q)=Sn(p,q)(qp)24.S_n(p,q)=\overrightarrow{S}_{n}(p,q)-\left\lfloor\frac{(q-p)^2}{4}\right\rfloor.

The directed quantity is known to equal (p+q2)n(p1)(q1)(p+q-2)n-(p-1)(q-1), while the displayed construction gives the stated upper bound for the undirected quantity. The conjecture asserts that this bound is best possible for sufficiently large nn, so the gain from allowing undirected copies is an additive constant.

Sources & referencesView supporting material

Primary source

Guy Moshkovitz and Asaf Shapira, “Exact Bounds for Some Hypergraph Saturation Problems”, arXiv:1209.3598 (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.