A Note on the Testability of Ramsey’s ClassCharles Jordan? and Thomas Zeugmann??
Division of Computer Science
Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan{skip,thomas}@ist.hokudai.ac.jp

Abstract. In property testing, the goal is to distinguish between objects that satisfy some desirable property and objects that are far fromsatisfying it, after examining only a small, random sample of the object
in question. Although much of the literature has focused on propertiesof graphs, very recently several strong results on hypergraphs have appeared. We revisit a logical result obtained by Alon et al. [1] in the lightof these recent results. The main result is the testability of all properties(of relational structures) expressible in sentences of Ramsey’s class.
Key words: property testing, logic, Ramsey’s class

1

Introduction

Alon et al. [1] proved the testability of all graph properties expressible in sentences of first-order logic where all quantifier alternations are of the type ‘∃∀’.
This class is the restriction of Ramsey’s [12] class to undirected graphs. Fischer [7] extended this (and other results of [1]) to tournaments. However, Ramsey’s [12] class is traditionally not restricted to undirected graphs; any (finite)
number of predicate symbols with any (finite) arities may appear. It is therefore
natural to ask whether one can extend this result to relational structures.
This result of Alon et al. [1] has been influential, and has already been extended several times, cf., e.g., [2, 8, 13]. These extensions have generally focusedon an intermediate result: the testability of colorability (and eventually hereditary1 ) properties. In particular, Austin and Tao [4] have recently obtained astrong result: the testability (with one-sided error) of hereditary properties of
directed, colored, not necessarily uniform hypergraphs. We return to the logicalclassification begun by Alon et al. [1] and show that this result and generalizations of the remaining parts of the proof in Alon et al. [1] combine to give ourdesired result, the testability of all properties expressible in Ramsey’s class.

2

Preliminaries

Instead of restricting our attention to graphs, we focus on properties of relational
structures. We begin by defining vocabularies of such structures.
?

Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
Supported by MEXT Grant-in-Aid for Scientific Research on Priority Areas underGrant No. 21013001.
1
A hereditary property is one that is closed under the taking of induced substructures.

??

2

C. Jordan and T. Zeugmann

Definition 1. A vocabulary τ is a tuple of distinct predicate symbols Riai withassociated arities ai , i.e., τ := (R1a1 , . . . , Rsas ) .
The vocabulary (unique up to renaming) of directed graphs is τG := (E 2 ).
Definition 2. A structure A with vocabulary τ is an (s + 1)-tuple,A
A := (U, RA
1 , . . . , Rs ) ,where U is a finite universe, and RA
i is an ai -ary predicate corresponding to theaisymbol Riai of τ , i.e., RA⊆U.
i
The natural numbers are denoted by N := {0, 1, . . .}. For any set U we write|U | to denote the cardinality of U and we generally identify U with the set{0, . . . , |U | − 1}. The size of A is denoted by #(A) and defined as #(A) := |U |.
Let STRUC n (τS) be the set of structures with vocabulary τ and size n, and
STRUC (τ ) := n∈N STRUC n (τ ) be the finite structures with vocabulary τ .
A property P with vocabulary τ is any subset of STRUC (τ ). We say thata structure A has P if A ∈ P . In property testing, we are interested in distinguishing between structures that have some property and those that are far fromhaving the property, and so we require a distance measure. Jordan and Zeugmann [9] introduced several possible distances and considered the relationshipbetween the resulting notions of testability. We are proving a positive result, andso it suffices to use only the most restricted variant considered there.
We begin by noting that relations have subrelations, for example monadic
loops in a binary predicate. In property testing, it can be useful and is more
restrictive (see Jordan and Zeugmann [9]) to consider these subrelations as separate relations when defining the distance between structures. We first define
the syntactic notion of subtype before proceeding to subrelations.
Definition 3. A subtype S of a predicate symbol Riai is any partition of the set{1, . . . , ai }.
For example, graphs have a single, binary predicate symbol E 2 which has
two subtypes: {{1, 2}} and {{1}, {2}}, corresponding to loops and non-loops
respectively. Let SUB(Riai ) denote the set of subtypes of predicate symbol Riai .
Definition 4. Let A ∈ STRUC (τ ) be a structure with vocabulary τ and universe U , and let S be a subtype of predicate symbol Riai ∈ τ . We define sU (S),the tuples that belong to S, as the set (x1 , . . . , xai ) ∈ U ai satisfying the following condition. For every 1 ≤ j, k ≤ ai , xj = xk iff j and k are containedin the same element of S. The subrelation sA (S) of A corresponding to S issA (S) := sU (S) ∩ RAi .
Returning to our example of graphs, the sets of loops and non-loops are thesubrelations of E corresponding to the subtypes {{1, 2}} and {{1}, {2}} of E 2 ,respectively. We denote the symmetric difference of sets U and V by U 4 V ,U 4 V := (U \V ) ∪ (V \U ) .

