A polynomial removal lemma for posets

Kun, Gábor and Fekete, Panna Tímea (2023) A polynomial removal lemma for posets. In: Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications EuroComb 2023. Nakladatelství Masarykovy univerzity Munipress, Prága, pp. 695-701. ISBN 9788028003449

Preview

Text 1.9781611977912.45.pdf Download (572kB) | Preview

Abstract

We prove a removal lemma with polynomial bound for posets. Alon and Shapira proved that every class of undirected graphs closed under the removal of edges and vertices is strongly testable. However, their bounds on the queries are not very effective, since they heavily rely on Szemerédi's regularity lemma. The case of posets turns out to be simpler: 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 also give a simple classification: for every class of posets closed under the removal of edges and vertices there is an such that the class is indistinguishable from the class of posets without chains of length (by testing with a constant number of queries). The analogous results hold for comparability graphs.

Actions (login required)

Edit Item