Forest sufficient condition for polynomial approximation homomorphism complexity
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.
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
Sign in to submit a solution.
No solutions have been posted yet.