A Note on the Testability of Ramsey’s Class

3

Definition 5. Let A, B ∈ STRUC n (τ ) be structures with vocabulary τ andsize n. The distance between A and B is|sA (S) 4 sB (S)|.
n|S|
Ri i ∈τ S∈SUB(Ri i )mrdist(A, B) := max
a

max a

The distance between structures is the fraction of assignments that differ
in the most different subtype. The distance between structures generalizes to
distance from properties in the usual way.
Definition 6. Let A ∈ STRUC n (τ ) be a structure with vocabulary τ and size n,
and let P ⊆ STRUC (τ ) be a property with vocabulary τ . The distance between A
and P ismrdist(A, P ) :=min n mrdist(A, B) .
B∈P ∩STRUC (τ )n

If P ∩ STRUC (τ ) is empty, we let the distance be infinite.
We are now able to define property testing itself.
Definition 7. Let P ⊆ STRUC (τ ) be a property with vocabulary τ . An (ε, q)tester T for P is a probabilistic algorithm which satisfies the following conditions,when given ε and access to an oracle that answers queries for the universe size#(A) and for the assignment of any tuple (x1 , . . . , xai ) ∈ RAi :1. If A ∈ P , then T accepts with probability at least 2/3.
2. If mrdist(A, P ) ≥ ε, then T rejects with probability at least 2/3.
3. T makes at most q queries.
In property testing, we are particularly interested in properties that can betested with a number of queries depending only on ε.
Definition 8. A property P is testable if there exists a function c(ε) such thatfor every ε > 0, there exists an (ε, c(ε))-tester for P .
This is a non-uniform definition because we do not require the testers to be,e.g., computable given ε. There exist properties that are non-uniformly testable
but not uniformly testable (see, e.g., Alon and Shapira [3]). Our results hold in either case2 (i.e., one can replace all occurrences of “testable” below by “uniformly
testable” and maintain correctness) and so we will not distinguish between them.
We also require logical definitions. These definitions are standard and wereview them quickly. See Enderton [6] for an introduction to logic and Börger et
al. [5] for background on classification problems.
The first-order language of τ is the closure of the atomic formulae xi = xj andRiai (x1 , . . . , xai ) for variable symbols xk under Boolean connectives ∧, ∨ and ¬and first-order quantifiers ∀ and ∃. We do not allow ordering or arithmetic. These
sentences are interpreted in the usual way and so, for a structure A ∈ STRUC (τ )2

In the uniform case, we must restrict Lemma 1 to decidable properties. All properties
considered here are clearly decidable.

4

C. Jordan and T. Zeugmann

and sentence ϕ of vocabulary τ , we can decide whether A |= ϕ. Logical sentences
define properties; if ϕ is a sentence with vocabulary τ , then it defines property
Pϕ := {A | A ∈ STRUC (τ ), A |= ϕ}.
Our logic does not contain arithmetic or ordering, and so all properties expressible in it are closed under isomorphisms. We formalize this as follows.
Definition 9. Let A, B ∈ STRUC n (τ ) be two structures with universe U andvocabulary τ . We say that A and B are isomorphic if there exists a bijection
f : U → U such that for all 1 ≤ i ≤ s and x1 , . . . , xai ∈ U , we haveB
(x1 , . . . , xai ) ∈ RAi ⇐⇒ (f (x1 ), . . . , f (xai )) ∈ Ri .

