Easy testability for posets

Panna Tímea Fekete, Gábor Kun

Published 2023-02-22Version 1

Alon and Shapira proved that every class of undirected graphs closed under the removal of edges and vertices is strongly testable. We show that every class of posets closed under the removal of edges is easily testable, that is, strongly testable with a polynomial bound on the queries. We get this result via a removal lemma with polynomial bound. We also give a simple classification: for every class of posets closed under the removal of edges and vertices there is an $h$ such that the class is indistinguishable from the class of posets without chains of length $h$ (by testing with a constant number of queries). The analogous results hold for comparability graphs.