Testing properties of graphs and functions

Introduction

Graph property testing is a very active area in computer science. In its most restricted form (and this will be our concern in this paper), it studies properties of (very large) graphs that can be tested by studying a randomly chosen induced subgraph of bounded size.

To be more precise, we have to describe what kind of error is allowed. In this paper, by graph we always mean a finite simple graph. A graph property is a class of graphs invariant under isomorphism. The edit distance of two graphs $G_{1},G_{2}$ on the same node set is $|E(G_{1})\triangle E(G_{2})|$. The edit distance of a graph $G$ from a graph property is the minimum number of edges we have to change (add or delete) to obtain a graph with the property. If no graph with the same number of nodes has the property, then this distance is infinite.

A graph property $\mathcal{P}$ is testable, if there exists another property $\mathcal{P}^{\prime}$ (called a test property) satisfying the following conditions:

(a) if a graph $G$ has property $\mathcal{P}$, then for all $1\leq k\leq|V(G)|$ at least a fraction of $2/3$ of its $k$-node induced subgraphs have property $\mathcal{P}^{\prime}$, and

(b) for every $\varepsilon>0$ there is a $k_{\varepsilon}\geq 1$ such that if $G$ is a graph whose edit distance from $\mathcal{P}$ is at least $\varepsilon|V(G)|^{2}$, then for all $k_{\varepsilon}\leq k\leq|V(G)|$ at most a fraction of $1/3$ of the $k$-node induced subgraphs of $G$ have property $\mathcal{P}^{\prime}$.

The notion of testability has other variations: we may also know the number of nodes of $G$, or we can take a sample whose size is growing slowly with the size of $G$, etc. The definition above is in a sense the most restrictive, and it has often been referred to with adjectives like “oblivious testing” and ”order independent testing”. Since this is the only version we consider in this paper, we simplify terminology by calling it simply “testable”.

We could strengthen this definition by requiring a fraction of $1-\varepsilon$ instead of $2/3$ and a fraction of $\varepsilon$ instead of $1/3$. We could also weaken it by allowing the test property $\mathcal{P}^{\prime}$ to depend on $\varepsilon$. It can be seen that neither of these modifications would change the notion of testability.

A surprisingly general sufficient condition for testability was proved by Alon and Shapira : Every hereditary graph property is testable. (A graph property is hereditary, if whenever a graph has the property, then all its induced subgraphs also have the property.) Alon, Fischer, Newman and Shapira gave a characterization of testable graph properties in terms of Szemerédi partitions (which is quite involved and we don’t quote it here). In fact, Szemerédi partitions play a central role in most results of this theory.

One of the main graph theoretic results in this paper is to give another combinatorial characterization of testable properties (Theorem 3.20). It says that a graph property is testable if and only if for every graph with the property, a sufficiently large “typical” induced subgraph is “close” to having the property.

Our main goal is, however, to treat property testing in terms of the theory of convergent (dense) graph sequences and graph limits . A sequence of graphs $(G_{n})$ is convergent if the density of copies of any fixed graph $F$ in $G_{n}$ tends to a limit. It turns out that the limit of a convergent graph sequence can be represented by a symmetric measurable function $W:~^{2}\to$, and that many problems and constructions in graph theory have a simpler and cleaner formulation when extended to this limit (see for a survey).

Parameter testing (or estimation) is closely related to property testing, but is in many respects simpler. This area has a very natural treatment in the framework of graph limits . The two theories are connected by a result of Fischer and Newman , who proved that the edit distance from a testable property is a testable parameter. The analytic theory of property testing is more involved than the analytic theory of parameter testing, mainly because of the different type of error that is permitted.

Above, we used the “edit distance” of two graphs in the definition of testable properties. However, there is a different distance, called the “cut distance”, which plays a central role in graph convergence; for example, a sequence of graphs is convergent if and only if it is Cauchy in an appropriately normalized cut distance. The main technical issue in the analytic theory of property testing is the interplay between these two distances; see Section 2.5 for some auxiliary results of this nature that might be interesting on their own right.

The space of limit objects (two-variable functions) with the “cut distance” is compact, a fact which is essentially equivalent to various (weak and strong) versions of Szemerédi’s Regularity Lemma . So while we do not explicitly use the Regularity Lemma, it is implicit in the utilization of the compactness of this space.

A further surprisingly general result using the edit distance is the theorem of Alon and Stav , proving that for every hereditary property, a random graph with appropriate density is the farthest from the property in edit distance. The analytic results developed in this paper allow us to state and prove a simple analytic analogue of this fact, from which the original result follows along with generalizations. Similar analytic analogues are derived for the other above mentioned results.

Preliminaries

For two graphs $F$ and $G$, a homomorphism from $F$ to $G$ is an adjacency preserving map $V(F)\to V(G)$. The number of such homomorphisms is denoted by ${\rm hom}(F,G)$. We’ll almost always use the normalized version of this number,

which can be interpreted as the probability that a random map $V(F)\to V(G)$ is a homomorphism. We denote by ${\rm ind}(F,G)$ the number of those injective homomorphisms that also preserve non-adjacency (in other words, the number of induced copies of $F$ in $G$). The normalized version of this number is

2 Functions and graphons

A function $W\in\mathcal{W}$ is called a stepfunction, if there is a partition $S_{1}\cup\dots\cup S_{k}$ of $$into measurable sets such that$W$is constant on every product set$S_{i}\times S_{j}$. The number$k$is the number of steps of$W$.

