Posets are easily testable

Fekete, Panna Tímea and Kun, Gábor (2024) Posets are easily testable. EUROPEAN JOURNAL OF COMBINATORICS. ISSN 0195-6698 (In Press)

Preview	Text 2302.11390v2.pdf - Submitted Version Download (214kB) | Preview
Preview	Text EJC_Fekete_Kun.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (505kB) | Preview

Abstract

Alon and Shapira proved that every monotone class (closed under taking subgraphs) of undirected graphs is strongly testable, that is, under the promise that a given graph is either in the class or ε-far from it, there is a test using a constant number of samples (depending on ε only) that rejects every graph not in the class with probability at least one half, and always accepts a graph in the class. However, their bound on the number of samples is quite large, since they heavily rely on Szemerédi’s regularity lemma. We study the case of posets and show that every monotone class of posets is easily testable, that is, a polynomial number of samples is sufficient. We achieve this via proving a polynomial removal lemma for posets. We give a simple classification: for every monotone class of posets there is an h such that the class is indistinguishable (every large enough poset in one class is ε-close to a poset in the other class) from the class of posets free of the chain Ch. This allows to test every monotone class of posets using O(ε−1) samples. The test has two-sided error, but it is almost complete: the probability to refute a poset in the class is polynomially small in the size of the poset. The analogous results hold for comparability graphs, too.

Actions (login required)

Edit Item