The ordered-forest core conjecture for polynomial testability

About 1 year old · traced to

Let FF be an ordered graph, meaning a graph equipped with a linear order on its vertices. An ordered forest is an ordered graph whose underlying graph is a forest, and the core of FF is its smallest retract under order-preserving graph homomorphisms. Let qF-free(ε)q_{F\text{-free}}(\varepsilon) denote the query complexity of testing FF-freeness. Ordered-forest core conjecture.

qF-free(ε)=poly⁡(1/ε)if and only if the core of F is an ordered forest.q_{F\text{-free}}(\varepsilon)=\operatorname{poly}(1/\varepsilon)\quad\text{if and only if the core of }F\text{ is an ordered forest}.

The conjecture was posed by the first author and Tomon. It seeks a characterization of polynomial testability for ordered graph properties; the source states that it remains open.

References

Primary source

Lior Gishboliner and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).

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.