Definition 10. Let P be a property with vocabulary τ . We say that P is closed
under isomorphisms if for all isomorphic A, B, A has P iff B has P .
Our goal is a classification of the syntactic subclasses of first-order logic
according to their testability. These subclasses are traditionally formulated asprefix-vocabulary fragments. Here we are only interested in Ramsey’s class, andso we omit more general definitions, see, e.g., Börger et al. [5] for details.
Ramsey’s class is denoted [∃∗ ∀∗ , all]= . This is the set of sentences of firstorder predicate logic in prenex normal form, where all existential quantifiers
precede all universal quantifiers. Function symbols do not appear, but any number of predicate symbols of any arity may appear, as may the special atomic
predicate =. Ramsey’s class has a number of nice algorithmic properties. For example, Ramsey [12] showed the satisfiability problem for this class is decidable,
and Lewis [11] showed it to be NEXPTIME-complete. Kolaitis and Vardi [10]proved a 0-1 law holds for existential second -order sentences, if the first-orderpart is in Ramsey’s class. The class that Alon et al. [1] proved testable is essentially the restriction of Ramsey’s class to graphs, denoted [∃∗ ∀∗ , (0, 1)]= .

3

Testability of Ramsey’s ClassWe show that all properties expressible in [∃∗ ∀∗ , all]= are testable. The proof follows that of Alon et al. [1]. First, we show that their notion of indistinguishability
preserves testability after generalizing to relational structures. Then, we provethat all sentences in our class define properties that are indistinguishable frominstances of a generalized colorability problem. Finally, we show that all suchproblems are hereditary and therefore testable in the setting defined by Austin
and Tao [4]. This implies testability under our definitions, giving the following.
Theorem 1. All sentences in [∃∗ ∀∗ , all]= are testable.
Alon et al. [1] introduced the concept of indistinguishability and showed thatit preserves testability of graph properties. We begin by extending their notion
to relational properties.

A Note on the Testability of Ramsey’s Class

5

Definition 11. Let P1 , P2 ⊆ STRUC (τ ) be properties with vocabulary τ that areclosed under isomorphisms. We say that P1 and P2 are indistinguishable if forevery ε > 0 there exists an N := N (ε) ∈ N such that the following holds for alln > N . For every A ∈ STRUC n (τ ), if A has property P1 , then mrdist(A, P2 ) < ε
and if A has P2 , then mrdist(A, P1 ) < ε.
The importance of indistinguishability is that it preserves testability.
Lemma 1. Let P1 , P2 ⊆ STRUC (τ ) be indistinguishable properties with vocabulary τ . Property P1 is testable iff P2 is testable.
The proof of Lemma 1 is a simple extension of the proof by Alon et al. [1]and is omitted due to space constraints. Next, we will show that all sentencesin [∃∗ ∀∗ , all]= define properties that are indistinguishable from instances of ageneralized colorability problem. We begin by defining the colorability problem.
For any fixed set F of structures with vocabulary τ , some positive numberof colors c, and functions that assign a color between 1 and c to each element ofeach structure in F , we define the F -colorability problem as follows. A structure
A ∈ STRUC (τ ) is F -colorable if there exists some (not necessarily proper) ccoloring of A such that A does not contain any induced substructures isomorphic
to a member of F . We let PF be the set of structures that are F -colorable.
For example, we can consider the case of graphs and let F contain c copiesof K2 . We enumerate these copies in some fashion from 1 to c, and for copy i,color both vertices with i. The resulting problem is of course the usual (k- or
equivalently) c-colorability. The following is a straightforward generalization of
the proof by Alon et al. [1].
Lemma 2. Let ϕ be any first-order sentence in the class [∃∗ ∀∗ , all]= . Thereexists an instance of the F -colorability problem that is indistinguishable from Pϕ ,the property defined by ϕ.
Proof. Let ε > 0 be arbitrary and ϕ := ∃x1 . . . ∃xt ∀y1 . . . ∀yu : ψ be any firstorder formula with quantifier-free ψ and vocabulary τ . We note, as did Alon etal. [1], that we can restrict our attention to formulas ψ where it is sufficient toconsider only cases where the variables are bound to distinct elements. This isbecause, given any ψ 0 , we can construct a ψ satisfying this restriction that isequivalent on structures with at least t + u elements, and the smaller structures
do not matter in the context of indistinguishability.
Let P = {A | A ∈ STRUC (τ ), A |= ϕ} be the property defined by ϕ. We
now define an instance of F -colorability that we will show to be indistinguishable
from P . We denote our c colors by the elements of{(0, 0)} ∪ {(a, b) | 1 ≤ a ≤ π1 , 1 ≤ b ≤ π2 , a, b ∈ N} .
Here, π1 is the numberof distinct structures of vocabulary τ with exactly tPaielements, π1 := 2 1≤i≤s t . Similarly, we denote by π2 the number of ways it ispossible to “connect” or “add” a single
element
to some existing, fixed t-elementPP
ai ai −jstructure of vocabulary τ , i.e., π2 := 2 1≤i≤s 1≤j≤ai −1 ( j )t
. We will use fixed6

