TCS -TR-A-09-39

TCS Technical Report

Contributions to the Classification for Testability:
Four Universal and One Existential Quantifier
byCharles Jordan and Thomas Zeugmann

Division of Computer Science
Report Series A
November 27, 2009

Hokkaido University
Graduate School ofInformation Science and Technology
Email: skip@ist.hokudai.ac.jp

Phone: +81-011-706-7675
Fax:+81-011-706-7675

Contributions to the Classification for
Testability: Four Universal and One Existential
Quantifier
Charles 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 structures that have some desired property and those that are far from having
the property, after examining only a small, random sample of the structure. We focus on the classification of first-order sentences based on theirquantifier prefixes and vocabulary into testable and untestable classes.
This classification was begun by Alon et al. [1] who showed that graphproperties expressible with quantifier patterns ∃∗ ∀∗ are testable but that
there is an untestable graph property expressible with a quantifier pattern ∀∗ ∃∗ . We simplify their untestable example and therefore show that
there is an untestable graph property expressible with each of the following quantifier patterns: ∀4 ∃, ∀3 ∃∀, ∀2 ∃∀2 and ∀∃∀3 .

1Introduction

In property testing, we take a small, random sample of a large structure and wish
to determine if the structure has some desired property or if it is far from having
the property. The hope is that we can gain efficiency in return for not deciding
the problem exactly. We focus on the classification problem for testability, where
the goal is to determine exactly which prefix vocabulary classes of first-order logic
are testable and which are not.
Property testing was first introduced in the context of program verification(cf. Rubinfeld and Sudan [11] and Blum et al. [5]). Goldreich et al. [9] initiated the study of combinatorial property testing, focusing on graphs. Alon etal. [1] first considered the classification problem for testability, although they restricted their attention to undirected, loop-free graphs. They showed that all suchfirst-order sentences1 with quantifier prefixes of the form ∃∗ ∀∗ express testableproperties. They also showed that there exists an untestable property expressible?

Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
Supported by MEXT Grand-in-Aid for Scientific Research on Priority Areas underGrant No. 21013001.
1
We assume throughout that all sentences are in prenex normal form.

??

2Charles Jordan and Thomas Zeugmannwith the prefix ∀∗ ∃∗ . The example they give is (essentially) an encoding of graphisomorphism that can be expressed with a quantifier prefix of the form ∀12 ∃5 .
In studying the classification problem, it is necessary to minimize the numberof quantifiers needed to express untestable properties. Additionally, the firstorder theory of graphs is not restricted to undirected, loop-free graphs. Here,
we show that there exists an untestable property of directed graphs that isexpressible in first-order sentences with prefixes ∀4 ∃, ∀3 ∃∀, ∀2 ∃∀2 , and ∀∃∀3 (seeTheorem 2 for a more formal statement). That is, four universal quantifiers andone existential quantifier, when the existential quantifier follows at least one
universal quantifier, suffice to express an untestable graph property. The proof
is a modification of the proof in Alon et al. [1], which is made possible by thepresence of directed edges and loops.
The results in Jordan and Zeugmann [10] show that one universal quantifier
is not sufficient to express an untestable property (regardless of the vocabulary),and so it would be interesting to determine the status of prefixes containing two
and three universal quantifiers.

2

Preliminaries

In property testing, the goal is always to distinguish structures that have someproperty from those that are far from having the property. We are particularlyinterested in properties that are first-order definable, and so we begin by defining
our logic. Enderton [8] provides a more detailed introduction.
The atomic terms are the (countable) variable symbols xi . There are no function or constant symbols, and so the terms are exactly the atomic terms. The
atomic formulas are E(xi , xj ) and xi = xj , for any two variable symbols xi andxj . The formulas are built from the atomic formulas using the Boolean connectives and first-order quantifiers (∀, ∃) in the usual way. The well-formed formulasor sentences are the formulas which contain no free variables. We have no further
use for formulas that are not well-formed, and so we will refer to the well-formed
formulas simply as formulas.
Our logic contains a special equality symbol (=) which we will always interpret as true equality (i.e., xi = xj is true iff the two symbols refer to the same
object). It also contains a single binary predicate symbol, which we have given
the name E. Of course, the name of this symbol is not important; any fixed,
unique name could have been chosen.
A structure is an object that allows us to interpret a sentence in our logic.
It consists of a finite universe U over which the variable symbols are allowed torange, and a binary relation E corresponding to the symbol E in our logic. Anysuch object can be considered a (directed) graph, and we will now refer to thesestructures as graphs. See Diestel [7] for an introduction to graph theory.
Definition 1. A graph A = (U A , E A ) is a pair consisting of a finite set ofvertices U A and a binary edge relation E A ⊆ U A × U A .

