The ordered-forest core conjecture for polynomial testability

From papers

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.

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 and Asaf Shapira, “Polynomial Property Testing”, arXiv:2508.16878 (2025).

Solutions 0

No solutions have been posted yet.