C. Jordan and T. Zeugmann

enumerations of these π1 structures with t elements and π2 ways of connecting
an additional element to a fixed t element structure.
We impose on the coloring of the structure the following restrictions. Eachcan be expressed by prohibiting finite sets of colored induced substructures.
(1) The color (0, 0) may be used at most t times. Therefore, we prohibit all(t + 1)-element structures that are colored completely with (0, 0).
(2) The graph must be colored using only {(0, 0)} ∪ {(a, b) | 1 ≤ b ≤ π2 } forsome fixed a ∈ {1, . . . , π1 }. Therefore, we prohibit all two-element structurescolored ((a, b), (a0 , b0 )) with a 6= a0 .
(3) We now consider some fixed coloring of a u-element structure V , whose universe we identify with {v1 , . . . , vu }. We assume that this coloring satisfies
the previous restriction and that color (0, 0) does not appear. We must decide whether to prohibit this structure. In order to do so, we first take thefixed a guaranteed by the previous restriction, and consider the t-element
structure E, whose universe we identify with {e1 , . . . , et }, that is the ath
structure in our enumeration of t element structures. We connect each vi to
E in the following way. If vi is colored (a, b), we use the bth way of connecting an additional element to a t-element structure in our enumeration.
We denote the resulting (t + u)-element structure as M and allow (do notprohibit) M iff M is a model of ψ when we replace xi with ui and yj with vj .
We now show that the resulting F -colorability problem is indistinguishable
from P . Assume that we are given an A |= ϕ. Color the t vertices existentially bound to the xi with (0, 0). Then, we can color all remaining vertices vi
with (a, b), where a corresponds to the substructure induced by {x1 , . . . , xt } inour enumeration of t-element structures, and b corresponds to the connection
between vi and {x1 , . . . , xt }. It is easy to see that this coloring satisfies the restrictions of our F -colorability problem. We have not made any modifications tothe structure and so mrdist(A, PF ) = 0.
Next, we assume that we are given a structure with a coloring that satisfies
our restrictions. We will show that we can obtain a model of ϕ by making onlya small number of modifications. First, if there are less than t elements colored(0, 0), we arbitrarily choose additional elements to color (0, 0) so that there areexactly t such elements. We will denote these t elements with {e1 , . . . , et }. Restriction (2) guarantees that all colors which are not (0, 0) share the same firstcomponent. Let a be this shared component. We make the structure inducedthby {e1 , . . . , et } identical to thein our enumeration of t-element
Pa structure
structures, requiring at most 1≤i≤s tai = O(1) modifications. Next, for eachelement vi that is colored (a, b) with a, b 6= 0, we modify the connections between vi and {e1 , . . . , et } in order to make these connections identical to the bth
way of making such connections in our enumeration. This requires at mostX
X ai (n − t)tai −j = O(n)j1≤i≤r 1≤j≤ai −1

A Note on the Testability of Ramsey’s Class

7