Classification for Testability: Four Universal and One Existential Quantifier3

The natural numbers are denoted by N := {0, 1, . . .}. We denote the set ofgraphs on exactly n vertices by G n and the set of all graphs by G := ∪n∈N G n .
The size of the universe of a graph A = (U A , E A ) is #(A) := |U A |.
A property P is any subset of G. Sentences are interpreted in the usual way,
and so we can decide A |= ϕ for any fixed graph A and first-order sentence ϕ.
Each sentence ϕ therefore defines a property, namely the set of its models,Pϕ := {A | A ∈ G and A |= ϕ} .
The properties that we use in the proof of Theorem 2 involve encodings of
isomorphisms. Graphs A = (U A , E A ) and B = (U B , E B ) are isomorphic if there
is a bijection f : U A 7→ U B such that for all (x, y) ∈ U A × U A , (x, y) ∈ E A
iff (f (x), f (y)) ∈ E B . We say that a property P is closed under isomorphisms
if for all isomorphic A, B ∈ G, it is true that A ∈ P iff B ∈ P . All properties
expressible in our logic are closed under isomorphisms.
The goal in property testing is to distinguish between structures that haveproperties and structures that are far from having them. This requires a distancemeasure, which we define next. In the following, ⊕ denotes exclusive-or and E A
is the edge relation of A.
Definition 2. Let A = (U, E A ) and B = (U, E B ) be any two graphs such that#(A) = #(B) = n. The distance between A and B isdist(A, B) :=|{(x1 , x2 ) | x1 , x2 ∈ U and E A (x1 , x2 ) ⊕ E B (x1 , x2 )}|.
n2

The dist distance is the fraction of edges on which the two graphs disagree.
This is the dense graph model introduced by Goldreich et al. [9] and is essentially based on the adjacency matrix representation. The distance generalizes toproperties in the following way.
Definition 3. Let P ⊆ G be a property of graphs and let A ∈ G n be a graphwith n vertices. Then,dist(A, P ) :=min

A0 ∈G n ∩P

dist(A, A0 ) .

We are now able to define property testing itself. The following definitions
are typical, but we will also mention several variations.
Definition 4. An ε-tester for property P is a randomized algorithm given an
oracle which answers queries for the universe size and queries for edges on desired pairs in a graph A. The tester must accept with probability at least 2/3 if
A has P and must reject with probability at least 2/3 if dist(A, P ) ≥ ε.
Definition 5. A property P is testable if for every ε > 0 there is an ε-tester for
P making a number of queries which is upper-bounded by a function depending
only on ε.

4Charles Jordan and Thomas Zeugmann

We allow different ε-testers for each ε > 0 and our definitions are therefore non-uniform. The uniform case is strictly more difficult (see, e.g., Alon andShapira [3]). We are interested in proving untestability, and our results holdeven in the non-uniform case. In oblivious testing (see Alon and Shapira [2]),the testers are not given access to the size of the universe. Again, our results holdin the more general case where the testers may make decisions based on the sizeof the universe. In a similar way, the number of loops in a graph is asymptotically insignificant compared to the number of possible non-loops. Modifying thedefinition of distance to account for this makes testing strictly more difficult (seeJordan and Zeugmann [10]) and so we use the more general definition above.
However, the (possible) loops seem to affect the notion of indistinguishability
defined by Alon et al. [1]. We use the following modification of Definition 2.
Definition 6. Let A = (U, E A ) and B = (U, E B ) be any two graphs such that#(A) = #(B) = n. For convenience, let
d1 (A, B) :=|{x | x ∈ U and E A (x, x) ⊕ E B (x, x)}|, andn|{(x1 , x2 ) | x1 , x2 ∈ U, x1 6= x2 , and E A (x1 , x2 ) ⊕ E B (x1 , x2 )}|.
n2
The mr-distance between A and B is
d2 (A, B) :=mrdist(A, B) := max {d1 (A, B), d2 (A, B)} .
That is, although the number of loops is asymptotically insigificant, a tester
can easily restrict its queries to the form (x, x) and distinguish between graphsthat differ only in loops. Definition 6 is a special case of a definition from Jordan
and Zeugmann [10]. We use the following simple variation of indistinguishability
for graphs that may contain loops.
Definition 7. Two properties P and Q of graphs are indistinguishable if they
are closed under isomorphisms and for every ε > 0 there exists an Nε such thatfor any graph A with universe of size n ≥ Nε , if A has P then mrdist(A, Q) ≤ ε
and if A has Q then mrdist(A, P ) ≤ ε.
The important fact to note is that indistinguishability preserves testability.
The proof of the following is analogous to that given in Alon et al. [1].
Theorem 1. If P and Q are indistinguishable, then P is testable if and only if
Q is testable.
Our classification definitions are from Börger et al. [6] except that we omit
function symbols. We omit a detailed discussion, but the following is for completeness. Let Π be a string over the four-character alphabet {∃, ∃∗ , ∀, ∀∗ }. Then[Π, (0, 1)]= is the set of sentences in prenex normal form which satisfy the following conditions:Classification for Testability: Four Universal and One Existential Quantifier

