A polynomial removal lemma for posets
EUROCOMB’23
695–701
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.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Gabor Kun, Panna Timea Fekete