additional modifications, all of which are to non-monadic subrelations. Binding xi to ei , the resulting structure is a model of ϕ. We made at most O(1)modifications to monadic subrelations and O(n) modifications to non-monadic
subrelations, and so mrdist(A, P ) ≤ max{O(1)/n, O(n)/Ω(n2 )} = o(1) < ε,where the inequality holds for sufficiently large n.
Therefore, all such properties P are indistinguishable from instances of F colorability.
tu
A hereditary property of relational structures is one which is closed undertaking induced substructures. F -colorability is clearly a hereditary property; if A
is F -colorable, then so are its induced substructures. However, the definitionsof Austin and Tao [4] are significantly different from ours and so we explicitly
reduce the following translation in our setting to their result.
Theorem 2 (Translation of Austin and Tao [4]). Let P be a hereditaryproperty of relational structures which is closed under isomorphisms. Then, property P is testable with one-sided error.
Before reducing Theorem 2 to its statement in [4], we first briefly introduce
their definitions. All of the definitions in Subsection 3.1 are from Austin and
Tao [4], although we omit definitions which are not necessary for our purposes.
3.1

Framework of Austin and Tao [4]We begin by introducing their analogue of vocabularies: finite palettes.
Definition 12. A finite palette K is a sequence K := (Kj )∞j=0 of finite sets, ofwhich all but finitely-many are singletons. The singletons are called points anddenoted pt. A point is called trailing if it occurs after all non-points.
We will write K = (K0 , . . . , Kk ), omitting trailing points and call k the orderof K. We use the elements of Kj to color the j-ary edges in hypergraphs.
Definition 13. A vertex set V is any set which is at most countable. If V, W
are vertex sets, then a morphism f from W to V is any injective map f : W → V
and the set of such morphisms is denoted Inj(W, V ). For N ∈ N, we denote theset {1, . . . , N } by [N ].
Of course, [N ] is a vertex set. Our structures are finite so we are mostly interested in finite vertex sets. Next, we define the analogue of relational structures.
Definition 14. Let V be a vertex set and K be a finite palette. A K-colored
hypergraph G on V is a sequence G := (G)∞j=0 , where each Gj : Inj([j], V ) → Kj
(V )is a function. Let K
be the set of K-colored hypergraphs on V .
Only finitely many of the Kj are not points, and so only finitely many Gj
are non-trivial. The Gj assign colors from Kj to the morphisms in Inj([j], V ).
In our relational setting, this set of morphisms corresponds to the set of j-ary
tuples (x1 , . . . , xj ) with pairwise distinct components.
Before defining hereditary K-properties, we need one last technical definition.

8

C. Jordan and T. Zeugmann

Definition 15. Let V, W be vertex sets and f ∈ Inj(W, V ) be a morphism from
W to V . The pullback map K (f ) : K (V ) → K (W ) is
K (f ) (G) (g) := Gj (f ◦ g) ,j(V ), j ≥ 0 and g ∈ Inj([j], W )). If W ⊆ V andfor all G = (Gj )∞j=0 ∈ Kf ∈ Inj(W, V ) is the identity map on W , we abbreviate

G W := K (f ) .
Abusing notation, the pullback map K (f ) maps K-colored hypergraphs on V
to those on W , by assigning the color of f ◦g to g, for all tuples g. Note that G W
is equivalent to the induced subhypergraph on W . For notational clarity, we
reserve P for properties of relational structures and use P to denote properties
of hypergraphs.
Definition 16. Let K = (Kj )∞j=0 be a finite palette. A hereditary K-property
P is an assignment P : V 7→ P (V ) of a collection P (V ) ⊆ K (V ) of K-colored
hypergraphs for every finite vertex set V such that
K (f ) (P (V ) ) ⊆ P (W )for every morphism f ∈ Inj(W, V ) between finite vertex sets.
Finally, we state the definition of (one-sided error) testability used by Austin
and Tao [4]. Here, for a vertex set V and c ∈ N, we write Vc := {V 0 | V 0 ⊆V, |V 0 | = c} to denote the set of subsets of V with exactly c elements.
Definition 17. Let K be a finite palette with order k ≥ 0 and P be a hereditary
K-property. Property P is testable with one-sided error if for every ε > 0, there
exists N ≥ 1 and δ > 0 satisfying the following. For all vertex sets V with
|V | ≥ N , if G ∈ K (V ) satisfies

 