5

1. The quantifier prefix is contained in the language specified by the regularexpression Π.
2. There are zero (0) monadic predicate symbols.
3. There is at most one (1) binary predicate symbol.
4. There are no other predicate symbols.
5. Equality (=) may additionally appear.
That is, [Π, (0, 1)]= is the set of sentences in the logic that we have defined above
whose quantifier prefixes in prenex normal form match Π.

3

An Untestable Property

We will begin by defining property P , which is essentially the graph isomorphism
problem for undirected loop-free graphs encoded in directed graphs that may
contain loops. We will begin by showing in Lemma 1 that P is indistinguishable
from property Pf (cf. Definition 9) which is expressible in any of the prefix
vocabulary classes mentioned in Theorem 2. We will then show that P is not
testable. Indistinguishability preserves testability and so this implies that Pf isalso untestable, which will suffice to show the following theorem.
Theorem 2. The following prefix classes are not testable:
1. [∀4 ∃, (0, 1)]=
2. [∀3 ∃∀, (0, 1)]=
3. [∀2 ∃∀2 , (0, 1)]=
4. [∀∃∀3 , (0, 1)]=
We define property P as follows. First, a graph that has property P must
consist of an even number of vertices, of which exactly half have loops. The
subgraph induced by the vertices with loops must be isomorphic to that inducedby the vertices without loops, ignoring all loops, and there must be no edges
connecting the vertices with loops to those without loops. Finally, all edges
must be undirected (i.e., an edge from x to y implies an edge from y to x). We
refer to such undirected edges as paired edges.
Definition 8. A graph G ∈ G n has P iff the following are true.
1. For some s, n = 2s.
2. There are exactly s vertices x satisfying E(x, x). We will refer to the set ofsuch vertices as H1 and to the remaining s vertices as H2 .
3. The substructure induced by H1 is isomorphic to that induced by H2 when
all loops are removed.That is, there is a bijection f from H1 to H2 such thatfor distinct x, y ∈ H1 , it is true that G |= E(x, y) iff G |= E(f (x), f (y)).
4. There are no edges between H1 and H2 .
5. All edges are undirected.

6Charles Jordan and Thomas Zeugmann

Graph isomorphism is not directly expressible in first-order logic, and so we
use the following encoding where the bijection f is made explicit by adding nedges between H1 and H2 .
Definition 9. A graph G ∈ G n has Pf iff the following are true.
1. For every vertex x, if E(x, x) then there is an edge from x to exactly one ysuch that ¬E(y, y).
2. For every vertex x, if ¬E(x, x) then there is an edge from x to exactly one
y such that E(y, y).
3. For all vertices x and y, E(x, y) iff E(y, x).
4. For all pair-wise distinct vertices x1 , x2 , x3 , x4 , if E(x1 , x1 ), ¬E(x2 , x2 ),E(x3 , x3 ), ¬E(x4 , x4 ), E(x1 , x2 ) and E(x3 , x4 ), then E(x1 , x3 ) iff E(x2 , x4 ).
Expressing Conditions 1 and 2 as “there is at most one such y” and “there
is at least one such y,” Pf can be expressed in each of the classes [∀4 ∃, (0, 1)]= ,[∀3 ∃∀, (0, 1)]= , [∀2 ∃∀2 , (0, 1)]= and [∀∃∀3 , (0, 1)]= .
For example, in the class [∀∃∀3 , (0, 1)]= , we can express Pf byh∀x1 ∃x2 ∀x3 ∀x4 ∀x5 :E(x1 , x1 ) → (¬E(x2 , x2 ) ∧ E(x1 , x2 ) ∧((¬E(x3 , x3 ) ∧ ¬E(x4 , x4 ) ∧ E(x1 , x3 ) ∧ E(x1 , x4 )) → x3 = x4 )) ∧¬E(x1 , x1 ) → (E(x2 , x2 ) ∧ E(x1 , x2 ) ∧((E(x3 , x3 ) ∧ E(x4 , x4 ) ∧ E(x1 , x3 ) ∧ E(x1 , x4 )) → x3 = x4 )) ∧(E(x1 , x3 ) → E(x3 , x1 )) ∧
E(x1 , x1 ) ∧ E(x4 , x4 ) ∧ ¬E(x3 , x3 ) ∧ ¬E(x5 , x5 ) ∧ E(x1 , x3 ) ∧ E(x4 , x5 ) ∧
x1 6= x3 ∧ x1 6= x4 ∧ x1 6= x5 ∧ x3 6= x4 ∧ x3 6= x5 ∧ x4 6= x5 →i
(E(x1 , x4 ) ↔ E(x3 , x5 )) .
To express Pf in the other classes of Theorem 2 it is sufficient to change only
the quantifier prefix.
The two properties P and Pf differ only in the edges which make the isomorphism explicit in Pf but are forbidden in P . There are at most n such edges, allof which are not loops. This suffices to prove the following.
Lemma 1. Properties P and Pf are indistinguishable.
Proof. Let ε > 0 be arbitrary and let Nε = ε−1 . Assume that G is a structurethat has property P and that #(G) > Nε . We will show that mrdist(G, Pf ) < ε.
Structure G has P and so there is a bijection f satisfying Condition 3 ofDefinition 8. For all x ∈ H1 , we add the edges E(x, f (x)) and E(f (x), x) andcall the result G0 . Property Pf differs from P only in that the isomorphism isClassification for Testability: Four Universal and One Existential Quantifier