Let $\mathcal{F}_{k}$ denote the set of all graphs on node set $[k]=\{1,\dots,k\}$. For $W\in\mathcal{W}_{0}$ and $F\in\mathcal{F}_{k}$, define

Two functions $W_{1},W_{2}\in\mathcal{W}_{0}$ are isomorphic, in notation $W_{1}\cong W_{2}$, if $t(G,W_{1})=t(G,W_{2})$ for every graph $G$. It was proved by Borgs, Chayes and Lovász that two functions are isomorphic if and only if there is a third function $U\in\mathcal{W}_{0}$ and two measure preserving maps $\phi_{1},\phi_{2}:~\to$ such that $W_{i}(x,y)=U(\phi_{i}(x),\phi_{i}(y))$ for $i=1,2$ and almost all $x,y\in$. An isomorphism class of functions in $\mathcal{W}_{0}$ is called a graphon .

A sequence of graphs $(G_{n})$ with $|V(G_{n})|\to\infty$ is called convergent, if $t(F,G_{n})$ tends to a limit for every fixed graph $F$. (This is equivalent with $t_{\rm ind}(F,G_{n})$ tending to a limit for every $F$.) It was proved in that for every convergent sequence of graphs $(G_{n})$ there is a function $W\in\mathcal{W}_{0}$ such that $t(F,G_{n})\to t(F,W)$ for every graph $F$. We call $W$ the limit of the sequence, and write $G_{n}\to W$. Every function in $\mathcal{W}_{0}$ arises as the limit of a convergent graph sequence. Furthermore, the limit is unique up to isomorphism.

For every graph $G$, we define a function $W_{G}\in\mathcal{W}_{0}$ as follows. Let $V(G)=\{1,\dots,n\}$ and consider a point $(x,y)\in^{2}$. Define integers $i$ and $j$ such that $x\in((i-1)/n,i/n]$ and $y\in((j-1)/n,j/n]$ (if $x=0$ we define $i=0$, and similarly for $j$). Then we set

(informally, we consider the adjacency matrix $A=(a_{ij})$ of $G$, and replace each entry $a_{ij}$ by a square of size $(1/n)\times(1/n)$ with the constant function $a_{ij}$ on this square). Note that $W_{G}$ depends on the labeling of the nodes of $G$ (but only up to a measure preserving transformation).

3 Distances of graphs and functions

As mentioned in the introduction, our results concern the interaction of two distances between graphs, the edit distance and the cut distance. Let $G_{1}$ and $G_{2}$ be two graphs with a common node set $V$. Instead of the edit distance mentioned in the introduction, we shall use its normalized version

(here $e_{G_{1}}(S,T)$ denotes the number of edges of $G$ with one endpoint in $S$ and the other endpoint in $T$).

We consider on $\mathcal{W}$ the cut norm

where the supremum is taken over all measurable subsets $S$ and $T$. (See for several useful properties of this norm.) We will also use the standard $L_{1}$ norm

This defines two metrics on $\mathcal{W}_{0}$ by

For every set $S\subseteq\mathcal{W}_{0}$ and every $c>0$, we define, as usual, the balls

Clearly $d_{\square}\leq d_{1}$, and hence $B_{1}(S,c)\subseteq B_{\square}(S,c)$. So $d_{\square}$ is continuous with respect to $d_{1}$. In general, $d_{1}$ is not continuous w.r.t. $d_{\square}$, but see Theorem 3.4 for a weaker statement.

For $W\in\mathcal{W}_{0}$ and $\phi:~\to$, set $W^{\phi}(x,y)=W(\phi(x),\phi(y))$. We define

where $\phi$ ranges over all invertible measure preserving maps from $$to$$. This is a quasimetric on $\mathcal{W}_{0}$, in which $U$ and $W$ are distance $0$ if and only if they are isomorphic. The metric $\delta_{\square}(U,W)$ is defined analogously.

The main advantage of $\delta_{\square}$ over $d_{\square}$ is that the space $(W,\delta_{\square})$ is compact, as was proved in .

We can use this distance to define yet another distance between graphs:

Note that in this definition the graphs $G_{1}$ and $G_{2}$ do not need to have the same number of nodes, and their distance is independent of the labeling of their nodes. If it happens that $V(G_{1})=V(G_{2})$, then clearly

The paper contains a more explicit description of this distance, and its relation to combinatorially defined distances. One of the main conclusions is that a sequence of graphs is convergent if and only if it is Cauchy in this metric. So $(\mathcal{W}_{0},\delta_{\square})$ is the completion of the set of graphs with distance $\delta_{\square}$.

We summarize some further facts about homomorphism densities and distances, mostly from . Let $F$ be a graph with $k$ nodes and $m$ edges. For every graph $G$, we have

but for the “induced” versions we only have the following approximate equality:

Lemma 4.1 in asserts that for any two functions $U,W\in\mathcal{W}_{0}$,

This implies (via the functions $W_{G}$ and $W_{H}$) a similar inequality for any two graphs $G$ and $H$:

An analogue of inequality (2) for induced densities in functions can be proved by essentially the same argument:

Using the easy inequality (1), this implies for the induced densities in graphs that

