← All problems

Gishboliner–Jin–Sudakov edge-mapping conjecture

There is an absolute constant C>0C>0 such that, for every graph GG with nn vertices and mm edges, g0(G)≤C(n+mn)g_0(G)\le C\left(n+\frac{m}{\sqrt n}\right), where g0(G)g_0(G) is the least integer NN such that every mapping f:E(KN)→E(KN)f:E(K_N)\to E(K_N) satisfying f(e)∩e=∅f(e)\cap e=\varnothing for every e∈E(KN)e\in E(K_N) admits a copy G∗G^* of GG in KNK_N such that f(e)∉E(G∗)f(e)\notin E(G^*) for every e∈E(G∗)e\in E(G^*).

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

A new unrefereed preprint claims the conjecture is false and identifies a different sharp growth rate, but the result has not been independently checked.

The conjecture predicts an extremal bound of order O(n+m/n)O(n+m/\sqrt{n}) for the edge-mapping problem. Its proposed replacement is a larger order, n+m3/4n+m^{3/4}, across the claimed general parameter range.

November 2026 claimed refutation

Zhanping Yang's preprint Sharp Bounds for Edge Mappings of Graphs claims to disprove the O(n+m/n)O(n+m/\sqrt{n}) estimate and establish matching upper and lower bounds of order n+m3/4n+m^{3/4}. The claim changes both the conjecture's truth value and the predicted extremal scale, but is supported only by the unrefereed preprint.

Current status (as of November 2026): The conjectured estimate is claimed false and the order n+m3/4n+m^{3/4} is claimed sharp, but these conclusions remain unverified.

Sources

Solutions 0

No solutions have been posted yet.