7

made explicit by the edges connecting loops and non-loops, and so G0 has Pf .
Indeed, it satisfies Conditions 1 and 2 of Definition 9 because G had no edges
between loops and non-loops and we have connected each to exactly one of theother, following the bijection f . Next, G0 satisfies Condition 3 of Definition 9
because G satisfied Condition 5 of Definition 8 and we added only paired edges.
Finally, G0 satisfies Condition 4 of Definition 9 because the edges between loops
and non-loops follow the isomorphism f from Condition 3 of Definition 8.
We have added exactly n (directed) edges, none of which are loops and so
mrdist(G, P ) ≤ mrdist(G, G0 ) = 0 + n/n2 < ε, where the inequality holds forn > Nε . The converse is analogous; given a G that has property Pf , we simply
remove the n edges between loops and non-loops after using them to construct
the isomorphism f .
tuProperties P and Pf are indistinguishable. Testability is preserved by indistinguishability (cf. Theorem 1) and therefore showing that P is not testablesuffices to prove that Pf is not testable (and therefore Theorem 2). The proof
closely follows that of Alon et al. [1]. The crucial lemma is the following, a combination of Lemmata 7.3 and 7.4 from Alon et al. [1]. We use countH (T ) to referto the number of times that a graph T occurs as an induced subgraph in H. A
bipartite graph is a graph where we can partition the vertices into two sets H1and H2 such that there are no edges “internal” to the partitions. That is, for all
x1 , y1 ∈ H1 and x2 , y2 ∈ H2 , ¬E(x1 , y1 ) and ¬E(x2 , y2 ).
Lemma 2 (Alon et al. [1]). There exists a constant ε0 > 0 such that for every
D ∈ N, there exist two undirected bipartite graphs H = H(D) and H 0 = H 0 (D)satisfying the following conditions.
1. Both H and H 0 have a bipartition into classes U1 and U2 , each of size t.
2. In both H and H 0 , for all subgraphs X with size t/3 ≤ #(X) ≤ t, there are
more than t2 /18 undirected edges between X and the remaining part of thegraph.
3. The minimum degree of both H and H 0 is at least t/3.
4. dist(H, H 0 ) ≥ ε0 .
5. For all D-element graphs T , countH (T ) = countH 0 (T ).
It is worth noting that the above is for undirected, loop-free graphs. However,bipartite graphs never have loops and “undirected” in our setting results inpaired edges. It is easy to show that if two structures agree on the counts for all
size D induced subgraphs, they agree on the counts for all induced subgraphs ofsize at most D. This is done by applying Lemma 3 inductively.
Lemma 3. Let H and H 0 be two graphs, both of size s, and let 2 < D ≤ s. If
for every graph T of size D, countH (T ) = countH 0 (T ), then for every graph T 0
of size D − 1, countH (T 0 ) = countH 0 (T 0 ).

8Charles Jordan and Thomas Zeugmann