1
V
(W )
, G W ∈ P≥ 1−δ,(1)
W |W ∈V
N
N

then there exists a G0 ∈ P (V ) satisfying

 

V
1
0
≤ ε.
, G W 6= G W
W |W ∈

V
k

(2)

k

To see that this is a variant of testability, it is easiest to consider the contrapositive. If there is a G0 satisfying (2), then G is not ε-far from P, using theimplicit distance measure based on the fraction of differing induced subhypergraphs of size k. If there is no such G0 (i.e., G is ε-far from P) and P is testable,
then (1) must not hold. That is, there are many induced subhypergraphs ofsize N that do not have P. The definition is for hereditary P, and so if G has P,
then so do all induced subhypergraphs. This allows the construction of testers.
Finally, we can state one of the main results of Austin and Tao [4].

A Note on the Testability of Ramsey’s Class

9Theorem 3 (Austin and Tao [4]). Let K be a finite palette and let P be ahereditary K-property. Then, P is testable with one-sided error.
In the following subsection we will map our vocabularies, structures andproperties to this setting. We will then show that hereditary properties in our
setting correspond to hereditary properties (in the sense of Definition 16) here,
and that testability in the sense of Definition 17 implies testability of the original
relational properties. That is, we explicitly reduce Theorem 2 to Theorem 3.
3.2

Reducing Theorem 2 to Theorem 3

We begin by mapping vocabulary τ = {R1a1 , . . . , Rsas } to a finite palette Kτ =(Ki )∞
i=0 . We use the color of a “tuple” to represent the set of assignmentson it. The difference between the set of j-ary tuples over a finite universe
U and Inj([j], U ) is that the latter does not permit repeated components. If
S ∈ SUB(Riai ) has |S| < ai , then the corresponding subrelation consists of tuples with repeated components. We treat such S as relations with arity |S| andno repeated components. Here, S(n, k) is the Stirling number of the second kind.
For a ≥ 1, let Pa := {Riai | Riai ∈ τ, ai = a} be the set of predicate
symbolshiPwith arity a. We now define palette K. Let K0 := pt and Ki := 2 j≥i |Pj |S(j,i) .
There are finitely-many predicate symbols and so only finitely-many Ki 6= pt.
Let Sa := {Sai | Sai ∈ SUB(Riai ), |Sai | = a, 1 ≤ i ≤ s} be the set of subtypes
with cardinality a for all a ≥ 1. Now, 2|Sa | = |Ka | and we have exactly enoughcolors to encode the set of assignments of the a-ary subtypes on a-ary tuples.
We will now define a map h from relational structures A on universe U to
hypergraphs GA ∈ K (U ) . For any Sai ∈ Sa , there is a bijectionr(Sai ) : sU (Sai ) → {(x1 , . . . , xa ) | xi ∈ U, xi 6= xj for i 6= j}from sU (Sai ) to the a-ary tuples without duplicate components, formed by removing the duplicate components. That is, r(Sai ) maps (x1 , . . . , xai ) to (xi1 , . . . , xia )where 1 ≤ i1 < i2 < . . . < ia ≤ ai . We can now define GA = h(A).
For j > 0, we define Gj : Inj([j], U ) → Kj as follows. Assign to f ∈ Inj([j], U )the color encoding the set of assignments of the subtypes Sj on (f (1), . . . , f (j)),
using the inverses (r(Sji ))−1 to get assignments for subtypes of high-arity relations. For j = 0, Inj([j], U ) = ∅ and K0 = pt and we can use a trivial map.
Of course, we extend the map to properties in the obvious way. If P is aproperty of relational structures, we let P (U ) := {h(A) | A ∈ P }. Formally, wedefine P(U ) := P (U ) , but there is a small technical point. We have identified
finite universes with subsets of the naturals, allowing us to call STRUC (τ ) a set.
However, Definition 13 allows a vertex set to be any finite set and Definition 16
requires hereditary hypergraph properties to be closed under bijections between
vertex sets. To remedy this, for each finite vertex set W , we fix a3 bijection
3