(assuming that $|V(G)|,|V(H)|>\binom{k}{2}$.

The following result from (Theorem 4.10) provides a converse to (2):

Let $U,W\in\mathcal{W}_{0}$ and let $k>1$ be a positive integer. Assume that for every simple graph $F$ on $k$ nodes, we have

We conclude with a lemma showing that convergence in the cut norm has good analytic properties.

Suppose that $\|W_{n}-W\|_{\square}\to 0$ as $n\to\infty$ ($W,W_{n}\in\mathcal{W}_{0}$). Then for every $Z\in\mathcal{W}_{0}$

for every measurable set $S\subseteq^{2}$.

If $Z$ is the indicator function of a rectangle, these conclusions follow from the definition of the $\|.\|_{\square}$ norm. Hence the conclusion follows for stepfunctions, since they are linear combinations of a finite number of indicator functions of rectangles. Then it follows for all integrable functions, since they are approximable in $L_{1}(^{2})$ by stepfunctions. ∎

4 WW-random graphs

Let $W\in\mathcal{W}_{0}$ and let $F$ be a graph with $k$ nodes. Then for every $0<\varepsilon<1$,

The following bound on the distance of a $W$-random graph from $W$ was proved in (Theorem 4.9(ii)):

Let $U\in\mathcal{W}_{0}$ and let $k>1$ be a positive integer. Then with probability at least $1-e^{-k^{2}/(2\log k)}$, we have

Summing this over all graphs $F$ on $k$ nodes, we get

for all graphs $F$ with at most $k$ nodes. Theorem 2.1 implies that in this case

So if we choose $k=\lfloor\sqrt{\log(n/2)}/4\rfloor$, then

Combining with (8), we get that with probability more than $1-1/\sqrt{n}$,

For the first formula, note that for $1\leq i,j\leq n$, the probability that a pair $i\not=j$ contributes to $d_{1}(H,G^{\prime})$ is

Summing over all $i\not=j$, and taking expectation, the equality follows. The second inequality is an easy consequence:

As a useful consequence, we obtain the following fact. The Regularity Lemma implies (see e.g. ) that functions in $\mathcal{W}_{0}$ can be approximated by functions of the form $W_{G}$, so that the number of nodes of $G$ can be bounded uniformly if the error is measured in the cut distance. Obviously, one cannot approximate all functions by functions $W_{G}$ in the $L_{1}$-norm. But for every $n$ there is graph on $n$ nodes that approximates $W$ so that the cut distance tends to $0$ uniformly, and at the same time the approximation in the $L_{1}$ norm is almost as good as possible.

Let $G$ be a simple graph and $U\in\mathcal{W}_{0}$. Then there exists a simple graph $G^{\prime}$ such that

On the other hand, Lemma 2.5 implies that with probability at least $3/4$, we have

So with positive probability, both (7) and (8) hold. ∎

5 Relating different norms

As pointed out in the introduction, the analytic problem behind property testing is to relate the cut norm and the $L_{1}$ norm. In this section, which contains our main technical tools, we study this connection. Some of the lemmas below are purely analytic in nature, and may be of interest on their own right.

Suppose that $\|U_{n}-U\|_{\square}\to 0$ and $\|W_{n}-W\|_{\square}\to 0$ as $n\to\infty$ ($U,W,U_{n},W_{n}\in\mathcal{W}_{0}$). Then

Let $\sigma(x,y)=\hbox{\rm sgn}(U(x,y)-W(x,u))$. Then

Suppose that $\|U_{n}-U\|_{\square}\to 0$ and $\|W_{n}-W\|_{\square}\to 0$ as $n\to\infty$ ($U,W,U_{n},W_{n}\in\mathcal{W}_{0}$). Suppose further that $U$ is $0-1$ valued. Then

Combined with Lemma 2.8, the assertion follows. ∎

Suppose that $\|U_{n}-U\|_{\square}\to 0$ as $n\to\infty$ ($U,U_{n}\in\mathcal{W}_{0}$). Then for every $W\in\mathcal{W}_{0}$ there is a sequence of functions $W_{n}\in\mathcal{W}_{0}$ such that $\|W_{n}-W\|_{\square}\to 0$ and

First we consider the case when $U\geq W$. Let

and $W_{n}=ZU_{n}$. Trivially $W_{n}\in\mathcal{W}_{0}$, $W=ZU$, and

(using Lemma 2.2 again). Combining this with Lemma 2.8 we get that $\|U_{n}-W_{n}\|_{1}\to\|U-W\|_{1}$.

The case when $U\leq W$ follows by a similar argument, replacing $U,W,\dots$ by $1-U,1-W,\dots$.

Finally, in the general case, consider the function $V=\max(U,W)$. Then clearly $\|U-V\|_{1}+\|V-W\|_{1}=\|U-W\|_{1}$. Since $U\leq V$, there exists a sequence $(V_{n})$ of functions such that $\|V_{n}-V\|_{\square}\to 0$ and $\|V_{n}-U_{n}\|_{1}\to\|V-U\|_{1}$. Since $V\geq W$, there is a sequence $(W_{n})$ of functions such that $\|W_{n}-W\|_{\square}\to 0$ and $\|W_{n}-V_{n}\|_{1}\to\|W-V\|_{1}$. Hence

Using Lemma 2.8 again, the lemma follows. ∎

A fact similar to Lemma 2.8 holds for the distances $\delta_{1}$ and $\delta_{\square}$ replacing the norms $\|.\|_{1}$ and $\|.\|_{\square}$. This does not seem to follow directly from Lemma 2.8, and the proof is more involved.

Suppose that $\delta_{\square}(U_{n},U)\to 0$ and $\delta_{\square}(W_{n},W)\to 0$ as $n\to\infty$ $(U,W,U_{n},W_{n}\in\mathcal{W}_{0})$. Then

Let $d$ denote the lim inf on the left hand side of (9). Let $\varepsilon$ be an arbitrary positive number. There is a number $k$ (depending on $U$, $W$ and $\varepsilon$), a partition $=\cup_{i=1}^{k}S_{i}$ of the unit interval into $k$ measurable pieces and two functions $W^{\prime},U^{\prime}\in\mathcal{W}_{0}$ such that both $W^{\prime}$ and $U^{\prime}$ are constant on every rectangle $S_{i}\times S_{j}$ and furthermore that $\|W-W^{\prime}\|_{1},~\|U-U^{\prime}\|_{1}\leq\varepsilon$. Let $n$ be a natural number such that $\|W_{n}-W\|_{\square}~,~\|U_{n}-U\|_{\square}\leq\varepsilon/k^{4}$ and $\delta_{1}(W_{n},U_{n})\leq d+\varepsilon$. There are measure preserving transformations $\rho,\pi:\mapsto$ such that $\|W_{n}^{\rho}-U_{n}^{\pi}\|_{1}\leq d+2\varepsilon$. Let $S_{i,j}$ denote the set $S_{i}^{\rho}\cap S_{j}^{\pi}$ for every $1\leq i,j\leq k$. It is clear that $S_{i,j}$ is a partition of the unit interval and that both ${W^{\prime}}^{\rho}$ and ${U^{\prime}}^{\pi}$ are constant on each rectangle $S_{i_{1},j_{1}}\times S_{i_{2},j_{2}}$. We have that

Writing $W^{\rho}-U^{\pi}=(W^{\rho}-{W^{\prime}}^{\rho})+({W^{\prime}}^{\rho}-U^{\prime\pi})+(U^{\prime\pi}-U^{\pi})$ we obtain that

Using that both ${W^{\prime}}^{\rho}$ and ${U^{\prime}}^{\pi}$ are constant on the sets $S_{i_{1},j_{1}}\times S_{i_{2},j_{2}}$ we obtain that the right side of the above inequality is equal to $\|{W^{\prime}}^{\rho}-{U^{\prime}}^{\pi}\|_{1}-2\varepsilon$. Consequently

Using that $\|W^{\rho}-{W^{\prime}}^{\rho}\|_{1},~\|U^{\pi}-{U^{\prime}}^{\pi}\|_{1}\leq\varepsilon$ we get that

Since $\varepsilon>0$ is arbitrary, (9) follows. ∎

Main results

We define a notion of testability for properties of functions in $\mathcal{W}_{0}$ and for graphons. Formally, a function property is a subset $\mathcal{R}\subseteq\mathcal{W}_{0}$; a graphon property is a function property that is invariant under isomorphism. A function property is closed if it is closed in the $\|.\|_{\square}$ norm.

The function property of being 0-1 valued is a graphon property by the characterization of isomorphism, but it is not closed, since for a sequence of random graphs $G_{n}$ with edge probability $1/2$, the functions $W_{G_{n}}$ are 0-1 valued, but their limit in the $\|.\|_{\square}$ norm, namely the identically $1/2$ function, is not.

A function property $\mathcal{R}$ is testable if there is a graph property $\mathcal{R}^{\prime}$ (called a test property for $\mathcal{R}$) such that

Similarly as for graph properties, the constants $1/3$ and $2/3$ are arbitrary, but it would not change the property if we replaced them by any two real numbers $0<a<b<1$:

Let $0<a<b<1$. A graphon property $\mathcal{R}$ is testable if and only if there is a graph property $\mathcal{R}^{\prime\prime}$ such that for every $\varepsilon>0$ there is a constant $k(\varepsilon)$ such that for every function $W\in\mathcal{W}_{0}$ and $k\geq k(\varepsilon)$,

Suppose that $\mathcal{R}$ is testable, and let $\mathcal{R}^{\prime}$ be the graph property in the definition of testability. For every simple graph $F$ and $k\leq|V(F)|$, define

Let $W\in\mathcal{R}$ and let $n>k$ be large enough. Then

Choosing $n$ large enough, this probability will be less than $1-b$, and hence

So (a) is satisfied. The proof of (b) is analogous, and so is the proof of the converse. ∎

It follows from the definition that a graphon property is testable if and only if its closure in the $\|.\|_{1}$ norm is testable. Furthermore, the closure in the $\|.\|_{\square}$ norm of a testable property is testable (but not the other way around, see example 3.6(d) below). It follows from Theorem 3.4 below (but it is not hard to see directly too) that if $\mathcal{R}$ is testable, then its closures in the $\|.\|_{1}$ norm and $\|.\|_{\square}$ norm coincide.

It is trivial that $B_{1}(\mathcal{R},\varepsilon)\subseteq B_{\square}(\mathcal{R},\varepsilon)$ for every $\mathcal{R}\subseteq\mathcal{W}$ and $\varepsilon>0$. A reverse containment characterizes testable graphon properties.

A graphon property $\mathcal{R}$ is testable if and only if for every $\varepsilon>0$ there is an $\varepsilon^{\prime}>0$ such that $B_{\square}(\mathcal{R},\varepsilon^{\prime})\subseteq B_{1}(\mathcal{R},\varepsilon)$.

Suppose that $\mathcal{R}$ is testable with test property $\mathcal{R}^{\prime}$. Let $\varepsilon>0$, let $k=k(\varepsilon)$ be the constant in the definition, and let $\varepsilon^{\prime}=2^{-k^{2}}$. Suppose that for some $W\in\mathcal{W}_{0}$, we have $d_{\square}(W,\mathcal{R})<\varepsilon^{\prime}$. Then there is a $U\in\mathcal{R}$ such that $d_{\square}(W,U)<\varepsilon^{\prime}$. By (4), we have for every graph $F$ on $k$ nodes

Conversely, suppose that $\mathcal{R}$ satisfies the condition in the proposition. Choose

Let $\mathcal{R}^{\prime}$ be the graph property that a graph $G$ with $|V(G)|=n$ has if and only if there exists a $U\in\mathcal{R}$ such that $|t(F,U)-t(F,G)|\leq\varepsilon_{n}$ for all graphs $F$ with $|V(F)|\leq k_{n}$. We show that (a) and (b) are satisfied.

Second, let $\varepsilon>0$ and suppose that $d_{1}(W,\mathcal{R})>\varepsilon$. By hypothesis, there is an $\varepsilon^{\prime}>0$ (depending only on $\varepsilon$) such that $d_{\square}(W,\mathcal{R})>\varepsilon^{\prime}$.

for all graphs $F$ with at most $k_{n}$ nodes. Similarly as above, Theorem 2.5 in implies that

for all graphs $F$ with at most $k_{n}$ nodes. By Theorem 3.6 in , it follows that

If $n$ is large enough, this is less that $\varepsilon^{\prime}$, contradicting the definition of $\varepsilon^{\prime}$. ∎

We also prove the following characterization, which is a functional analogue of the characterization of Alon, Fischer, Newman and Shapira .

A graphon property $\mathcal{R}$ is testable if and only if for every $\varepsilon>0$ there is an $\varepsilon^{\prime}>0$ and a finite set $S$ of stepfunctions such that $\mathcal{R}\subseteq B_{\square}(S,\varepsilon^{\prime})\subseteq B_{1}(\mathcal{R},\varepsilon)$.

This theorem gives a “constructive” method of testing a testable graphon property: for every fixed error bound, it suffices to compute the $d_{\square}$ distance from a finite number of stepfunctions to separate the case when $W\in\mathcal{R}$ from the case when $d_{1}(W,\mathcal{R})\geq\varepsilon$.

First, suppose that $\mathcal{R}$ is testable, and let $\varepsilon>0$. By Theorem 3.4, there is an $\varepsilon^{\prime}>0$ such that $B_{\square}(\mathcal{R},2\varepsilon^{\prime})\subseteq B_{1}(\mathcal{R},\varepsilon)$. For every stepfunction $s$, consider the open ball $B_{\square}(s,\varepsilon^{\prime})$. These balls cover the whole space, so by the compactness of $(\mathcal{W},\delta_{\square})$ there is a finite set $S_{0}$ of stepfunctions such that the corresponding balls cover the whole space. Let $S$ be the set of those stepfunctions in $S_{0}$ for which the corresponding balls intersect $\mathcal{R}$. Then clearly $\mathcal{R}\subseteq B_{\square}(S,\varepsilon^{\prime})$. On the other hand, $B_{\square}(U,\varepsilon^{\prime})$ intersects $\mathcal{R}$ for every $U\in S$, and hence $B_{\square}(S,\varepsilon^{\prime})\subseteq B_{\square}(\mathcal{R},2\varepsilon^{\prime})\subseteq B_{1}(\mathcal{R},\varepsilon)$.

Second, suppose that $\mathcal{R}$ satisfies the condition in the theorem, then for every $\varepsilon>0$ there exists an $\varepsilon^{\prime}>0$ and a finite set $S$ of stepfunctions such that $\mathcal{R}\subseteq B_{\square}(S,\varepsilon^{\prime})\subseteq B_{1}(\mathcal{R},\varepsilon/2)$. Let $\varepsilon^{\prime\prime}=\varepsilon\varepsilon^{\prime}/6$. We claim that

Indeed, let $W\in B_{\square}(\mathcal{S},\varepsilon^{\prime}+\varepsilon^{\prime\prime})$. Then there is a $U\in\mathcal{S}$ such that $\|U-W\|_{\square}<\varepsilon^{\prime}+2\varepsilon^{\prime\prime}$. Consider $Y=(1-\frac{1}{3}\varepsilon)W+\frac{1}{3}\varepsilon U$. Then

so $Y\in B_{\square}(S,\varepsilon^{\prime})$. On the other hand,

and so $W\in B_{1}(B_{\square}(S,\varepsilon^{\prime}),\varepsilon/2)$. This proves (12), which in turn implies that

This proves that $\mathcal{R}$ is testable. ∎

We conclude this section with some examples of testable and non-testable function properties.

On the other hand, the complementary property $\mathcal{R}^{c}=\mathcal{W}_{0}\setminus\{U\}$ is testable; indeed, its closure is $\mathcal{W}_{0}$ (either in the $\|.\|_{\square}$ norm or the $\|.\|_{1}$ norm), which is trivially testable.

(b) Let $\mathcal{S}\subseteq\mathcal{W}_{0}$ be an arbitrary graphon property and let $a>0$ be an arbitrary number. Then $\mathcal{R}=B_{\square}(\mathcal{S},a)$ is testable.

Indeed, for $\varepsilon>0$ define $\varepsilon^{\prime}=a\varepsilon/(2-2\varepsilon)$. Let $W\in B_{\square}(\mathcal{R},\varepsilon^{\prime})$. Then $W\in B_{\square}(\mathcal{S},a+\varepsilon^{\prime})$, and so there is a $U\in\mathcal{S}$ such that $\|U-W\|_{\square}\leq a+2\varepsilon^{\prime}$. Consider $Y=(1-\varepsilon)W+\varepsilon U$. Then $\|Y-U\|_{\square}=\|(1-\varepsilon)(U-W)\|_{\square}\leq(1-\varepsilon)(a+2\varepsilon^{\prime})=a$, so $Y\in\mathcal{R}$. On the other hand, $\|W-Y\|_{1}=\|\varepsilon(W-U)\|_{1}\leq\varepsilon$, and so $W\in B_{1}(\mathcal{R},\varepsilon)$.

(c) For every fixed graph $F$ and $0<c<1$, the property $\mathcal{R}$ that $t(F,W)=c$ is testable; an appropriate test property is

Indeed, it follows from Theorem 2.3 that with probability $1-o(1)$,

Fixing two subgraph densities, however, may yield a non-testable property: for example, $t(K_{2},W)=1/2$ and $t(C_{4},W)=1/16$ imply that $W\equiv 1/2$ (see ).

(d) The graphon property that $W$ is 0-1 valued is not testable. It is closed in the $\|.\|_{1}$ norm, but its closure in the $\|.\|_{\square}$ norm is the whole set $\mathcal{W}_{0}$.

2 Graph properties vs. function properties

We want to establish the connection between testability of graph properties and graphon properties. The fact that graphons arise as limits of graph sequences suggests the following definition.

If $\mathcal{P}$ is a graph property, then we define its closure $\overline{\mathcal{P}}$ as the set of all functions $W\in\mathcal{W}_{0}$ for which there exists a sequence of graphs $G_{n}\in\mathcal{P}$ with $|V(G_{n})|\to\infty$ such that $G_{n}\to W$ (i.e., $W_{G_{n}}$ converges to $W$ in the $\delta_{\square}$ metric).

Clearly $\overline{\mathcal{P}}$ is closed under isomorphism, i.e. it is a graphon property. The following examples show that $\overline{\mathcal{P}}$ is not necessarily an “extension” of $\mathcal{P}$ in the sense that $\mathcal{P}$ cannot be recovered from it. Intuitively, $\overline{\mathcal{P}}$ is a nice object which is a “clean” version of $\mathcal{P}$; it is an analytic profile of the property $\mathcal{P}$, which eliminates all uncontrollable noise from it.

(a) Let $\mathcal{P}$ be the graph property that the graph doesn’t have a 4-cycle. Then only the $0$ function has property $\overline{\mathcal{P}}$. In fact, graphs without $4$-cycles are sparse and property testing (in the sense of Definition 1.1) does not distinguish sparse graphs from each other.

(b) Let $\mathcal{P}$ be the graph property that the graph has an even number of edges. Rather counter-intuitively, this property is testable according to Definition 1.1 above, and its closure is the whole set $\mathcal{W}_{0}$.

(c) Let $\mathcal{P}$ be the graph property that the graph has an even number of nodes. This property is not testable, since adding a single node to a large graph changes the distribution of small induced subgraphs by very little, but changes the property. The closure of this property is again the whole set $\mathcal{W}_{0}$ (which is testable).

(d) Quasirandomness is defined as a property of a sequence of graphs, but we can make it a graph property $\mathcal{Q}$ (at the cost of a somewhat arbitrary choice of the error bound) as follows: a graph $G$ on $n$ nodes is quasirandom, if

The closure $\overline{\mathcal{Q}}$ of this property consists of only one function, the identically $1/2$ function. This singleton set of functions is not testable, since for any sequence $(G_{n})$ of quasirandom graphs, $\|W_{G_{n}}-\frac{1}{2}\|_{\square}\to 0$ but $\|W_{G_{n}}-\frac{1}{2}\|_{1}=1/2$. This implies (by Theorem 3.18 below) that quasirandomness is not a testable property.

The first part of the following fact was stated in .

(a) The closure of a hereditary graph property $\mathcal{P}$ consists of those functions $W\in\mathcal{W}_{0}$ for which

for every $k$. Equivalently, $t_{\rm ind}(F,W)=0$ whenever $F\notin\mathcal{P}$.

(b) The closure of a testable graph property $\mathcal{P}$ consists of those functions $W\in\mathcal{W}_{0}$ for which

It follows from Theorem 3.5 that in the last formula, we could replace $d_{1}$ by $d_{\square}$.

To show the converse, assume that $W\in\overline{\mathcal{P}}$, and let $(G_{n})$ be a sequence of graphs such that $G_{n}\in\mathcal{P}$ and $G_{n}\to W$. We can write

so it suffices to prove that $t_{\rm ind}(F,W)=0$ for $F\notin\mathcal{P}$. By (1), we have

for every $F\in\mathcal{F}_{k}$. For $F\in\mathcal{F}_{k}\setminus\mathcal{P}$, we have $t_{\rm ind}(F,G_{n})=0$ since $G_{n}\in\mathcal{P}$ and the property is hereditary. Hence by (15), in this case

If $\mathcal{P}$ is a hereditary graph property, then $W\in\overline{\mathcal{P}}$ depends only on the support of $W$.

We conclude with two lemmas on testability. We’ll say more about both (Theorems 3.20 and 3.18), but these simple lemmas will be needed before that.

Let $\mathcal{P}$ be a testable graph property. Then for every $\varepsilon>0$ there is an $\varepsilon^{\prime}>0$ and a positive integer $n^{\prime}$ such that if $G$ are two graphs with $G^{\prime}\in\mathcal{P}$, $\delta_{\square}(G,G^{\prime})<\varepsilon^{\prime}$ and $|V(G)|,|V(G^{\prime})|\geq n^{\prime}$, then $d_{1}(G,\mathcal{P})<\varepsilon$.

Let $\varepsilon>0$ and let $k=k(\varepsilon)$ in the definition of testability. We show that $n^{\prime}=9k^{2}$ and $\varepsilon^{\prime}=1/k^{2}$ is a good choice. Since $G^{\prime}$ has property $\mathcal{P}$, we have that at least $2/3$ of its $k$-node induced subgraphs have property $\mathcal{P}^{\prime}$. It follows by (5) that more than $1/3$ of the $k$-node subgraphs of $G$ have the property $\mathcal{P}^{\prime}$. Hence $d_{1}(G,\mathcal{P})<\varepsilon$ by testability. ∎

If $\mathcal{P}$ is testable then $\overline{\mathcal{P}}$ is testable.

The converse is not true in general, but in Theorem 3.18 we will give a characterization of testable properties in terms of their closure.

It suffices to prove that if $(W_{n})$ is a sequence of functions in $\mathcal{W}_{0}$ such that $d_{\square}(W_{n},\overline{\mathcal{P}})\to 0$, then $d_{1}(W_{n},\overline{\mathcal{P}})\to 0$. We may assume that the sequence $W_{n}$ is convergent, so $W_{n}\to U$ for some $U\in\mathcal{W}_{0}$ (in the $\delta_{\square}$ distance). Clearly $U\in\overline{\mathcal{P}}$, so by the definition of closure, there are graphs $H_{n}\in\mathcal{P}$ such that $|V(H_{n})|\to\infty$ and $H_{n}\to U$.

Fix any $\varepsilon>0$. By Lemma 3.11, there is an $\varepsilon^{\prime}>0$ such that if $|V(G)|,|V(H)|$ are large enough, $H\in\mathcal{P}$, and $\delta_{\square}(G,H)<\varepsilon^{\prime}$, then $d_{1}(G,\mathcal{P})<\varepsilon$. Furthermore, there is an $n_{\varepsilon}\geq 1$ such that if $n\geq n_{\varepsilon}$, then $\delta_{\square}(W_{H_{n}},U),\delta_{\square}(W_{n},U)\leq\varepsilon^{\prime}/3$.

Fix any $n\geq n_{\varepsilon}$, and let $G_{n,m}$ ($m=1,2,\dots$) be a sequence of graphs such that $|V(G_{n,m})|\to\infty$ and $G_{n,m}\to W_{n}$ as $m\to\infty$. Then

if $m$ is large enough, hence by the choice of $\varepsilon^{\prime}$, we have $d_{1}(G_{n,m},\mathcal{P})\leq\varepsilon$. This means that there are graphs $J_{n,m}\in\mathcal{P}$ with $V(J_{n,m})=V(G_{n,m})$ such that $d_{1}(G_{n,m},J_{n,m})\leq\varepsilon$. By choosing a subsequence, we can assume that $J_{n,m}\to U_{n}$ as $m\to\infty$ for some $U_{n}\in\overline{\mathcal{P}}$. Applying Lemma 2.11 we obtain that

2.2 Closure and distance

What is the relationship between the $d_{1}$ distance from a property and from its closure? The following propositions summarize what we know. We say that a graph $G^{\prime}$ is an equitable $m$-blowup of $G$ if it is obtained by replacing each node of $G$ by $m$ or $m+1$ twin copies ($m\geq 1$).

(a) For every hereditary graph property $\mathcal{P}$ and every graph $G$,

(b) For every testable graph property $\mathcal{P}$,

(c) Let $\mathcal{P}$ be an arbitrary graph property and let $G^{1},G^{2},\dots$ be all equitable blowups of a graph $G$. Then

Hence there is an instance of $G^{\prime}$ for which $G^{\prime}\in\mathcal{P}$ and $d_{1}(G,G^{\prime})\leq d_{1}(W_{G},\mathcal{P})+\delta$. Thus $d_{1}(G,\mathcal{P})\leq d_{1}(G,G^{\prime})\leq d_{1}(W_{G},\overline{\mathcal{P}})+\delta$. Since $\delta$ is arbitrary, this proves (a).

(b) Suppose not, then there exists a sequence of graphs $(G_{n})$ with $|V(G_{n})|\to\infty$ such that $d_{1}(G_{n},\mathcal{P})\to a$ and $d_{1}(W_{G_{n}},\overline{\mathcal{P}})\to b$, where $a\not=b$. We may assume that $V(G_{n})=[q_{n}]$, where $q_{n}\to\infty$.

First, select graphs $H_{n}\in\mathcal{P}$ such that $V(H_{n})=V(G_{n})$ and $d_{1}(G_{n},H_{n})=d(G_{n},\mathcal{P})$. By selecting a subsequence, we may assume that the sequence $H_{n}$ is convergent; let $U\in\mathcal{W}_{0}$ be its limit. Clearly $U\in\overline{\mathcal{P}}$. Then $\delta_{\square}(W_{H_{n}},\overline{\mathcal{P}})\leq\delta_{\square}(W_{H_{n}},U)\to 0$, and hence $d_{\square}(W_{H_{n}},\overline{\mathcal{P}})\to 0$. By Theorem 3.4, this implies that $d_{1}(W_{H_{n}},\overline{\mathcal{P}})\to 0$. But then in the inequality

the first term on the right hand side tends to $a$, while the second tends to $0$, showing that $b\leq a$.

Next we show that, with probability tending to $1$ as $n\to\infty$, we have

Indeed, the left hand side is the sum of $q_{n}/2$ independent random variables, all $0-1$ valued, so this follows by the Law of Large Numbers.

This implies that with probability at least $1/4$,

With positive probability, both (18) and (19) occur, and so by (16) we have

Sending $n\to\infty$ we see that $a\leq b+3\varepsilon$. Since $\varepsilon$ was arbitrary, it follows that $a\leq b$, which is a contradiction.

(c) Let $\varepsilon>0$, and let $U\in\overline{\mathcal{P}}$ be a function such that $\|W_{G}-U\|_{1}\leq d_{1}(W_{G},U)+\varepsilon$. Let $H_{n}$ be a sequence of graphs such that $H_{n}\to U$ and $H_{n}\in\mathcal{P}$. Then for an appropriate labeling of the nodes of $H_{n}$, we have $\|W_{H_{n}}-U\|_{\square}\to 0$. Since $W_{G}$ is $0-1$ valued, Lemma 2.9 implies that $\|W_{H_{n}}-W_{G}\|_{1}\to\|U-W_{G}\|_{1}$. Let $V(G)=\{1,\dots,k\}$ and $V(H_{n})=\{1,\dots,m\}$. Choose $n$ large enough so that $\|W_{H_{n}}-W_{G}\|_{1}\leq\|U-W_{G}\|_{1}+\varepsilon$ and $m\geq k/\varepsilon$.

Let $V_{i}=\bigl\{\lfloor(i-1)m/k\rfloor+1,\dots,\lfloor im/k\rfloor\bigr\}$ for $i=1,\dots,k$. Then $(V_{1},\dots,V_{k})$ is a partition of $V(H_{n})$ into $k$ almost equal classes. Define a graph $G^{\prime}$ on $\{1,\dots,k\}$ by connecting $u\in V_{i}$ to $v\in V_{j}$ if and only if $ij\in E(G)$. Then $G^{\prime}$ is an equitable blowup of $G$. Furthermore, $W_{G^{\prime}}$ and $W_{G}$ differ only on stripes of width less than $1/m$ along the orders of the squares on which $W_{G}$ is constant, so $\|W_{G^{\prime}}-W_{G}\|_{1}\leq 2k/m\leq 2\varepsilon$. Thus

Since $\varepsilon$ was arbitrary, this proves that

To prove the converse, let $a=\liminf d_{1}(G^{n},\mathcal{P})$, and let $H_{n}\in\mathcal{P}$ be chosen so that $V(H_{n})=V(G^{n})$ and $d_{1}(H_{n},G^{n})=d_{1}(G^{n},\mathcal{P})$. Select a subsequence such $d_{1}(H_{n}-G^{n})\to a$, and choose a further subsequence so that $H_{n}$ is convergent. Let $H_{n}\to U\in\overline{\mathcal{P}}$. We have $\delta_{\square}(W_{H_{n}},U)\to 0$ and $\delta_{\square}(W_{G^{n}},W_{G})\to 0$, hence by Lemma 2.11,

Hence $d_{1}(W_{G},\overline{\mathcal{P}})\leq\delta_{1}(W_{G},U)\leq a$. ∎

Let $\mathcal{P}$ be any graph property and $G_{n}\to W$, a convergent graph sequence. Then

Let $H_{n}\in\mathcal{P}$ be such that $V(G_{n})=V(H_{n})$ and $d_{1}(G_{n},H_{n})=d_{1}(G_{n},\mathcal{P})$. We may select a subsequence so that $H_{n}\to U$ for some $U\in\mathcal{W}_{0}$. Clearly $U\in\overline{\mathcal{P}}$. Furthermore, $\|W_{G_{n}}-W\|_{\square}\to 0$ and $\|W_{H_{n}}-U\|_{\square}\to 0$, so by Lemma 2.8, we have

2.3 Monotone closure

For two functions $U,W\in\mathcal{W}_{0}$ we write $U\preceq W$ if there exist functions $U^{\prime},W^{\prime}\in\mathcal{W}$ such that $U\cong U^{\prime}$, $W\cong W^{\prime}$, and $U^{\prime}\leq W^{\prime}$ almost everywhere.

Let $\mathcal{P}$ a graph property. By its upward closure we mean the graph property $\mathcal{P}^{\uparrow}$ consisting of those graphs that have a spanning subgraph in $\mathcal{P}$. For a function property $\mathcal{R}$, we define its upward closure to consist of those functions $W\in\mathcal{W}_{0}$ for which there exists a function $U\in\mathcal{R}$ such that $U\preceq W$. In both versions, the downward closure is defined analogously.

The following theorem, whose proof is surprisingly nontrivial, asserts that closure and upward closure commute.

First, let $W\in\overline{\mathcal{P}^{\uparrow}}$. Then there exists a graph sequence $G_{n}\to W\in\mathcal{W}_{0}$ such that $G_{n}$ has a spanning subgraph $G_{n}^{\prime}\in\mathcal{P}$. We consider the pair $(G_{n},G_{n}^{\prime})$ as the graph $G_{n}$ in which the edges of $G_{n}^{\prime}$ colored red, the remaining edges are colored blue. We may choose a subsequence of the indices so that the remaining sequence is convergent as 2-edge-colored graphs, meaning that for every 2-edge-colored simple graph $F$, the sequence of densities $t(F,G_{n})$ of the densities of color-preserving homomorphisms is convergent. It is shown in that the limit object of a such a sequence can be described by a pair of functions $U,V\in\mathcal{W}_{0}$, such that $V$ is the limit of the sequence $(G_{n})$, $U$ is the limit of the sequence $(G_{n}^{\prime})$, and $U\leq V$ almost everywhere. Hence $V\cong W$ and $U\in\overline{\mathcal{P}}$. This proves that $W\in(\overline{\mathcal{P}})^{\uparrow}$.