Proof. Assume H and H 0 satisfy the initial conditions of Lemma 3, but that
there exists a T 0 of size D − 1 such that countH (T 0 ) 6= countH 0 (T 0 ). Let C =0{T | #(T ) = D
subgraph}.
Pand T contains T as an induced
Note P
that T ∈C countH (T ) countT (T 0 ) = countH (T 0 )(s − D + 1) and likewise for T ∈C countH 0 (T ) countT (T 0 ). We have assumed that H and H 0 satisfy
countH (T ) = countH 0 (T ) for T ∈ C, but countH (T 0 ) 6= countH 0 (T 0 ), giving acontradiction and the Lemma follows.
tuRecall that testing is easiest under the dist definition, and so Lemma 4 also
implies that P is not testable under the mrdist definition.
Lemma 4. Property P is not testable under the dist definition.
Proof. Assume that P is testable. Then, there exists an ε-tester for
ε := 1/2 min {ε0 /4, 1/72} ,where ε0 is the constant from Lemma 2. We can assume without loss of generalitythat the tester queries all edges in a random sample of D := D(ε) vertices.
Consider the graph G which contains two copies of the H = H(D) from
Lemma 2, where one of the copies is marked by loops on each vertex and there
are no edges between the copies. This graph has property P , and so the tester
must accept it with probability at least 2/3. Next, consider the graph G0 whichcontains one copy of H marked by loops and one copy of H 0 , again where
there are no edges between the two (induced) subgraphs. Graph G0 is such that
dist(G0 , P ) ≥ ε (cf. Lemma 5) and so it must be rejected with probability atleast 2/3. Both G and G0 consist of two bipartite graphs, each of which has abipartition into two classes of size t, and so #(G) = #(G0 ) = 4t.
However, G and G0 both contain exactly the same number of each induced
subgraph with D vertices. This is because both have loops on exactly half ofthe vertices and the two halves are not connected by any edges. Some of the Dvertices must be in the first copy of H and the others in the second H (resp. H 0 ).
By Lemma 3, H and H 0 contain the same number of each induced subgraphwith size at most D. The tester therefore obtains any fixed sample with thesame probability in G and G0 and is unable to distinguish between them. It istherefore unable to accept G with probability 2/3 and reject G0 with probability
2/3. This completes the proof, conditional on Lemma 5.
tuLemma 5. The graph G0 is such that dist(G0 , P ) ≥ ε.
Proof. Assume that dist(G0 , P ) < ε. Then, there is an M ∈ P such that
dist(G0 , M ) < ε. Let M1 be the set of vertices with loops in M and M2 theset of vertices without loops. We will refer to the vertices with loops in G0 as
H and to those without loops as H 0 . Without loss of generality, assume that|M1 ∩ H| ≥ |M1 ∩ H 0 |. Then, |M1 ∩ H| ≥ t. We let α1 be the set M1 \H and α2
be M2 \H 0 . Note that |α1 | = |α2 | and |α1 | ≤ t because |M1 ∩ H| ≥ t.
Informally, M is formed by moving the vertices α1 from H 0 to H and thevertices α2 from H to H 0 , and then possibly making other changes. There arethree cases, which we will consider in order.

Classification for Testability: Four Universal and One Existential Quantifier9

1. |α1 | = 0.
2. |α1 | ≥ t/3.
3. 0 < α1 < t/3.
If |α1 | = 0, then we can construct M from G0 without exchanging vertices
between H and H 0 , and in particular, construct H 0 from H (ignoring loops), bymaking less than ε(4t)2 modifications. However, dist(H, H 0 ) ≥ ε0 by Lemma 2
and so this must require at least ε0 (2t)2 modifications. By definition, ε < ε0 /4
so ε(4t)2 < ε0 (2t)2 . The first case is therefore not possible.
Recall that |α1 | ≤ t. If |α1 | ≥ t/3, then by Condition 2 of Lemma 2 there
exists at least t2 /18 undirected edges between α1 and H 0 \α1 and between α2and H\α2 . All of these edges must be removed to satisfy P because each would
connect a vertex with a loop to a vertex without a loop. Therefore, dist(G0 , M ) ≥4t2 /18(4t)2 = 1/72. But, ε < 1/72 and so the second case is not possible.
Therefore, it must be that 0 < |α1 | < t/3. Here, we will show that it must be
the case that α1 and α2 are relatively far apart. If they are not far apart, then it
is possible to modify them instead of swapping them. This essentially results inthe first case considered above. Condition 3 of Lemma 2 requires that each vertex
has relatively high degree. These edges can be either internal to α1 (resp. α2 )or connecting α1 (α2 ) with H 0 \α1 (H\α2 ). If α1 and α2 are relatively far apart,
then we will see that this forces too many edges “outside” of α1 (resp. α2 ),resulting in a similar situation to the second case considered above.
We have assumed that dist(G0 , M ) < ε and that we can construct M fromG0 by making less than ε(4t)2 modifications if we move α1 to H and α2 to H 0 .
This entails the following modifications.
1. Removing all edges connecting α1 to H 0 \α1 .
2. Removing all edges connecting α2 to H\α2 .
3. Adding any required edges between α1 and H\α2 .
4. Adding any required edges between α2 and H 0 \α1 .
5. Changing α1 , α2 , H\α2 and H 0 \α1 to their final forms.
We can assume that the total number of modifications is less than ε(4t)2 . It
must be that dist(α1 , α2 )|α1 |2 /(4t)2 + ε ≥ ε0 /4. If this does not hold, then we
could first modify α1 to make it identical to α2 and then make H 0 identical to
M2 . Next, M2 is identical to M1 , which we could make identical to H. This would
require less than ε0 (2t)2 modifications, which would violate Lemma 2. Therefore,dist(α1 , α2 ) ≥16(ε0 /4 − ε)t2.
|α1 |2(1)

