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

Valid HTML 4.1