Our properties are closed under isomorphisms, so any fixed bijection is acceptable.

10

C. Jordan and T. Zeugmann

g W : W → {0, . . . , |W | − 1}. We then define P := h(P ) formally as(
P (W ) ,if W = {0, 1, . . . , |W | − 1};
P(W ) :=W
K (g ) P ({0,...,|W |−1}) , otherwise.
Hereditary relational properties are mapped to hereditary hypergraph properties, which are testable in the sense of Definition 17 by Theorem 3.
Lemma 3. If P is a hereditary property of relational structures, then h(P ) is ahereditary property of hypergraphs.
Proof. Let P be a hereditary property of relational structures with vocabularyτ . Assume that P := h(P ) does not satisfy Definition 16. Then, there exist finite
vertex sets V and W , and a morphism f 0 ∈ Inj(W, V ) such that
K (f ) (P (V ) ) 6⊆ P (W ) .

(3)

Since f 0 exists, Inj(W, V ) cannot be the empty set and so |V | ≥ |W |. Let
UV := {0, . . . , |V |−1} and UW := {0, . . . , |W |−1}. By the definition of P, we canV
fix bijections g V : V → UV and g W : W → UW such that P (V ) = K (g ) P (UV )Wand P (W ) = K (g ) P (UW ) . By the definition of P = h(P ), this implies





W
V
6⊆ K (g ) P (UW ) .
K (f ) K (g ) P (UV )Bijections are invertible, and so this implies
”
“

−1
g V ◦f ◦(g W )P (UV ) 6⊆ P (UW ) .
K
−1
and note f 0 ∈ Inj(UW , UV ). Let A0 ∈ P (UV ) be
Rename f 0 := g V ◦ f ◦ g W
0such that K (f ) (A0 ) 6∈ P (UW ) .
We defined P as h(P ) for a hereditary property P of relational structures.
Property P is closed under isomorphisms, and so there is an A := h−1 (A0 ) ∈P ∩STRUC |UV | (τ ) such that the |UW |-element substructure induced by {a | a =f 0 (u) for some u ∈ Uw } does not have P . This contradicts the hereditariness of
P and so P must be hereditary in the sense of Definition 16.
tu
We mapped hereditary relational properties to hereditary hypergraph properties, which are testable by Theorem 3. We will show this implies testability ofthe original properties.
Definition 18. Let A, B ∈ STRUC n (τ ) be structures with vocabulary τ anduniverse U := {0, . . . , n − 1} of size n, k := maxi ai be the maximum arity of thepredicate symbols, and h : STRUC n (τ ) → K (U ) be the map defined above. The
h-distance between A and B is

 

1
U
hdist(A, B) :=
W
|
W
∈
,
h(A)

=
6
h(B)

.
W
W

U
k
k

A Note on the Testability of Ramsey’s Class11

We now relate the two distances with the following simple lemma.
Lemma 4. Let A, B ∈ STRUC n (τ ) be relational structures with vocabulary τand size n. Then, hdist(A, B) ≥ mrdist(A, B).
Proof. Assume that mrdist(A, B) = ε. Then, there exists a predicate symbol
Riai ∈ τ and subtype S ∈ SUB(Riai ) such that sA (S) 4 sB (S) /n|S| = ε. Let
k := maxi ai and let the universe of both structures be Un := {0, . . . , n − 1}.
Consider a random permutation of the universe (i.e., a bijection r : Un → Un )chosen uniformly from the set of such permutations. The probability that thesubstructures induced on {r(0), . . . , r(k−1)} differ in A and B is hdist(A, B). The
probability that the first |S| elements, i.e. {r(0), . . . , r(|S| − 1)}, differ in sA (S)and sB (S) is ε and so hdist(A, B) ≥ ε.
tu
Equality is obtained when |S| = k. It is possible to show that the two distances differ by at most a constant factor, and so the corresponding notions of
testability are essentially equivalent. However, Lemma 4 suffices for our purposes.
Lemma 5. Let P ⊆ STRUC (τ ) be a property of relational structures which ismapped by h to a property of hypergraphs that is testable with one-sided error.
Then, P is testable with one-sided error.
Proof. Let P := h(P ) be the hypergraph property which P is mapped to. We
will show that the following is an ε-tester for P with one-sided error. Let N ≥ 1,
δ > 0 be the constants of Definition 17 for ε. Assume that we are testing a
structure A ∈ STRUC n (τ ) and recall that U = {0, . . . , n − 1}.
1. If #(A) ≤ N , query the entire structure and decide exactly whether A ∈ P .
2. Otherwise, repeat the following q(δ) times.
(a) Uniformly select N elements and query the induced substructure.
(b) If it has P , continue. Otherwise, reject.
3. Accept if all of the induced substructures had P .
If A ∈ P , then all induced substructures have P because P is hereditary andthe tester accepts with probability 1. Next, assume mrdist(A, P ) > ε. We use
Definition 17 to show the tester will find a witness for A 6∈ P with probability
at least 2/3. By Lemma 4, hdist(A, P ) ≥ mrdist(A, P ) > ε. We assumed h(P )is hereditary, and so (by Theorem 3) it is testable in the sense of Definition 17.
The probability that a uniformly chosen N -element substructure does not have
P is at least δ. We use q(δ) to amplify the success probability from δ to 2/3. utThis completes the proof of Theorem 1. All properties expressible in Ramsey’sclass are indistinguishable from instances of F -colorability. Indistinguishability
preserves testability and so it sufficed to show that these instances are testable.
All instances of F -colorability are hereditary relational properties, which aretestable by Theorem 2, which we reduced to the statement by Austin and Tao [4].

12

4

C. Jordan and T. Zeugmann

Conclusion

We have revisited the positive result obtained by Alon et al. [1] in the light of astrong result obtained recently by Austin and Tao [4]. We have shown that thisallows us to extend the proof that properties expressible in Ramsey’s class aretestable, from undirected, loop-free graphs to arbitrary relational structures.
A more direct proof for the testability of Ramsey’s class would be interesting,especially if it results in better query complexity. It would also be interesting toconsider the testability of additional prefix classes and connections with otherclassifications (such as, e.g., that for the finite model property).

References
1. Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large graphs.
Combinatorica 20(4) (2000) 451–476
2. Alon, N., Shapira, A.: A characterization of the (natural) graph properties testablewith one-sided error. SIAM J. Comput. 37(6) (2008) 1703–1727
3. Alon, N., Shapira, A.: A separation theorem in property testing. Combinatorica
28(3) (2008) 261–281
4. Austin, T., Tao, T.: On the testability and repair of hereditary hypergraph properties. Preprint, available on arXiv.org as arXiv:0801.2179v2 (2009)
5. Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. SpringerVerlag (1997)
6. Enderton, H.B.: A Mathematical Introduction to Logic. second edn. Academic
Press (2000)
7. Fischer, E.: Testing graphs for colorability properties. In: Proceedings, 12th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA). (2001) 873–882
8. Fischer, E.: Testing graphs for colorability properties. Random Struct. Algorithms
26(3) (2005) 289–309
9. Jordan, C., Zeugmann, T.: Relational properties expressible with one universal
quantifier are testable. In Watanabe, O., Zeugmann, T., eds.: Stochastic Algorithms: Foundations and Applications, 5th International Symposium, SAGA 2009,
Sapporo, Japan, October 2009, Proceedings. Volume 5792 of Lecture Notes in
Computer Science., Springer (2009) 141–155
10. Kolaitis, P., Vardi, M.: The decision problem for the probabilities of higher-orderproperties. In: STOC ’87: Proceedings of the 19th Annual ACM Symposium on
Theory of Computing, New York, NY, USA, ACM (1987) 425–435
11. Lewis, H.R.: Complexity results for classes of quantificational formulas. J. Comput.
Syst. Sci. 21(3) (1980) 317–353
12. Ramsey, F.P.: On a problem of formal logic. Proc. London Math. Soc. (2) 30(1930) 264–286
13. Rödl, V., Schacht, M.: Property testing in hypergraphs and the removal lemma.
In: STOC ’07: Proceedings of the 39th Annual ACM Symposium on Theory ofComputing, New York, NY, USA, ACM (2007) 488–495