If both α1 and α2 are complete graphs then they cannot be far apart. Given
that all vertices in α1 (α2 is analogous) have degree at least t/3, then there mustbe at least|α1 |(t/3 − |α1 | + 1) + 2r

10Charles Jordan and Thomas Zeugmannedges connecting α1 to H 0 \α1 , where r is the number of edges internal to α1that must be ommited to satisfy (1). The simple lower bound on r, the numberof edges needed for two graphs with at most r edges to be dist(α1 , α2 )-far, that
follows from dist(α1 , α2 ) ≤ 2r/|α1 |2 is sufficient. Combining this with (1) yieldsr ≥ 8(ε0 /4 − ε)t2 .

(2)

The number of edges connecting α1 to H 0 \α1 is therefore, by (2), at least|α1 |(t/3 − |α1 | + 1) + 16(ε0 /4 − ε)t2 ≥ 16(ε0 /4 − ε)t2 .
All of these edges must be removed to move α1 (resp. α2 ), and sodist(G0 , M ) ≥16(ε0 /4 − ε)t2
ε0
=
− ε.
(4t)2
4

We have defined ε ≤ ε0 /8 and so dist(G0 , M ) ≥ ε, a contradiction.
The cases are exhausted and so dist(G0 , P ) ≥ ε as desired.

4tuConclusion

Property testing is an application of induction (in the philosophy of science
sense), in which we obtain a small, random sample of a structure and seek todetermine whether the structure has a desired property or is far from having theproperty. We have considered the classification problem for testability, classifying the prefix vocabulary classes of first-order logic according to their testability.
In particular, we have given a simplified version of the untestable property from
Alon et al. [1] for the case of directed graphs which may contain loops. This implies that there exists an untestable property expressible with quantifier prefixes∀4 ∃, ∀3 ∃∀, ∀2 ∃∀2 and ∀∃∀3 . It would be worthwhile to determine the testabilityof the prefixes containing two or three universal quantifiers (for graphs or moregeneral relational structures).

5

Appendix

We complete the proof of Lemma 2 following the outline by Alon et al. [1]. Allgraphs in this appendix are undirected, loop-free graphs on labelled vertices.
5.1

Proof of Lemma 2

Lemma 2 (Alon et al. [1]) There exists a constant ε0 > 0 such that for every
D ∈ N, there exist two bipartite graphs H = H(D) and H 0 = H 0 (D) satisfying
the following conditions.

Classification for Testability: Four Universal and One Existential Quantifier11

1. Both H and H 0 have a bipartition into classes U1 and U2 , each of size t.
2. In both H and H 0 , for all subgraphs X with size t/3 ≤ #(X) ≤ t, there are
more than t2 /18 undirected edges between X and the remaining part of thegraph.
3. The minimum degree of both H and H 0 is at least t/3.
4. dist(H, H 0 ) ≥ ε0 .
5. For all D-element graphs T , countH (T ) = countH 0 (T ).
Proof. We follow the proof outlined by Alon et al. [1] and begin with their proofof the following simple lemma.
Lemma 6 (Alon et al. [1]). There exist constants ε and N such that every
2graph H with n > N (labelled) vertices is ε-far from all but at most 2n /5 othergraphs with the same vertex set.
εProof. Choose an ε < 1/2 such that eε < 21/10 and an N > ε−1 such that2nn < 2n /10 for n > N . The number of graphs that are less than ε-far from agiven H with n > N vertices is at mostn!

εn2  n
X
2

i

i=0

.

(3)





a−1
n2
inductively to εn
We apply the identity ab = a−1
2 . A simple
b−1 +b
inductive proof shows that applying this identity once to each term, repeating
 Pa
 n2 −a n2= i=0 ai εnfor a levels, gives εn2 −i =: L(a), and so
2


Pn

n2
εn2



n
i



= L(n) =n   2
X
n −n
n
i=0

εn2 − ii.

(4)

= 2n , there are 2n > εn2 total “terms” in the sumPεn2 (n2 )
can therefore be paired with amation. Each term in the summation
Recalling that

i=0

i=0

i

term from (4) that upper-bounds it. Combining with (3), we see that the numberof graphs that are less than ε-far from H is less than 2 εn2
2
n
n e
n!
<
n
< 2n /5 ,2εnεt Lemma 6
u

as desired.

