Forest sufficient condition for polynomial approximation homomorphism complexity
Let and be graphs. Let an -forest be the forest construction used in the source, and let denote its associated graph. Forest sufficient-condition conjecture. If there exists an -forest such that
then
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
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.