Forest sufficient condition for polynomial approximation homomorphism complexity

From papers

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

TFandHT,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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.