Next, we show that most (sufficiently large) bipartite graphs satisfy Conditions 2 and 3 of Lemma 2. We use the following statement of Chernoff bounds(see Appendix A of Alon and Spencer [4]);Pr[X < a] ≤ E[e−λX ]eλa ,where λ is chosen to optimize the bound, and also the following lemma.

(5)

12

Charles Jordan and Thomas Zeugmann

Lemma 7 (Lemma A.1.5 in Alon and Spencer [4]).
2eλ + e−λ= cosh(λ) ≤ eλ /2 .
2

(6)Lemma 8 (Alon et al. [1]). There exists an N 0 such that for n > N 0 , at2
least 12 2n of the bipartite graphs with a given (labeled) bipartition U1 , U2 where|U1 | = |U2 | = n satisfy both of the following conditions.
(8.1) The minimum degree is at least n/3.
(8.2) For every subset X of U1 ∪ U2 with size n/3 ≤ |X| ≤ n, there are morethan n2 /18 edges between X and (U1 ∪ U2 )\X.
Proof. We let G be a random bipartite graph with a given, labeled bipartition
U1 , U2 chosen in the following way. Each possible edge (u, v) ∈ U1 × U2 isplaced independently and uniformly with probability 1/2. There are n2 possible
2edges, and so each of the 2n possible such bipartite graphs is generated withequal probability. The probability of G satisfying (8.1) and (8.2) above is (bydefinition)|{H | H is such a graph that satisfies (8.1) and (8.2)}|.
2n2
We want a lower-bound on the number of such graphs, or equivalently a22
lower-bound on Pr[G satisfies (8.1) and (8.2)] · 2n that is greater than 12 2n . It
suffices therefore to show that this probability is at least 1/2. Using the union
bound, Pr[G satisfies (8.1) and (8.2)] ≥1 − Pr[G does not satisfy (8.1)] − Pr[G does not satisfy (8.2)] .
We will show in Claims 1 and 2 that this is at least 1 − o(1) > 1/2, where theinequality holds for sufficiently large N 0 . We will let U = U1 ∪ U2 be the set of
all vertices.
Claim 1 Pr[G does not satisfy (8.1)] = o(1).
Proof. Let deg(v) be the degree of a vertex v. By the union bound,X
Pr[G does not satisfy (8.1)] ≤Pr[deg(v) ≤ n/3].
v∈U

