Forest sufficient condition for polynomial approximation homomorphism complexity

About 1 year old · traced to

Let FF and HH be graphs. Let an FF-forest TT be the forest construction used in the source, and let T⋆T^{\star} denote its associated graph. Forest sufficient-condition conjecture. If there exists an FF-forest TT such that

T→FandH→T⋆,T\rightarrow F\qquad\text{and}\qquad H\rightarrow T^{\star},

then

MF,H(ε)=poly⁡(1/ε).M_{F,H}(\varepsilon)=\operatorname{poly}(1/\varepsilon).

This is presented immediately after the conjectural characterisation of polynomial versus exponential behaviour and is intended as the polynomial side of that dichotomy. The supplied text does not establish this statement as a theorem, and the conjecture remains open.

References

Primary source

Lior Gishboliner, Eoin Hurley and Yuval Wigderson, “Asymmetric results about graph homomorphisms”, arXiv:2502.20278 (2026).

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.