A Note on the Testability of Ramsey's Class
Authors: Charles Jordan1 and Thomas Zeugmann2
Source: Theory and Applications of Models of Computation,
7th Annual Conference, TAMC 2010,
Prague, Czech Republic, June 7-11, 2010,
Proceedings,
(Jan Kratochvíl, Angsheng Li,
Jiří Fiala, and Petr Kolman, Eds.),
Lecture Notes in Computer Science 6108, pp. 296-307, Springer 2010.
Abstract. In property testing, the goal is to distinguish between objects that satisfy some desirable property and objects that are far from satisfying it, after examining only a small, random sample of the object in question. Although much of the literature has focused on properties of graphs, very recently several strong results on hypergraphs have appeared. We revisit a logical result obtained by Alon et al. [1] in the light of these recent results. The main result is the testability of all properties (of relational structures) expressible in sentences of Ramsey's class.
1 Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
2 Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas under Grant No. 21013001.
©Copyright 2010, Springer