Let Nuv be an “indicator” variable for the event that there is an edge E(u, v)
which is normalized to take the following values,(−1, if ¬E(u, v);
Nuv :=(7)
1, if E(u, v).

13Classification for Testability: Four Universal and One Existential Quantifier

Then, deg(v) ≤ n/3 iff
X

Yv :=

Nuv ≤ −n/3 ,{u|u∈U1 if v∈U2 , u∈U2 if v∈U1 }P
Pand sov∈U Pr[deg(v) ≤ n/3] =v∈U Pr[Yv ≤ −n/3]. We apply (5) andLemma 7, and so2

Pr[Yv ≤ −n/3] ≤ E[e−λYv ]e−λn/3 = cosh(λ)e−λn/3 ≤ eλ n/2−λn/3 .
Minimizing the bound by setting λ = 1/3 gives
Pr[G does not satisfy (8.1)] ≤ (2n)e−n/18 = o(1) ,t Claim 1u

as desired.
Claim 2 Pr[G does not satisfy (8.2)] = o(1).
Proof. By the union bound,X

Pr[G does not satisfy (8.2)] ≤Pr[G violates (8.2) with X] .

{X|X⊆U,n/3≤|X|≤n}(8)
Let a := |X ∩ U1 |, b := |X ∩ U2 |, i := a + b = |X|. As
Pin (7), we let Nuv be
a normalized indicator for the event E(u, v). Let YX := {u,v|u∈X,v∈U \X} Nuv .
Then, G violates (8.2) with X iff YX < −i(2n − i) + n2 /9. Using again (5),X
Pr[G violates (8.2) with X]={X|X⊆U,n/3≤|X|≤n}X

Pr[YX < −i(2n − i) + n2 /9]≤{X|X⊆U,n/3≤|X|≤n}X

2E[e−λYX ]eλ(−i(2n−i)+n /9)={X|X⊆U,n/3≤|X|≤n}

X

2

Y

E[e−λNuv ]eλ(−i(2n−i)+n /9) .

(9){X|X⊆U,n/3≤|X|≤n} {u,v|u∈X,v∈U \X}

We can divide the product into four cases,


Q

−λNuv
]=
{u,v|u∈X,v∈U \X} E[eY{u,v|u∈X∩U1 ,v∈U1 \X}Y{u,v|u∈X∩U1 ,v∈U2 \X}Yeλ  

eλ  ·{u,v|u∈X∩U2 ,v∈U2 \X}eλ + e−λ  
2Y{u,v|u∈X∩U2 ,v∈U1 \X}eλ + e−λ 
.
2

14

Charles Jordan and Thomas Zeugmann

Recalling Lemma 7 and combining with (9), Pr[G does not satisfy (8.2)] ≤“”22
λ(a(n−a)+b(n−b))+ λ2 (a(n−b)+b(n−a))+λ −i(2n−i)+ n9

X

e

.

(10)

{X⊆U |n/3≤|X|≤n} n 
There are at most na i−achoices of X with size i when a = |X ∩ U1 | andb = i − a = |X ∩ U2 |, and so after simplifying, (10) is at mosti  
n
X
X
2
2
2
λ2
n
n
eλ(2ai+n /9−2a −in)+ 2 (2a +in−2ai) .
a
i−a
a=0

(11)

i=dn/3eUsing the simple bound
n
i
X
X

n
k



≤


en k
, we get that (11) is at most
k
2

λ2

2

2

ei+a ln(n/a)+(i−a) ln(n/(i−a))+λ(2ai+n /9−2a −in)+ 2 (2a +in−2ai) .

i=dn/3e a=0

(12)
2

2

Let us consider 2ai + n /9 − 2a − in. If a ≥ 5n/6, then
2ai +

n2
n2
25
− 2a2 − in ≤ 2in +− n2 − in
9
9
18
5 2
≤ − n = −Θ(n2 ) .
18

If a < 5n/6, then the maximum of 2ai + n2 /9 − 2a2 − in occurs at a = i/2.
Therefore,
2ai +

n2
n2
i2
i2
n2
− 2a2 − in ≤ i2 +− − in =
+
− in
9
9
2
2
9
n2
n2
n2
n2
+
−
=−
= −Θ(n2 ) ,
≤
18
9
3
6

because the maximum occurs at the boundary i = n/3. Applying these bounds,(12) is at most
n
i
X
X

2

λ2

2

ei+a ln(n/a)+(i−a) ln(n/(i−a))+λ(−n /6)+ 2 (2a +in−2ai) .

(13)

i=dn/3e a=0√
Choosing the non-optimal λ = 1/ n and looking only at asymptotics, we see
from (13) that Pr[G does not satisfy (8.2)] ≤niXXeO(n)+O(n ln n)−Θ(n3/2)+O(n) = O(n2 )e−Θ(n3/2 ) = o(1) .

i=dn/3e a=0

t Claim 2uClassification for Testability: Four Universal and One Existential Quantifier

The two claims combine to give the lemma.

15

t Lemma 8u

We are now ready to complete the proof of Lemma 2. We let ε0 be the ε ofLemma 6, and choose a sufficiently large s = 2n > max(N, 2N 0 ) where N andD
N 0 are from Lemmas 6 and 8 respectively. There are at most E := 2( 2 ) graphs
on D vertices and each appears at most sD times as an induced subgraph in aDgraph on s vertices. An “appearance count” for a graph is an 2( 2 ) -tuple giving,for each of the possible graphs on D vertices, the number of appearances as an
induced subgraph. There are therefore at most (sD )E = 2DE log s many distinct
2
appearance counts (tuples). By Lemma 8, there are at least 12 2n bipartite graphs
satisfying the conditions of that lemma, and
2
2
2
2
1 n2
2 = 2s /4−1 = 2s /20−1 2s /5 > 2DE log s 2s /5 ,2

where the inequality holds for sufficiently large s.
There are at most 2DE log s distinct appearance counts and so there must2
be some appearance count shared by more than 2s /5 of the above graphs. By
Lemma 6, there must be two such graphs (satisfying the conditions of Lemma 8
and with the same appearance count) that are ε-far from each other. ut Lemma 2

References[1] Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficienttesting of large graphs. Combinatorica, 20(4):451–476, 2000.
[2] Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties
testable with one-sided error. SIAM J. Comput., 37(6):1703–1727, 2008.
[3] Noga Alon and Asaf Shapira. A separation theorem in property testing. Combinatorica, 28(3):261–281, 2008.
[4] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley, third edition,
2008.
[5] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting withapplications to numerical problems. J. of Comput. Syst. Sci., 47(3):549–595, 1993.
[6] Egon Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem.
Springer-Verlag, 1997.
[7] Reinhard Diestel. Graph Theory. Springer, third edition, 2006.
[8] Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press,
second edition, 2000.
[9] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998.
[10] Charles Jordan and Thomas Zeugmann. Relational properties expressible with one
universal quantifier are testable. In Osamu Watanabe and Thomas Zeugmann,editors, Stochastic Algorithms: Foundations and Applications, 5th International
Symposium, SAGA 2009, Sapporo, Japan, October 2009, Proceedings, volume 5793
of Lecture Notes in Computer Science, pages 141 – 155. Springer, 2009.
[11] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials
with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996.