A polynomial removal lemma for posets

EUROCOMB’23

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 $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.

Pages:
695–701
References

Alon, Noga and Fischer, Eldar and Krivelevich, Michael and Szegedy, Mario (2000). Efficient testing of large graphs. Combinatorica, 20(4), 451-476.
https://doi.org/10.1007/s004930070001

Alon, Noga and Shapira, Asaf (2003). Testing subgraphs in directed graphs. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (pp. 700-709).
https://doi.org/10.1145/780542.780644

Alon, Noga and Shapira, Asaf (2005). Every monotone graph property is testable. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (pp. 128-137).
https://doi.org/10.1145/1060590.1060611

Alon, Noga and Shapira, Asaf (2006). A characterization of easily testable induced subgraphs. Combinatorics, Probability and Computing, 15(6), 791-805.
https://doi.org/10.1017/S0963548306007759

Alon, Noga and Fox, Jacob (2011). Testing perfection is hard. arXiv preprint arXiv:1110.2828.

Alon, Noga and Fox, Jacob (2015). Easily testable graph properties. Combinatorics, Probability and Computing, 24(4), 646-657.
https://doi.org/10.1017/S0963548314000765

Austin, Tim and Tao, Terence (2010). Testability and repair of hereditary hypergraph properties. Random Structures & Algorithms, 36(4), 373-463.
https://doi.org/10.1002/rsa.20300

Behrend, Felix A (1946). On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences, 32(12), 331-332.
https://doi.org/10.1073/pnas.32.12.331

Fox, Jacob (2011). A new proof of the graph removal lemma. Annals of Mathematics, 561-579.
https://doi.org/10.4007/annals.2011.174.1.17

Fox, Jacob and Wei, Fan (2018). Fast property testing and metrics for permutations. Combinatorics, Probability and Computing, 27(4), 539-579.
https://doi.org/10.1017/S096354831800024X

Gishboliner, Lior and Tomon, István (2021). Polynomial removal lemmas for ordered graphs. arXiv preprint arXiv:2110.03577.
https://doi.org/10.5070/C62359151

Goldreich, Oded and Goldwasser, Shari and Ron, Dana (1998). Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4), 653-750.
https://doi.org/10.1145/285055.285060

Green, Ben (2005). A Szemerédi-type regularity lemma in abelian groups, with applications. Geometric & Functional Analysis GAFA, 15(2), 340-376.
https://doi.org/10.1007/s00039-005-0509-8

Hladký, Jan and Máthé, András and Patel, Viresh and Pikhurko, Oleg (2015). Poset limits can be totally ordered. Transactions of the American Mathematical Society, 367(6),4319--4337.
https://doi.org/10.1090/S0002-9947-2015-06299-0

Klimošová, Tereza and Král', Daniel (2014, January). Hereditary properties of permutations are strongly testable. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1164-1173). Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611973402.86

Král', Daniel and Serra, Oriol and Vena, Lluís. (2012). A removal lemma for systems of linear equations over finite fields. Israel Journal of Mathematics, 187, 193-207.
https://doi.org/10.1007/s11856-011-0080-y

Lovász, László and Szegedy, Balázs (2008). Testing properties of graphs and functions. arXiv preprint arXiv:0803.1248.

Rödl, Vojtěch. and Schacht, Mathias (2009). Generalizations of the removal lemma. Combinatorica, 29(4), 467-501.
https://doi.org/10.1007/s00493-009-2320-x

Roth, Klaus F (1953). On certain sets of integers. J. London Math. Soc, 28(1), 104-109.
https://doi.org/10.1112/jlms/s1-28.1.104

Rubinfeld, Ronitt and Sudan, Madhu (1996). Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25(2), 252-271.
https://doi.org/10.1137/S0097539793255151

Ruzsa, Imre Z and Szemerédi, Endre (1978). Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18(939-945), 2.

Metrics

0

Views

0

PDF views