for every connected component $X$ which has not been altered. We define $f'(v):=f_X(v)$ for $v\in X$. By construction $f'$ is obviously an embedding of $F$ into $H$.
Since $H\in \mathcal{P}_n$ this yields a contradiction.
Hence the existence of $H'$ contradicts the assumption that $(\ast)>0$ which implies that $H$ has the claimed properties.

First observe that $n\geq 8k^3$ allows us to chose  $a_i$ and $b_j$ for every $i\in I$ and $j\in J$ in such a way that $k\leq a_i \leq p_i(G[S])$, $k\leq b_j \leq c_j(G[S])$
and $\sum_{i\in I}i\cdot a_i+\sum_{j\in J}j\cdot b_j\leq  n-k^3$. Amongst all such choices we pick $a_i$ and $b_j$ such that
$\sum_{i\in I}i\cdot a_i+\sum_{j\in J}j\cdot b_j$ is maximum.
Let $M$ be a set of vertices containing all connected components of $G$ apart from  $a_i$
paths and $b_j$ cycles from $G[S]$ for every $i\in I$, $j\in J$. Then $|M|\leq  2k|B|+|B|+4k^3$
since $M$ consists of $N_k^G(B)$ (at most $2k|B|+|B|$ vertices), all vertices in a connected
component which is either a path of length $i$ for $i\notin I$ or a cycle of length $j$ for
$j\notin J$ (since there are at most $2k^2$ such paths and cycles (as argued in Case 1) and each contains at most $k$ vertices)
or in case $a_i\not= p_i(G)$ or $b_j\not=c_j(G)$ for some $i\in I$,
$j\in J$, $M$ consist of at most $k^3+k$ vertices as we picked $a_i$, $b_j$ to maximise
$\sum_{i\in I}i\cdot a_i+\sum_{j\in J}j\cdot b_j$.

Now we use Claim <ref> and obtain an $\mathcal{F}_n'$-free graph $H\in \mathcal{P}_n$ such that $p_i(H)\geq a_i$ and $c_j(H)\geq b_j$. Hence we can modify $G$ into a graph $G'$ which is isomorphic to $H$ by only modifying $G[M]$. Since we can modify $G[M]$ into any graph with no more than $4k|B|+2|B|+8k^3\leq 16 k^3|B|$ modifications we showed that $G$ is $\tau(|B|/n)$-close to having $\mathcal{P}$.

§ TESTING PROPERTIES OF NEIGHBOURHOODS

In this section we only consider simple graphs, undirected graphs without self-loops and without parallel edges, and  for any  $d\in \mathbb{N}$ let $\mathcal{C}_d$  be the class of simple graphs of bounded degree $d$.
We view simple graphs as structures over the signature $\sigma_{\operatorname{graph}}:=\{E\}$, where $E$ encodes a binary, symmetric and irreflexive relation. This allows transferring the notions from Section <ref> to graphs.

Let $r\geq 1$ and let $\tau$ be an $r$-type and let $\varphi_{\tau}(x)$ be a FO formula saying that $x$ has $r$-type $\tau$.
We say that a graph $G$ is $\tau$-neighbourhood regular, if $G\models \forall x\varphi_{\tau}(x)$. We say that a graph $G$ is $\tau$-neighbourhood free, if $G \models \lnot \exists x \varphi_{\tau}(x)$. Let $\tau_1,\dots,\tau_t$ be a list of all $r$-types in $\mathcal{C}_d$. If $F\subseteq \{\tau_1,\dots,\tau_t\}$ we say that $G$ is $F$-free, if $G$ is $\tau$-neighbourhood free for all $\tau\in F$.

Observe that both  $\tau$-neighbourhood-freeness and $\tau$-neighbourhood regularity can be defined by formulas in $\Pi_2$ for any neighbourhood type $\tau$. Hence the next Lemma shows that there exist neighbourhood properties that are in $\Pi_2$, but not in $\Sigma_2$.

There exist $1$-types $\tau,\tau'$ such that neither $\tau$-neighbourhood freeness nor $\tau'$-neighbourhood regularity can be defined by a formula in $\Sigma_2$.

Note that the above lemma implies that we cannot simply invoke the testers for testing $\Sigma_2$ properties from Theorem <ref> to test these two properties.

For $n\in \mathbb{N}$, let $C_n$ be the cycle graph with vertex set $[n]:=\{0,1,\dots,n-1\}$.
Let $P_{n-1}$ be the path graph with vertex set $[n-1]$. We first show the following claim.

Let $\varphi= \exists \overline{x}\forall \overline{y} \chi(\overline{x},\overline{y})$ where $\overline{x}=(x_1,\dots,x_k)$, $\overline{y}=(y_1,\dots,y_\ell)$ are tuples of variables and $\chi(\overline{x},\overline{y})$ is a quantifier-free formula. If $C_n\models \varphi$ then  $P_{n-1}\models \varphi$ for any $n>k$.

Assume on the contrary that for some $n>k$,
it holds that $C_n \models \varphi$, while $P_{n-1}\not\models \varphi$. Since $C_n\models \varphi$ there are $k$ vertices $v_1,\dots,v_k$ in $C_n$ such that $C_n\models \forall \overline{y} \chi((v_1,\dots,v_k),\overline{y})$. Since $n>k$, there exists at least one vertex $i\in [n]$ that is not amongst $v_1,\dots,v_k$. Let $v_j':= (v_j+n-1-i)\mod n$ be a vertex of $P_{n-1}$. Since $P_{n-1}\not\models \varphi$ and $v_j'\in [n-1]$, we have that $P_{n-1}\not\models \forall \overline{y}\chi((v_1'\dots,v_k'),\overline{y})$. Hence there must be vertices $w_1',\dots,w_\ell'$ in $P_{n-1}$ such that $P_{n-1}\not\models \chi((v_1',\dots,v_k'),(w_1',\dots,w_\ell'))$. Now let $w_j:=(w_j'+i+1)\mod n$. Then $v_j\mapsto v_j'$ and $w_j\mapsto w_j'$ defines an isomorphism from $C_n[\{v_1,\dots,v_k,w_1,\dots,w_\ell\}]$ and $P_{n-1}[\{v_1',\dots,v_k',w_1',\dots,w_\ell'\}]$. Hence $C_n\not \models \chi((v_1,\dots,v_k),(w_1,\dots,w_\ell))$ which contradicts that $C_n\models \varphi$.

Now we let $\tau$ be the $1$-neighbourhood type saying that the center vertex $x$ has exactly one neighbour. Let $\tau'$ be the $1$-neighbourhood type saying that the center vertex has two non-adjacent vertices. Since $C_n$ is $\tau$-neighbourhood free and $\tau'$-neighbourhood regular, while $P_{n-1}$ is neither, the statement of the lemma follows from Claim <ref>.

Now we state our main algorithmic results in this section. The first result shows that if $\tau$ is an $r$-type with degree smaller than the degree bound of the class of graphs, then the $\tau$-neighbourhood-freeness is testable.

Let $\tau$ be an $r$-type, where $r\geq 1$. If $\tau \subseteq \mathcal{C}_{d'}$ and $d'<d$, then $\tau$-neighbourhood freeness is uniformly testable on the class $\mathcal{C}_{d}$ with constant running time.

The second result shows if $\tau$ is a $1$-type, then $\tau$-neighbourhood-freeness is testable.

For every $1$-type $\tau$, $\tau$-neighbourhood freeness is uniformly testable on the class $\mathcal{C}_{d}$ with constant time.

The third result says that $\tau$-neighbourhood regularity is testable for every $1$-type $\tau$ consisting of cliques, which only overlap in the centre vertex.

Let $\tau$ be a $1$-type such that  vertex $a$ having $1$-type $\tau$ in $B$  implies that $B\setminus \{a\}$ is a union of disjoint cliques for every $1$-ball $B$ with centre $a$. Then $\tau$-neighbourhood regularity is uniformly testable on $\mathcal{C}_{d}$ in
constant time.

By previous discussions, the above theorems imply that there are formulas in $\Pi_2\setminus\Sigma_2$ which are testable.

§.§ Proofs of Theorem <ref>, <ref> and <ref>

Consider the following algorithm $\sampler_{r,s}$: given access to a graph $G\in \mathcal{C}_{d}$,
it samples a set $S$ of $s$ vertices of $G$ uniformly and independently, and then explores their $r$-balls; it then returns
the distribution vector $\bar v$ of length $t$ of the $r$-types of this sample, $\bar v_i=|\{v\in S\mid \mathcal{N}_r^G(v)\in \tau_i\}|/s$.

Let $\lambda\in (0,1]$, $r\in \mathbb{N}$ and let $G\in \mathcal{C}_{d}$ be a graph with $n$ vertices.
Let $s\geq ({t^2}/{\lambda^2})\ln(t+40)$.
Then the vector $\bar v$ returned
by $\sampler_{r,s}(G)$ satisfies
$\sum_{i=1}^{t}|\rho_{G,r}(\{\tau_i\})-\bar v_i|  \leq \lambda$  with probability at least $19/20$ .

If  $\rho_{G,r}({\tau_i})$ is $0$, then $\Pr[v_i=0]=1$.

The following Lemma provides a framework that will be used in Theorems <ref>,<ref> and <ref>.

Let $\F$
be a finite set of $r$-types of bounded maximum degree $d$ and let
$\mathcal{P}\subseteq \mathcal{C}_{d}$ be the set of all graphs being $\F$-free.
$M\subseteq \mathbb{N}$  be a decidable set such that
$G\in \mathcal{P}$ implies that $|V(G)|\notin M$. Let $f_M:\mathbb{N}\rightarrow \mathbb{N}$
be a function such that $M$ can be decided in time $f_M$. Assume for every
$\epsilon\in (0,1]$ there exist $\lambda:=\lambda(\epsilon) \in (0,1]$ and
$n_0:=n_0(r,\epsilon)\in \mathbb{N}$  such that every graph $G\in \mathcal{C}_{d}$ on $n\geq
n_0$, $n\notin M$ vertices, which is $\epsilon$-far from $\mathcal{P}$, contains
more than $\lambda n$ elements $v$ with
$\mathcal{N}_r^G(v)\in \tau\in \F$. Then $\mathcal{P}$ is uniformly
testable on $\mathcal{C}_{d}$ in time $\mathcal{O}(f_M)$.

Consider the following probabilistic algorithm  $T$, which is given direct access to a graph $G\in \mathcal{C}_{d}$ and gets the number of vertices $n$ as input.  Let $s=({t^2}/{\lambda^2})\ln(t+40)$.

* Reject if $n\in M$.

* If $n < n_0$: use a precomputed table to decide exactly if $G\in \mathcal{P}$.

* Otherwise run $\sampler_{r,s}(G)$ to get $\bar v$, which satisfies that

\[\sum_{i=1}^{t}|\rho_{G,r}(\{\tau_i\})-\bar v_i| \leq \lambda\]

with probability at least ${19}/{20}$.

* Reject $G$ if $\sum_{\tau_i\in \F}\bar v_{i}>0$. Accept otherwise.

The query complexity of $T$ is clearly constant, since $s$ is constant and
the number of vertices in any $r$-neighbourhood is bounded by $d^{r+1}+1$
for graphs in $\mathcal{C}_{d}$. The running time of the first step is $f_M(n)$ and
for the other steps it is constant.

To prove that $T$ is an $\epsilon$-tester, first assume that $G\in \mathcal{P}$. Then $n\notin M$ and $\mathcal{N}_r^G\in \tau \notin \F$ for all vertices $v$ . Hence $\sum_{\tau_i\in \F}\bar v_{i}=0$ and $T$ accepts $G$.
Now consider that $G$ is $\epsilon$-far from $\mathcal{P}$. If $n\in M$ then
$G$ is rejected in the first step. Hence let $n\notin M$, and assume
$\sum_{i=1}^{t}|\rho_{G,r}(\{\tau_i\})-\bar v_i|  \leq \lambda$, which occurs with
probability at least ${19}/{20}\geq {2}/{3}$. Then

\begin{align*}
\sum_{\tau_i\in \F}\bar v_{i}&=\sum_{\tau_i\in \F}\rho_{G,r}(\{\tau_i\})-\sum_{\tau_i\in \F}\big(\rho_{G,r}(\{\tau_i\})-\bar v_{i}\big)\\&>
\lambda-\Big|\sum_{\tau_i\in \F}\big(\rho_{G,r}(\{\tau_i\})-\bar v_{i}\big)\Big|\geq\lambda-\sum_{\tau_i\in \F}\big|\rho_{G,r}(\{\tau_i\})-\bar v_{i} \big|\geq 0,
\end{align*}

the first inequality holds by the  assumption that in graphs that are $\epsilon$-far from $\mathcal{P}$ there are more than $\lambda n$ vertices whose type is in $F$.
Hence $T$ rejects $G$.

To illustrate the use of the set $M$ in Lemma <ref>, let
$\mathcal{P}$ be the property of being $K_4$-neighbourhood regular. Let $G_m$ be the
graph consisting of $m$ disjoint copies of $K_4$ and one isolated vertex. First
note that $G_m$ contains $4m+1$ vertices. Being $K_4$-regular implies that
every vertex has degree $3$. But because every graph contains an even number of
vertices of odd degree, $G_m$ cannot be made $K_4$-neighbourhood regular by
edge modifications. Therefore $G_m$ is $\epsilon$-far from $\mathcal{P}$. But for
$m\rightarrow \infty$ the probability of sampling the isolated vertex in $G_m$
tends to $0$ meaning that with high probability the tester with $M=\emptyset$
will accept $G_m$. We will show in Theorem <ref>
that $\mathcal{P}$ is testable if we set $M=\mathbb{N} \setminus \{4m\mid m\in \mathbb{N}\}$.

For $r\geq 1$ let  $\tau$ be an $r$-type. Let $B$ be an $r$-ball with constant $a$ of type $\tau$. Let $\tilde{d}< d$, $d\not= 0$ be integers and
assume that $\mathcal{N}_{r-1}^B(a)$ contains a vertex $b$ with
$\deg_B(b)=\tilde{d}$ and that $\deg_B(v)\not=\tilde{d}+1$ for all
vertices $v$ in $\mathcal{N}_{r-1}^B(a)$. Let $\epsilon \in (0,1]$ be fixed,
$n_0={2d^2}/{\epsilon}$ and $\lambda={\epsilon
d}/(14(1+d^{2r+1}))$. Then every graph $G\in \mathcal{C}_{d}$ on
$n\geq n_0$ vertices which is $\epsilon$-far from being
$\tau$-neighbourhood free contains more than $\lambda n$ vertices
of $r$-type $\tau$.

We proceed by contraposition. Assume $G\in
\mathcal{C}_{d}$ is a graph on $n\geq n_0$ vertices containing no more than $\lambda n
$ vertices $v$ of $r$-type $\tau$.

Case $\tilde{d}=0$, $d>1$.
In this case the forbidden type $\tau$ must be an isolated vertex. Since every vertex of degree $0$ must be of the forbidden type,  we add one edge to every pair of vertices of degree $0$.  If there is only one vertex $v$ of degree $0$ left, we  add an edge from $v$ to any other vertex of degree $<d$. If there is no such vertex then there must be vertex $u$ contained in two edges and we replace one edge $\{u,w\}$ by $\{v,w\}$. That way we obtain $G'$ which is $2\lambda n\leq \epsilon dn$ close to $G$.

Case $\tilde{d}\geq 1$. Let us pick a set
$\{v_1,\dots,v_k\}$ of $k\leq \lambda n$ vertices of degree $\tilde{d}$ such
that for every vertex $v$ of $r$-type $\tau$ there is an
index $1\leq i\leq k$ with $v_i\in N_{r-1}^G(v)$. We will
distinguish the following two cases.

First assume that there are less than $\lambda n$ vertices of degree
$\tilde{d}$, of pairwise distance greater than $2r$ and of distance greater
than $2r$ from $\{v_1,\dots,v_k\}$. Then there are less than $2\lambda n
(1+d^{2r+1})$ vertices of degree $\tilde{d}$ in total. We distinguish two cases. First consider the case that $\tilde{d}=1$. In this case
we  add edges between pairs of degree $1$ vertices. If there are two vertices of degree $1$ left   who are adjacent, we delete the edge between them. If there is only one vertex $v$ of degree $1$ left, then there is another vertex $u$ of odd degree. By removing an edge $\{u,w\}$ and adding $\{v,w\}$ we get that $\deg_G(v),\deg{w}\geq 1$. We obtain $G'$  which is $2\lambda n(1+d^{2r+1})\leq \epsilon dn$ close to $G$ and  contains no vertex of degree $\tilde{d}$ and therefore has to be $\tau$-free.

Now consider the case that $\tilde{d}\geq 2$. In this case we let $G'$ be a
graph obtained from $G$ by the following modifications. For every vertex
$v$ of degree $\tilde{d}$ we pick edges
$\{v,v_1\},\{v,v_2\},\{w,w'\},\{u,u'\}$ such that $v,w,u$ have pairwise
distance at least $3$. We delete the  edges $\{v,v_1\},\{v,v_2\}$, $\{w,w'\},\{u,u'\}$ and insert the edges
$\{v_1,w\},\{v_2,u\},\{w',u'\}$, reducing the degree of $v$ while
maintaining the degrees of all other vertices. The resulting graph has no
vertex of degree $\tilde{d}$. Note that if such edges do not exist at any
point during the iteration the graph contains no more than $2d^3\leq
\epsilon dn$ edges, and we delete them all resulting in a graph with no
vertex of degree $\tilde{d}$.

In total we did no more than $7\cdot
2\lambda n (1+d^{2r+1})\leq \epsilon dn$ edge modifications which implies that
$G'$ is $\epsilon$-close to $G$. In addition, $G'$ is
$\tau$-neighbourhood free, because a neighbourhood
of type $\tau$ would imply having a vertex of degree

Now assume that there are at least $\lambda n$ vertices of degree
$\tilde{d}$, of pairwise distance greater than $2r$ and of distance greater
than $2r$ from $\{v_1,\dots,v_k\}$. Let $\{v_1',\dots,v_k'\}$ be a set of
vertices of degree $\tilde{d}$ such that $\dist_G(v_i,v_j')> 2r$ for all
$1\leq i,j\leq k$ and $\dist(v_i',v_j')> 2r$ for all $1\leq i<j\leq k$. Let
$G'$ be the graph obtained from $G$ by inserting the edges $\{v_i,v_i'\}$.
First note that this takes no more than $\lambda n \leq \epsilon d n$ edge
modifications which implies that $G$ is $\epsilon$-close to $G'$.  Further
assume that $v'$ is a vertex in $G'$ of $r$-type $\tau$.
By choice of the set $\{v_1,\dots,v_k\}$  we altered the isomorphism type of each vertex of type $\tau$ in $G$. Therefore
Therefore $\mathcal{N}_r^{G'}(v')$  contains an
inserted edge $(v_i,v_i')$. We will first prove that either
$\dist_{G'}(v',v_i)<r$ or $\dist_{G'}(v',v_i')<r$. Assume that this is not the case. Then there is a path
such that $w_j\not=v_i$ and $w_j\not=v_i'$ for all $-r<j<r$. Let $-r\leq
j<r$ be the largest index such that $w_j\in
\{v_1,\dots,v_k,v_1',\dots,v_k'\}$. Then the path $(w_j,\dots,w_r=v_i')$ is
a path in $G$ of length $\leq 2r$, which contradicts the choice of  $v_1,\dots,v_k,v_1',\dots,v_k'$. Since
$\deg_{G'}(v_i)=\deg_{G'}(v_i')=\tilde{d}+1$, this implies that
$\mathcal{N}_{r-1}^G(v')$ contains a vertex of degree $\tilde{d}+1$,
which contradicts that $v'$ has $r$-type
$\tau$. Hence $G'$ is
$\tau$-neighbourhood free.

For $r\geq 1$ let $\tau$ be an $r$-type. Let $B$ be an $r$-ball with constant $a$ of type $\tau$. Assume $\deg_B(v)=d$ for all vertices $v\in N^{B}_{r-1}(a)$. Let $\epsilon\in (0,1]$ be fixed and let $\lambda=\epsilon$. Then every graph $G\in \mathcal{C}_{d}$ on $n\geq 1$ vertices which is $\epsilon$-far from being $\tau$-neighbourhood free contains more than $\lambda n$ vertices of $r$-type $\tau$.

If $d=0$, then the Lemma holds.
Hence we can assume that $B$ is not just an isolated vertex.
We proceed by contraposition. Assume $G\in \mathcal{C}_{d}$ is a graph on $n\geq 1$
vertices containing no more than $\lambda n $ vertices $v$ of $r$-type
$\tau$. Let $G'$ be the graph obtained from $G$ by
isolating all vertices $v$ of $r$-type $\tau$. First note
that $G'$ is $\epsilon$-close to $G$ since we did no more than $d\lambda n
\leq \epsilon dn$ edge modifications. Now assume that $v'$ is a vertex of
$r$-type $\tau$. Since we isolated all vertices having
$r$-type $\tau$ we know that
\mathcal{N}_{r}^G(v')$.  Therefore there
must be a vertex $v$ in $N_{r}^G(v')$ such that
$v$ has type $\tau$, because otherwise the
$r$-ball of $v'$ could not witness any of the edge modifications. This means
that there is a path $(v'=v_0,v_1,\dots,v_{k-1},v_k=v)$ of length $k\leq r$
in $G$. Now pick the maximum index $i$ such that
$\dist_{G'}(v',v_i)<\infty$. First observe that because $v=v_k$ is isolated
in $G'$ we get that $i<k$ and therefore $\dist_{G'}(v',v_i)<r$.  Since
$\dist_{G'}(v',v_{i+1})=\infty$ by construction and $\{v_i,v_{i+1}\}\in
E(G)$, we get
d$. Since $\mathcal{N}_{r}^{G'}(v')\in \tau$ this yields a
contradiction to our previous assumption that all vertices in
$\mathcal{N}^{B}_{r-1}{a}$ have degree $d$. Hence the graph $G'$ can not
contain a vertex $v'$ of $r$-type $\tau$ and is therefore
$\tau$-neighbourhood free.

The next Lemma follows from Lemmas <ref> and <ref>

for $r=1$, since the $0$-ball has one vertex.

Let  $\tau$ be a $1$-type. Let $\epsilon\in (0,1]$ be fixed, $n_0={2d^2}/{\epsilon}$ and $\lambda={\epsilon d}/(14(1+d^{3}))$. Then every graph $G\in \mathcal{C}_{d}$ on $n\geq n_0$ vertices which is $\epsilon$-far from being $\tau$-neighbourhood free contains more than $\lambda n$ vertices of $1$-type $\tau$.

Lemma <ref> with $\F=\{\tau\}$   and $M=\emptyset$ combined with Lemma <ref> proves Theorem <ref> in all cases apart from when $d=1$. In case $d=1$ we have $\tilde{d}=0$. In this case we set $M:=\{n\in\mathbb{N}\mid n\equiv 1\mod 2 \}$ and get that for $\epsilon\in (0,1]$ and  $\lambda=\epsilon$ we have that every graph $G\in \mathcal{C}_{d}$ on $n\equiv 0\mod 2$ vertices which is $\epsilon$-far from being $\tau$-neighbourhood free contains more than $\lambda n$ vertices of $r$-type $\tau$. This is the case as assuming the number of vertices of $r$-type $\tau$ is no more than $\lambda n$ we can add an edge between any pair of vertices of degree $0$, obtaining a graph $G'$ which is $\lambda n\leq \epsilon dn$ close to $G$.

Theorem <ref> follows from Lemma <ref> and Lemma <ref> where in Lemma <ref> we use either $\F=\{\tau\}$ or $\F=\emptyset$ depending on whether $\tau$ has degree bounded by $d$.
Let $\tau$ be a $1$-type such that   $B\setminus \{a\}$ is a union of disjoint cliques for all $(B,a)\in \tau$ as in the statement of the theorem.
We define $\mathcal{P}$ to be the property of being $\tau$-neighbourhood regular and let $\setOfMaxCliques$ be the set of maximal cliques in $G$. Let us define the function $\maxcl^G:V(G)\times\mathbb{N}\rightarrow \mathbb{N}$ where $\maxcl^G(v,i):=|\{K\in \setOfMaxCliques\mid |K|=i,v\in K\}|$  is the number of maximal $i$-cliques containing $v$.

If $G\in \mathcal{P}$ then $\maxcl^B(a,i)\cdot n\equiv 0\mod i$.

First note that $G\in \mathcal{P}$ implies that $\mathcal{N}_1^G(v)\in \tau$ for all $v\in V(G)$. Then $\maxcl^B(a,i)=\maxcl^G(v,i)$ for all $v\in V(G)$ and

\[\maxcl^B(a,i)\cdot n  =\sum_{v\in V}\maxcl^G(v,i) =|\{K\in\setOfMaxCliques\mid |K|=i \}|\cdot i\equiv 0 \mod i.\]

Let $M:=\{n\in \mathbb{N}\mid \text{there is }1\leq i \leq d \text{ such that }\maxcl^B(a,i)\cdot n\not\equiv 0 \mod i\}$.
Note that deciding whether $n\in M$
only requires standard arithmetic operations.

For $\epsilon\in (0,1]$ let $\lambda={\epsilon}/(20d^6) $ and $n_0=20 d^8$.  Than any graph $G\in \mathcal{C}_{d}$ on $n\geq n_0$, $n\notin M$ vertices, which is $\epsilon$-far from $\mathcal{P}$, contains more than $\lambda n$ vertices $v$ which are not of $1$-type $\tau$.

We proceed by contraposition. Let $G\in \mathcal{C}_{d}$ be a graph on $n\geq n_0$, $n\notin M$ vertices and assume that $G$ contains $\leq \lambda n$ vertices which are not of $1$-type $\tau$. We will now describe an algorithmic procedure which takes $<\epsilon d n$ edge modifications and transforms $G$ into a graph $G^{(4)}\in \mathcal{P}$, which will prove the claim.

Let $\tilde{E}^{(1)}:=\{e\in E(G)\mid \text{there are distinct } K, K'\in \setOfMaxCliques, |K\cap K'|>1,e\subseteq K\}$.  Let $G^{(1)}$ be the graph $G^{(1)}=(V(G), E^{(1)})$, where $E^{(1)}=E\setminus\tilde{E}^{(1)}$. First note that $G^{(1)}$ has no distinct maximal cliques $K,K'$ with $|K\cap K'|>1$. Furthermore

\begin{align*}
|\tilde{E}^{(1)}|&\leq {d\choose 2}\cdot |\{K \in \setOfMaxCliques \mid \text{exists } K'\in \setOfMaxCliques , |K\cap K'|>1 \}|\leq \frac{d^3\lambda n}{2},
\end{align*}

where the second inequality holds because every $K\in \setOfMaxCliques$ such that there is $K'\in\setOfMaxCliques$ with $|K\cap K'|>1$ and $K\neq K'$ must contain one of the $\lambda n$ vertices $v$ which are not of $1$-type $\tau$ and there are $\leq d\lambda n$ maximal cliques containing such a vertex. In addition, the removal of the edges in $\tilde{E}^{(1)}$ will affect no more than $d^4\lambda n$ vertices because there are no more than $d^3\lambda n$ vertices contained within an edge of $\tilde{E}^{(1)}$, each of their $1$-neighbourhoods contains $d$ vertices and any vertex, whose $1$-neighbourhood is affected, must be of distance $1$ to one of the vertices contained in an edge in $\tilde{E}^{(1)}$. Hence $G^{(1)}$ contains $\leq (d^4+1)\lambda n<2d^4\lambda n$ vertices $v$ which are not of $1$-type $\tau$.

Note that in $G^{(1)}$ for all vertices $v$ the graph $\mathcal{N}^{G^{(1)}}_{1}(v)\setminus \{v\}$ is a disjoint union of cliques but there might be $K\in \setOfMaxCliques[G^{(1)}]$ such that $\maxcl^B(a,|K|)=0$. We define the edge set  $\tilde{E}^{(2)}:=\{e\in E^{(1)}\mid \text{exists }K\in \setOfMaxCliques[G^{(1)}], e\subseteq K,\maxcl^B(a,|K|)=0\}$ and let $G^{(2)}$ be the graph $G^{(2)}=(V(G), E^{(2)}))$, where $E^{(2)}=E^{(1)}\setminus\tilde{E}^{(2)}$.

\begin{align*}
|\tilde{E}^{(2)}|&\leq d\cdot |\{v\mid \text{exists }K\in \setOfMaxCliques[G^{(1)}], v\in K,\maxcl^B(a,|K|)=0\}|\leq d\cdot 2d^4\lambda n,
\end{align*}

where the first inequality holds because every clique in $G^{(1)}$ has size $\leq d$ and the second because $\mathcal{N}^{G^{(1)}}_{1}(v)\notin \tau$ for every $v\in \{v\mid \text{exists }K\in \setOfMaxCliques[G^{(1)}], v\in K,\maxcl^B(a,|K|)=0\}$.

Note that $\maxcl^B(a,|K|)\not= 0$ for all $K\in
\setOfMaxCliques[G^{(2)}]$, but there might be $v\in V(G)$ and
$i\leq d$ with $\maxcl^B(a,i)\not=\maxcl^{G^{(2)}}(v,i)$. Moreover,
note that because $n\geq n_0$ there are at least $2d$ $4$-balls in
$G^{(2)}$ which are completely disjoint from the $4$-balls of any vertex
$v$ of $1$-type $\tau$. $G^{(3)}$ will also have this
Let $G^{(3)}=(V(G),E^{(3)})$ be the graph obtained from $G^{(2)}$ by the following operations.
For every pair $v,v'$ such that there is $i\leq d$ with
$\maxcl^B(a,i)>\maxcl^{G^{(2)}}(v,i)$ and
$\maxcl^B(a,i)<\maxcl^{G^{(2)}}(v',i)$, let $w$ be a vertex of type
$\tau$ which has at least distance $4$ to $v$ and to $v'$.
Let $ K'=\{v'_1,\dots,v'_{i-1},v'\}\in \setOfMaxCliques[G^{(2)}]$ and
$K=\{v_1,\dots,v_{i-1},w\}\in \setOfMaxCliques[G^{(2)}]$. Delete the
edges $\{\{v',v'_j\},\{w,v_j\}\mid  j\in [i-1]\}$ and add the edges
$\{\{v,v_j\}, \{w,v'_j\}\mid j\in [i-1]\}$. Note that the vertices
$v_1,\dots,v_{i-1},v'_1,\dots,v'_{i-1},w$ are still contained in the same
number of cliques as before, while $v$ is contained in one additional
$i$-clique and $v'$ is contained in one less.

Note that in $G^{(3)}$, it holds that either $\maxcl^B(a,i)\geq
\maxcl^{G^{(3)}}(v,i)$ for all vertices $v$, or $\maxcl^B(a,i)\leq
\maxcl^{G^{(3)}}(v,i)$ for all $v$ for every $i\in \{1,\dots,d\}$.
Let $G^{(4)}$ be the graph obtained from $G^{(3)}$ by the following
operations. For every $i$ such that there is a vertex $v$ with
$\maxcl^B(a,i)<\maxcl^{G^{(3)}}(v,i)$, we pick $i$ not necessarily
distinct vertices
$v_1,\dots,v_i$ with the following property. In case a vertex $v$ appears $k$ times amongs $v_1,\dots, v_i$ then
$\maxcl^{G^{(3)}}(v,i)-\cdot\maxcl^B(a,i)\geq k$. Note that
these choices are possible because $\sum_{v\in
V(G^{(3)})}\maxcl^{G^{(3)}}(v,i)\equiv 0 \mod i$ and $\maxcl^B(a,i)\cdot
n\equiv 0 \mod i$ by assumption $n\notin M$ and hence we have $\sum_{v\in
E^{(3)}}(\maxcl^{G^{(3)}}(v,i)-\maxcl^B(a,i))\equiv 0 \mod i$. Let
$K_1,\dots,K_i\in \setOfMaxCliques[G^{(3)}]$  be distinct cliques such that $v_j\in K_j$ for every
$1\leq j\leq i$. Let $K=\{w_1,\dots,w_i\}\in \setOfMaxCliques[G^{(3)}]$
such that the distance between any pair $v_j,w_k$ is at least $4$. Remove
the set of edges $\{\{w_j,w_k\},\{v_j,v\}\mid v\in K_j, j,k\in [i]\}$ and
add the set of edges $\{\{w_j,v\}\mid v\in K_j,j\in [i]\}$. Note that
this reduces the number of maximal $i$-cliques $v_1,\dots,v_i$ are in by
one, while leaving the number of cliques $w_1,\dots,w_i$ are in the
Similarly, for  every $i$  such that there is a vertex $v$ with
$\maxcl^B(a,i)>\maxcl^{G^{(3)}}(v,i)$ we pick $i$ not necessarily
distinct vertices
$v_1,\dots,v_i$ with the following property. In case $v$ appears $k$ time amongst $v_1,\dots,v_i$ we have
$\maxcl^B(a,i)-\maxcl^{G^{(3)}}(v,i)\leq k$. Let
$w_1,\dots,w_i$ be vertices with $\maxcl^B(a,i)=\maxcl^{G^{(3)}}(w_j,i)$
such that $w_1,\dots,w_i$ are of distance at least $4$ from every $v_j$, $1\leq j\leq i$, and $w_1,\dots,w_i$ are pairwise of distance at least
Let $K_j\in \setOfMaxCliques[G^{(3)}]$ with $w_j\in K_j$ for $ j\in
\{1,\dots,i\}$. Remove the set of edges  $\{\{w_j,w\}\mid w\in K_j,1\leq j\leq i\}$
and add the set of edges $\{\{v_j,w\}\{w_j,w_k\}\mid w\in K_j,j,k\in
\{1,\dots,i\}\}$. Note that this adds one to the number of $i$-cliques
$v_1,\dots,v_i$ are in, while leaving the number of $i$-cliques
$w_1,\dots,w_i$ are in the same.

By construction $G^{(4)}\in \mathcal{P}$. The number of edge modifications in
total  is $|E^{(1)}|+|E^{(2)}|$ plus the number of modifications it takes
to transform $G^{(2)}$ into $G^{(4)}$. First note that

∑_i=3^d∑_v∈V(G)|^B(a,i)-^G^(2)(v,i)|≤2d ·2d^4λn

since every of the $2d^4\lambda n$ vertices $v$ in
$G^{(2)}$ of $1$-type $\tau$ can contribute at most $2d$ to
the sum above. Since transforming $G^{(2)}$ into $G^{(4)}$ we proceed
greedily, meaning we reduce the number $\sum_{i=3}^{d}\sum_{v\in
V(G)}|\maxcl^B(a,i)-\maxcl^{G^{(2)}}(v,i)|$ by at least one in
every step, and every such reduction takes a maximum of $4d^2$ edge
modifications in total we need less than

|E^(1)|+|E^(2)|+4d^2·2d·2d^4λn≤20 d^7λn=ϵd n

edge modifications.

Let $\mathcal{F}:=\{\tau'\mid \tau \text{ is a }1\text{-type },\tau\not=\tau'\}$. Note that $|\mathcal{F}|\leq t<\infty$, where equality occurs when $B\notin \mathcal{C}_{d}$. Then Claim <ref> combined with Lemma <ref> for $M$ and $\mathcal{F}$ defined as above proves the Theorem.

§ CONCLUSION

We studied testability of properties definable in first-order logic in the bounded-degree model of property testing for graphs and relational structures, where testability of a property means if it is testable with constant query complexity. We showed that all properties in $\Sigma_2$ are testable (Theorem <ref>),
and we complemented this by exhibiting a property (of relational structures) in $\Pi_2$ that is not testable (Theorem <ref>).
Using a hardness reduction, we also exhibit a property of undirected, 3-regular graphs in $\Pi_2$ that is not testable (Theorem <ref>). The question whether first-order definable properties are testable with
a sublinear number of queries  (e.g. $\sqrt{n}$) in the bounded-degree model is left open.

Similar results (on the separation between $\Sigma_2$ and $\Pi_2$ properties) were obtained in the dense graph model in [4], albeit with very different methods. Indeed, non-testability of first-order logic in the bounded-degree model is somewhat unexpected: Testing algorithms proceed by sampling vertices and then exploring their local neighbourhoods, and
it is well-known that first-order logic can only express `local' properties. On
graphs and structures of bounded degree this is witnessed by Hanf's strong normal form of first-order logic [24], which is built around the absence and presence of different isomorphism types of local neighbourhoods.
However, our negative result shows that locality of first-order logic is not sufficient for testability. This also answers an open question from [1].

We obtained our non-testable properties by
encoding the zig-zag construction of bounded-degree expanders into first-order logic on
relational structures (Theorem <ref>) and then extending this to undirected graphs (Theorem <ref>).
We believe that this will be of independent interest.
We remark that it might also be possible to use the iterative construction of replacement product graphs of [33]
instead of the zig-zag construction to obtain a similar example.

We then used our non-testable graph property to answer a question on proximity oblivious testers in the bounded-degree model, asked
by Goldreich and Ron more than 10 years ago [22]. Such a tester is particularly simple: it performs a basic test a number of times that may depend on the proximity parameter,
whereas the basic test is oblivious of the parameter. In [22], the properties that are testable in this model have been characterised as those that are both GSF-local, and non-propagating. Roughly speaking, GSF-local means that the graph class omits a family of generalised subgraphs (subgraphs with constraints on how the subgraphs interact with the rest of the graph), and
non-propagating means that
graphs in which a forbidden generalised subgraph is unlikely to be detected by sampling vertices
are actually close to having the property in terms of edge modifications. In other words, no `chain reactions' occur, where repairing one edge will produce new unwanted configurations that again need repairing, etc.
Goldreich and Ron asked, whether `non-propagating' is necessary.
We showed that this is the case.
Our proof is based on relating first-order definable properties to GSF-local properties, via a notion that we call neighbourhood profiles, which captures first-order definability.
Finally, we took an approach suggested by Hanf's normal form, and we proved testability of some
first-order properties that speak about isomorphism types of neighbourhoods, including testability
of $1$-neighbourhood-freeness, and  $r$-neighbourhood-freeness under a mild assumption on the
degrees (Theorem <ref>, Theorem <ref>, and Theorem <ref>).
In particular, these theorems imply that there are properties defined by formulas in $\Pi_2\setminus \Sigma_2$ which are testable. Since subgraph-freeness and subgraph containment are testable, Hanf's normal form suggests
studying testability of (negated) Hanf sentences, i. e. neighborhood properties, as a next step.
While Hanf sentences are trivially testable, we pose as an open problem whether every negated Hanf sentence is testable.

Let us remark that not all $\Sigma_2$-properties are GSF-local. Indeed, subgraph containment can be expressed in $\Sigma_1$,
while it is not a GSF-local property.
Also observe that our testers for neighbourhood properties in Section <ref> have one-sided error, i. e. the testers always accept the graphs that satisfy the property. Finally, note that, in contrast to subgraph-freeness and induced subgraph-freeness, the properties $\tau$-neighbourhood regularity and $\tau$-neighbourhood-freeness are neither monotone nor hereditary, which are properties that are closed under edge deletion and closed under vertex deletion, respectively.
As we mentioned before, Ito et al. [27] recently characterised one-sided error (constant-query) testable monotone and hereditary graph properties in the bounded-degree (directed and undirected) graph model. In order to give a full characterisation of one-sided error testable properties in the bounded-degree graph model, it is important to take a step beyond monotone and hereditary graph properties.

§ DEFERRED PROOFS FROM SECTION <REF>: ALTERNATIVE PROOF OF THEOREM <REF>

Now we make use of a result from [15] and our Lemma <ref> that the models of $\graphFormula$ is a family of expanders to give an alternative proof of Theorem <ref>.
We first introduce a definition of “hyperfinite graphs”.

Let $\varepsilon\in (0,1]$ and $k\geq 1$. A graph $G$ with maximum degree bounded by $d$ is called $(\varepsilon,k)$-hyperfinite if one can remove at most $\varepsilon d |V|$ edges from $G$ so that each connected component of the resulting graph has at most $k$ vertices. For a function $\rho: (0,1]\rightarrow\mathbb{N}^+$, a graph $G$ is called $\rho$-hyperfinite if $G$ is $(\varepsilon,\rho(\varepsilon))$-hyperfinite for every $\varepsilon>0$. A set (or property) $\Pi$ of graphs is called $\rho$-hyperfinite if every graph in $\Pi$ is $\rho$-hyperfinite. A set (or property) $\Pi$ of graphs is called hyperfinite if it is $\rho$-hyperfinite for some function $\rho$.

Now we recall that a graph property is a set of graphs that is invariant under graph isomorphism. A subproperty of a property $P$ is a subset of graphs in $P$ that is also invariant under graph isomorphism.

Let $C_d$ be the class of graphs of bounded maximum degree $d$. Let $P\subseteq C_d$ be a property that does not contain an infinite hyperfinite subproperty, and let $P'\subseteq C_d$ be arbitrary property such that $P\cap P'$ is an infinite set. Then $P\cap P'$ is not testable.

Now we are ready to give another proof of Theorem <ref>.

We show that the property $\graphProp$ does not contain an infinite hyperfinite subproperty. If this is true, then by applying Lemma <ref> with $P=\graphProp$ and $P'=C_d$, we have that $\graphProp$ is not testable. This will then finish the proof of Theorem <ref>.

Suppose towards contradiction that $\graphProp$ contains an infinite hyperfinite subproperty. That is, there exists an infinite subset $Q\subseteq \graphProp$ and a function $\rho : (0, 1] \rightarrow \mathbb{N}$ such that $Q$ is $(\varepsilon, \rho(\varepsilon))$-hyperfinite for every $\varepsilon > 0$.
That is, for any graph $G=(V,E)\in Q$, for any $\varepsilon>0$, we can remove $\varepsilon d |V|$ edges from $G$ so that each connected component of the resulting graph has at most $\rho(\varepsilon)$ vertices. Now let $\varepsilon$ be an arbitrarily small constant such that $\rho(\varepsilon)\ll |V|$ and that $\varepsilon\leq \frac{\xi}{100d}$, where $\xi$ is the constant from Lemma <ref>. Let $V_1,V_2,\dots$ be a vertex partitioning of $V$ such that $|V_i|\leq \rho(\varepsilon)$ and the number of edges crossing different parts is at most $\varepsilon d |V|$. Let $S$ be a vertex subset that is a union of the first $j$ parts $V_1,\cdots,V_j$ such that $|\cup_{i\leq j-1} V_i|< \frac{|V|}{3}$ and $|\cup_{i\leq j} V_i|\geq\frac{|V|}{3}$. Note that such a set always exists as $|V_i|\leq \rho(\varepsilon)\ll |V|$ and furthermore, $|S|=|\cup_{i\leq j} V_i|<\frac{|V|}{2}$. Now on one hand, $|\langle S, \bar{S}\rangle|$ is at most the number of edges crossing different parts and thus at most $\varepsilon d |V|$. On the other hand, since $G\in \graphProp$, $G$ is a $\xi$-expander for some constant $\xi$ from Lemma <ref>. Thus, $|\langle S, \bar{S}\rangle|\geq \xi \frac{|V|}{3} > \varepsilon d |V|$, which is a contradiction by our setting of $\varepsilon$. Therefore,  $\graphProp$ does not contain an infinite hyperfinite subproperty. This finishes the proof of the theorem.

§ DEFERRED PROOFS FROM SECTION <REF>

Every structure $\struc{A}\in \bigcup_{1\leq k \leq m}\classStruc{P}_{\rho_k}\setminus \{\struc{A}_{\emptyset}\}$ satisfies $\varphi_{\operatorname{tree}}$.

Let $\struc{A}\in \bigcup_{1\leq k \leq m}\classStruc{P}_{\rho_k}\setminus \{\struc{A}_{\emptyset}\}$. Then there is $k\in \{1,\dots,m\}$ such that $\struc{A}\in \classStruc{P}_{\rho_k}$.

By definition, $\varphi_{\operatorname{tree}}:= \exists^{\leq 1} x \varphi_{\operatorname{root}}(x)\land \varphi \land \forall x (\psi(x)\lor \chi(x))$,  where

\begin{align*}
\varphi:= &\forall x \Big(\big(\varphi_{\operatorname{root}}(x)\land R(x,x)\big)\lor
\big(\exists^{=1} y F(y,x)\land \lnot \exists y R(x,y)\land \lnot \exists y R(y,x)\big)\Big),
\\\psi(x):= &\neg\exists y F(x,y)\land \bigwedge_{k\in \indexSetH} L_k(x,x)\land \forall y \Big(y\not= x \rightarrow
\\& \bigwedge_{k\in \indexSetH}\lnot L_k(x,y) \wedge \bigwedge_{k\in \indexSetH}\lnot L_k(y,x)\Big)
\end{align*}

\begin{align*}
\chi(x):=&\lnot\exists y \bigvee_{k\in \indexSetH}\big(L_k(x,y)\lor L_k(y,x)\big)\land
\bigwedge_{k\in \indexSetH}\exists y_{k} \Big(x\not=y_{k}\land F_{k}(x,y_{k})\\
&\land %\\&
(\bigwedge_{k'\in \indexSetH,k'\not=k}\lnot F_{k'}(x,y_k))\land \forall y(y\not=y_k\rightarrow \lnot F_{k}(x,y))\Big).
\end{align*}

Thus, it is sufficient to prove that $\struc{A}\models \exists^{\leq 1} x \varphi_{\operatorname{root}}(x)$, $\struc{A}\models \varphi$ and $\struc{A}\models\forall x (\psi(x)\lor \chi(x))$.

To prove $\struc{A}\models \exists^{\leq 1} x \varphi_{\operatorname{root}}(x)$ we note that by construction of $\rho_k$ we have $\struc{A}\not\models \varphi_{\operatorname{root}}(a)$
for any $a\in \univ{A}$ for which $(\mathcal{N}_2^{\struc{A}}(a),a)\notin \tau_{d,2,\sigma}^k$. Since $\rho_k$ restricts the number of occurrences of elements of neighbourhood type $\tau_{d,2,\sigma}^{k}$ to at most one, this proves that there is at most one $a\in \univ{A}$ with $\struc{A}\models \varphi_{\operatorname{tree}}(a)$ and hence $\struc{A}\models \exists^{\leq 1} x \varphi_{\operatorname{root}}(x)$.

To prove $\struc{A}\models \varphi$, let $a\in \univ{A}$ be an arbitrary element.
Since $\struc{A}\in \classStruc{P}_{\rho_k}$, there is an $i\in I_{k}$ such that $(\mathcal{N}_2^{\struc{A}}(a),a)\in \tau_{d,2,\sigma}^i$.
But then by definition, there exist $\other{\struc{A}}\models \varphi_{\zigzag}$ and $\other{a}\in \univ{\other{A}}$ such that $(\mathcal{N}_2^{\struc{A}}(a),a)\cong (\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$.
Assume $f$ is an isomorphism from  $(\mathcal{N}_2^{\struc{A}}(a),a)$ to  $(\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. First consider the case that $\struc{A}\models \varphi_{\operatorname{root}}(a):=\forall y \lnot F(y,a)$. Assume there  is $\other{b}\in \univ{\other{A}}$ such that $(\other{b},\other{a})\in \rel{F}{\other{\struc{A}}}$. Since $\other{b}\in N_2^{\other{\struc{A}}}(\other{a})$, there must be an element $b\in N_2^{\struc{A}}(a)$ such that $f(b)=\other{b}$. Since $f$ is an isomorphism mapping $a$ to $\other{a}$, this implies $(b,a)\in \rel{F}{\struc{A}}$, which contradicts $\struc{A}\models \varphi_{\operatorname{root}}(a)$.
Hence $\other{\struc{A}}\models \varphi_{\operatorname{root}}(\other{a})$. Since $\other{\struc{A}}\models \varphi_{\operatorname{tree}}'$, it holds that $\other{\struc{A}}\models \varphi$, which means that $(\other{a},\other{a})\in \rel{R}{\other{\struc{A}}}$. But since $f$ is an isomorphism mapping $a$ onto $\other{a}$, this implies $(a,a)\in \rel{R}{\struc{A}}$. Now consider the case that
$\struc{A}\not\models \varphi_{\operatorname{root}}(a)$. Then there is $b\in \univ{A}$ with $(b,a)\in \rel{F}{\struc{A}}$. Since $f$ is an isomorphism, this implies $(f(b),\other{a})\in \rel{F}{\other{\struc{A}}}$. Hence $\other{\struc{A}}\models \exists^{=1} y F(y,\other{a})\land \lnot \exists y R(\other{a},y)\land \lnot \exists y R(y,\other{a})$, as $\other{\struc{A}}\models \varphi$. Now assume that  there is $b'\not=b$ such that $(b',a)\in \rel{F}{\struc{A}}$. Then $f(b)\not=f(b')$ and $(f(b),\other{a}),(f(b'),\other{a})\in \rel{F}{\other{\struc{A}}}$. Since this contradicts $\other{\struc{A}}\models \exists^{=1} y F(y,\other{a})$ we have $\struc{A}\models \exists^{=1} y F(y,a)$. Furthermore, assume that there is $b'\in \univ{A}$ such that either $(a,b')\in \rel{R}{\struc{A}}$ or $(b',a)\in \rel{R}{\struc{A}}$. Then either $(\other{a},f(b'))\in \rel{R}{\other{\struc{A}'}}$ or $(f(b'),\other{a})\in \rel{R}{\other{\struc{A}}}$, which contradicts $\other{\struc{A}}\models \lnot \exists R(\other{a},y)\land \lnot \exists y R(y,\other{a})$. Therefore $\struc{A}\models \lnot \exists y R(a,y)\land \lnot \exists y R(y,a)$ which completes the proof of $\struc{A}\models\varphi$.

We prove $\struc{A}\models \forall x (\psi(x)\lor \chi(x))$ by considering the two cases $\struc{A}\models \neg\exists y F(a,y)$ and $\struc{A}\models \exists yF(a,y)$ for each element $a\in \univ{A}$. For this, let $a\in \univ{A}$ be any element. By the construction of $\rho_k$ there is $\other{\struc{A}}\models \varphi_{\zigzag}$ and $\other{a}\in \univ{\other{A}}$ such that $(\mathcal{N}_2^{\struc{A}}(a),a)\cong (\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. Let $f$ be an isomorphism from  $(\mathcal{N}_2^{\struc{A}}(a),a)$ to $(\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. First consider the case that $\struc{A}\models \neg\exists y F(a,y)$. If there was $\other{b}\in \univ{\other{A}}$ with $(\other{a},\other{b})\in \rel{F}{\other{\struc{A}}}$ then $(a,f^{-1}(\other{b}))\in \rel{F}{\struc{A}}$ contradicting our assumption. Hence $\other{\struc{A}}\models \neg\exists y F(\other{a},y)$  which implies that $\other{\struc{A}}\not\models \chi(\other{a})$. But since $\other{\struc{A}}\models \varphi_{\zigzag}$, it holds that $\other{\struc{A}}\models \forall x (\psi(x)\lor \chi(x))$, which implies that $\other{\struc{A}}\models \psi(\other{a})$. Hence $(\other{a},\other{a})\in \rel{L_k}{\other{\struc{A}}}$ for every $k\in \indexSetH$. Since $f$ is an isomorphism and $f(a)=\other{a}$, it holds that $(a,a)\in \rel{L_k}{\struc{A}}$ for every $k\in \indexSetH$, and hence $\struc{A}\models \bigwedge_{k\in \indexSetH} L_k(a,a)$. Furthermore, assume that there is $b\in \univ{A}$, $b\not=a$ and $k\in \indexSetH$ such that either $(a,b)\in \rel{L_k}{\struc{A}}$ or $(b,a)\in \rel{L_k}{\struc{A}}$. Since $f$ is an isomorphism this implies that either $(\other{a},f(b))\in \rel{L_k}{\other{\struc{A}}}$ or $(f(b),\other{a})\in \rel{L_k}{\other{\struc{A}}}$ which contradicts $\other{\struc{A}}\models \chi(\other{a})$. Hence $\struc{A}\models\forall y \Big(y\not= a \rightarrow \bigwedge_{k\in \indexSetH}\lnot L_k(a,y) \wedge \bigwedge_{k\in \indexSetH}\lnot L_k(y,a)\Big)$ proving that $\struc{A}\models \psi(a)$.

Now consider the case that there is an element $b\in \univ{A}$ such that $(a,b)\in \rel{F}{\struc{A}}$. Since this implies that $(\other{a},f(b))\in \rel{F}{\other{\struc{A}}}$, we get that $\other{\struc{A}}\not\models \psi(\other{a})$, and hence $\other{\struc{A}}\models \chi(\other{a})$. Now assume that there is  $b\in \univ{A}$ and $k\in \indexSetH$ such that either $(a,b)\in \rel{L_k}{\struc{A}}$ or $(b,a)\in \rel{L_k}{\struc{A}}$. But then either $(\other{a},f(b))\in \rel{L_k}{\other{\struc{A}}}$ or $(f(b),\other{a})\in \rel{L_k}{\other{\struc{A}}}$, which contradicts $\other{\struc{A}}\models \chi(\other{a})$. Hence $\struc{A}\models  \lnot\exists y \bigvee_{k\in \indexSetH}\big(L_k(a,y)\lor L_k(y,a)\big)$. For each $k\in \indexSetH$, let $\other{b}_k\in \univ{\other{A}}$ be an element such that $\other{\struc{A}}\models \other{a}\not=\other{b}_{k}\land F_{k}(\other{a},\other{b}_{k})\land
(\bigwedge_{k'\in \indexSetH,k'\not=k}\lnot F_{k'}(\other{a},\other{b}_k))\land \forall y(y\not=\other{b}_k\rightarrow \lnot F_{k}(\other{a},y))$. Since $f$ is an isomorphism,  this implies that $a\not= b_k:=f^{-1}(\other{b}_k)$, $(a,b_k)\in \rel{F_k}{\struc{A}}$ and $(a,b_k)\notin \rel{F_{k'}}{\struc{A}}$, for each $k'\in \indexSetH,k'\not=k$. Furthermore, assume there is  $b\in \univ{A}$, $b\not=b_k$ such that $(a,b)\in \rel{F_k}{\struc{A}}$. Since $f$ is an isomorphism, this implies $f(b)\not=f(b_k)=\other{b}_k$ and $(\other{a},\other{b})\in \rel{F_k}{\other{\struc{A}}}$, which contradicts $\other{\struc{A}}\models \forall y(y\not=\other{b}_k\rightarrow \lnot F_{k}(\other{a},y))$. Hence $\struc{A}\models \forall y(y\not=b_k\rightarrow \lnot F_{k}(a,y))$ and therefore concluding that $\struc{A}\models \chi(a)$. This proves that in either case $\struc{A}\models \psi(a)\lor\chi(a)$ and therefore $\struc{A}\models \forall x(\psi(x)\lor \chi(x))$.

Every structure $\struc{A}\in \bigcup_{1\leq k \leq m}\classStruc{P}_{\rho_k}\setminus \{\struc
{A}_{\emptyset}\}$ satisfies $\varphi_{\operatorname{rotationMap}}$.

Let $\struc{A}\in \bigcup_{1\leq k \leq m}\classStruc{P}_{\rho_k}\setminus \{\struc{A}_{\emptyset}\}$. Then there is a $k\in \{1,\dots,m\}$ such that $\struc{A}\in \classStruc{P}_{\rho_k}$.

By definition, $\varphi_{\operatorname{rotationMap}}=\varphi\land \psi$, where

\begin{align*}
&\varphi:= \forall x \forall y \Big(\bigwedge_{i,j\in \indexSetRotation}(E_{i,j}(x,y)\rightarrow E_{j,i}(y,x))\Big) \text{ and }\\
&\psi:= \forall x \Big(\bigwedge_{i\in \indexSetRotation}\Big(\bigvee_{j\in \indexSetRotation}\big(\exists^{=1}y E_{i,j}(x,y)\land \bigwedge_{\substack{j'\in \indexSetRotation\\ j'\not=j}}\lnot \exists y E_{i,j'}(x,y)\big)\Big)\Big).
\end{align*}

Thus, it is sufficient to prove that $\struc{A}\models\varphi$ and $\struc{A}\models \psi$.

To prove $\struc{A}\models\varphi$, assume towards a contradiction that there are $a,b\in \univ{A}$ such that for some pair $i,j\in \indexSetRotation$, we have that $(a,b)\in \rel{E_{i,j}}{\struc{A}}$, but $(b,a)\notin \rel{E_{j,i}}{\struc{A}}$. By construction of  $ \classStruc{P}_{\rho_k}$, there is a structure $\other{\struc{A}}\models \varphi_{\zigzag}$ and $\other{a}\in \univ{\other{A}}$ such that $(\mathcal{N}_2^{\struc{A}}(a),a)\cong (\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. Assume $f$ is an isomorphism from $(\mathcal{N}_2^{\struc{A}}(a),a)$ to  $(\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. Note that $f(b)$ is defined since $b$ is in the $2$-neighbourhood of $a$. Furthermore since $f$ is an isomorphism, $(a,b)\in \rel{E_{i,j}}{\struc{A}}$ implies $(\other{a},f(b))\in \rel{E_{i,j}}{\other{\struc{A}}}$, and $(b,a)\notin \rel{E_{j,i}}{\struc{A}}$ implies $(f(b),\other{a})\notin \rel{E_{j,i}}{\other{\struc{A}}}$. Hence $\other{\struc{A}}\not\models \varphi$, which contradicts $\other{\struc{A}}\models \varphi_{\operatorname{rotationMap}}$.

To prove $\struc{A}\models\psi$, assume towards a contradiction that there is an $a\in \univ{A}$ and $i\in \indexSetRotation$ such that  $\struc{A}\not\models \exists^{=1}y E_{i,j}(a,y)\land \bigwedge_{\substack{j'\in \indexSetRotation\\ j'\not=j}}\lnot \exists y E_{i,j'}(a,y)$ for every  $j\in \indexSetRotation$. We know that there is a structure $\other{\struc{A}}\models \varphi_{\zigzag}$ and $\other{a}\in \univ{\other{A}}$ such that $(\mathcal{N}_2^{\struc{A}}(a),a)\cong (\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. Let $f$ be an isomorphism from $(\mathcal{N}_2^{\struc{A}}(a),a)$ to $(\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. Since $\other{\struc{A}}\models \psi$, there must be $j\in \indexSetRotation$ such that $\other{\struc{A}}\models \exists^{=1}y E_{i,j}(\other{a},y)\land \bigwedge_{\substack{j'\in \indexSetRotation\\ j'\not=j}}\lnot \exists y E_{i,j'}(\other{a},y)$. Hence there must be $\other{b}\in \univ{\other{A}}$ such that $(\other{a},\other{b})\in \rel{E_{i,j}}{\other{\struc{A}}}$, which implies that $(a,f^{-1}(\other{b}))\in \rel{E_{i,j}}{\struc{A}}$. Since we assumed that $\struc{A}\not\models \exists^{=1}y E_{i,j}(a,y)\land \bigwedge_{\substack{j'\in \indexSetRotation\\ j'\not=j}}\lnot \exists y E_{i,j'}(a,y)$, there must be either $b\not=f^{-1}(\other{b})$ with $(a,b)\in \rel{E_{i,j}}{\struc{A}}$, or there must be $j'\in \indexSetRotation$, $j'\not=j$ and $b'\in \univ{A}$ such that $(a,b')\in \rel{E_{i,j'}}{\struc{A}}$.  In the first case  $(\other{a},f(b))\in \rel{E_{i,j}}{\other{\struc{A}}}$, since $f$ is an isomorphism. But then $\other{\struc{A}}\not\models \exists^{=1}y E_{i,j}(\other{a},y)$, which is a contradiction. In the second case, we get that $(\other{a},f(b'))\in \rel{E_{i,j'}}{\other{\struc{A}}}$. But then $\other{\struc{A}}\not\models \bigwedge_{\substack{j'\in \indexSetRotation\\ j'\not=j}}\lnot \exists y E_{i,j'}(\other{a},y)$, which is a contradiction. Hence $\struc{A}\models \varphi \land \psi$.

Every structure $\struc{A}\in \bigcup_{1\leq k \leq m}\classStruc{P}_{\rho_k}\setminus \{\struc{A}_{\emptyset}\}$ satisfies $\varphi_{\operatorname{base}}$.

Let $\struc{A}\in \bigcup_{1\leq k \leq m}\classStruc{P}_{\rho_k}\setminus \{\struc{A}_{\emptyset}\}$. Then there is a $k\in \{1,\dots,m\}$ such that $\struc{A}\in \classStruc{P}_{\rho_k}$.

By definition, $\varphi_{\operatorname{base}}:=\forall x  \big(\varphi_{\operatorname{root}}(x)\rightarrow (\varphi(x)\land\psi(x))\big)$, where

\begin{align*}
\varphi(x):=&\bigwedge_{i,j\in \indexSetRotation}\Big(E_{i,j}(x,x)\land \forall y \Big(x\not= y\rightarrow \big(\lnot E_{i,j}(x,y)\land \lnot E_{i,j}(y,x)\big)\Big)\Big)\text{ and }\\
\psi(x):=& \bigwedge_{\substack{ \rot_{H^2}(k,i)=(k',i')\\k,k'\in \indexSetH\\i,i'\in \indexSetRotation }}\exists y \exists y'\big(F_k(x,y)\land F_{k'}(x,y')\land E_{i,i'}(y,y')\big).
\end{align*}

Thus, it is sufficient to prove that $\struc{A}\models \varphi(a)$ and $\struc{A}\models \psi(a)$ for every $a\in \univ{A}$ for which $\struc{A}\models \varphi_{\operatorname{root}}(a)$. Therefore assume $a\in \univ{A}$ is any element such that $\struc{A}\models \varphi_{\operatorname{root}}(a)$. Because $\struc{A}\in \classStruc{P}_{\rho_k}$ there is an $i\in I_{k}$ such that $(\mathcal{N}_2^{\struc{A}}(a),a)\in \tau_{d,2,\sigma}^i$. Then by definition there is a structure $\other{\struc{A}}\models \varphi_{\zigzag}$ and $\other{a}\in \univ{\other{A}}$ such that $(\mathcal{N}_2^{\struc{A}}(a),a)\cong (\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$.  Let $f$ be an isomorphism from $(\mathcal{N}_2^{\struc{A}}(a),a)$ to $(\mathcal{N}_2^{\other{\struc{A}}}(\other{a}),\other{a})$. Assume that there is an element $\other{b}\in \univ{\other{A}}$ such that $(\other{b},\other{a})\in \rel{F}{\other{\struc{A}}}$. Since $f$ is an isomorphism and $\other{b}\in N_2^{\other{\struc{A}}}(\other{a})$ we get that $(f^{-1}(\other{b}),a)\in \rel{F}{\struc{A}}$ which contradicts that $\struc{A}\models\varphi_{\operatorname{root}}(a)$ as $\varphi_{\operatorname{root}}(x):= \forall y \lnot F(y,x)$. Hence there is no element  $\other{b}\in \univ{\other{A}}$ such that $(\other{b},\other{a})\in \rel{F}{\other{\struc{A}}}$ which implies that $\other{\struc{A}}\models \varphi_{\operatorname{root}}(\other{a})$. But since $\other{\struc{A}}\models \varphi_{\zigzag}$ we have that $\other{\struc{A}}\models \varphi_{\operatorname{base}}$ and hence $\other{\struc{A}}\models \varphi(\other{a})$ and $\other{\struc{A}}\models \psi(\other{a})$.

To prove $\struc{A}\models\varphi(a)$ first observe that $(a,a)\in \rel{E_{i,j}}{\struc{A}}$ for every $i,j\in \indexSetRotation$ since $\other{\struc{A}}\models \varphi(\other{a})$ implies that $(\other{a},\other{a})\in \rel{E_{i,j}}{\other{\struc{A}}}$ for every $i,j\in \indexSetRotation$ and $f$ is an isomorphism mapping $a$ onto $\other{a}$. Assume that there is an element $b\in \univ{A}$, $b\not=a$ and indices $i,j\in \indexSetRotation$ such that either $(a,b)\in \rel{E_{i,j}}{\struc{A}}$ or $(b,a)\in \rel{E_{i,j}}{\struc{A}}$. Since $b\in N_2^{\struc{A}}(a)$ and $f$ is an isomorphism we get that $f(b)\not=f(a)=\other{a}$ and either $(\other{a},f(b))\in \rel{E_{i,j}}{\other{\struc{A}}}$ or $(f(b),\other{a})\in \rel{E_{i,j}}{\other{\struc{A}}}$. But this contradicts $\other{\struc{A}}\models \varphi(\other{a})$ and hence $\struc{A}\models \varphi(a)$.

We now prove that $\struc{A}\models \psi(a)$. Let $k,k'\in \indexSetH$ and $i,i'\in \indexSetRotation$ such that $\rot_{H^2}(k,i)=(k',i')$. Since $\other{\struc{A}}\models \psi(\other{a})$ there must be elements $\other{b},\other{b}'\in \univ{\other{A}}$ such that $(\other{a},\other{b})\in \rel{F_k}{\other{\struc{A}}}$, $(\other{a},\other{b}')\in \rel{F_{k'}}{\other{\struc{A}}}$ and $(\other{b},\other{b}')\in \rel{E_{i,i'}}{\other{\struc{A}}}$. But since $\other{b},\other{b}'\in N_2^{\other{\struc{A}}}(\other{a})$ we get that $f^{-1}(\other{b})$ and $f^{-1}(\other{b}')$ are defined  and since $f$ is an isomorphism we get that $(a,f^{-1}(\other{b}))\in \rel{F_k}{\struc{A}}$, $(a,f^{-1}(\other{b}'))\in \rel{F_{k'}}{\struc{A}}$ and $(f^{-1}(\other{b}),f^{-1}(\other{b}'))\in \rel{E_{i,i'}}{\struc{A}}$. Hence $\struc{A}\models \exists y \exists y'\big(F_k(a,y)\land F_{k'}(a,y')\land E_{i,i'}(y,y')$ for any $k,k'\in \indexSetH$ and $i,i'\in \indexSetRotation$ such that $\rot_{H^2}(k,i)=(k',i')$ which implies that $\struc{A}\models \psi(a)$.

§ ACKNOWLEDGMENTS

We thank Sebastian Ordyniak for inspiring discussions.
The second author thanks Michał Pilipczuk and Pierre Simon for inspiring discussions at the docCourse on Sparsity in Prague 2018.

[1]
I. Adler and F. Harwath, Property testing for bounded degree
databases, in 35th Symposium on Theoretical Aspects of Computer Science,
STACS 2018, February 28 to March 3, 2018, Caen, France, 2018,
pp. 6:1–6:14.

[2]
I. Adler, N. Köhler, and P. Peng, GSF-locality is not
sufficient for proximity-oblivious testing, in 36th Computational Complexity
Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual
Conference), V. Kabanets, ed., vol. 200 of LIPIcs, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2021, pp. 34:1–34:27,

[3]
I. Adler, N. Köhler, and P. Peng, On testability of
first-order properties in bounded-degree graphs, in Proceedings of the 2021
ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference,
January 10 - 13, 2021, D. Marx, ed., SIAM, 2021, pp. 1578–1597,

[4]
N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Efficient
testing of large graphs, Combinatorica, 20 (2000), pp. 451–476.
Preliminary version in FOCS'99.

[5]
N. Alon, E. Fischer, I. Newman, and A. Shapira, A combinatorial
characterization of the testable graph properties: it's all about
regularity, SIAM Journal on Computing, 39 (2009), pp. 143–167.

[6]
N. Alon and V. D. Milman, $\lambda$1, isoperimetric inequalities for
graphs, and superconcentrators, Journal of Combinatorial Theory, Series B,
38 (1985), pp. 73–88.

[7]
I. Benjamini, O. Schramm, and A. Shapira, Every minor-closed
property of sparse graphs is testable, Advances in mathematics, 223 (2010),
pp. 2200–2218.

[8]
M. Blum, M. Luby, and R. Rubinfeld, Self-testing/correcting with
applications to numerical problems, Journal of computer and system sciences,
47 (1993), pp. 549–595.

[9]
B. Bollig and D. Kuske, An optimal construction of hanf sentences,
Journal of Applied Logic, 10 (2012), pp. 179–186,

[10]
H. Chen and Y. Yoshida, Testability of homomorphism inadmissibility:
Property testing meets database theory, in Proceedings of the 38th ACM
SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019,
pp. 365–382.

[11]
A. Czumaj, P. Peng, and C. Sohler, Relating two property testing
models for bounded degree directed graphs, in Proceedings of the 48th Annual
ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA,
USA, June 18-21, 2016, 2016, pp. 1033–1045.

[12]
R. Diestel, Graph Theory, 4th Edition, vol. 173 of Graduate texts
in mathematics, Springer, 2012.

[13]
J. Dodziuk, Difference equations, isoperimetric inequality and
transience of certain random walks, Transactions of the American
Mathematical Society, 284 (1984), pp. 787–794.

[14]
H. Ebbinghaus and J. Flum, Finite model theory, Perspectives in
Mathematical Logic, Springer, 1995.

[15]
H. Fichtenberger, P. Peng, and C. Sohler, Every testable (infinite)
property of bounded-degree graphs contains an infinite hyperfinite
subproperty, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on
Discrete Algorithms, Society for Industrial and Applied Mathematics, 2019,
pp. 714–726.

[16]
S. Forster, D. Nanongkai, T. Saranurak, L. Yang, and
S. Yingchareonthawornchai, Computing and testing small connectivity in
near-linear time and queries via fast local cut algorithms, SODA,  (2020).

[17]
H. Gaifman, On local and non-local properties, 1982.

[18]
O. Goldreich, Introduction to property testing, Cambridge
University Press, 2017.

[19]
O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its
connection to learning and approximation, Journal of the ACM (JACM), 45
(1998), pp. 653–750.

[20]
O. Goldreich and T. Kaufman, Proximity oblivious testing and the
role of invariances, in Studies in Complexity and Cryptography. Miscellanea
on the Interplay between Randomness and Computation, Springer, 2011,
pp. 173–190.

[21]
O. Goldreich and D. Ron, Property testing in bounded degree graphs,
Algorithmica, 32 (2002), pp. 302–343,

[22]
O. Goldreich and D. Ron, On proximity-oblivious testing, SIAM
Journal on Computing, 40 (2011), pp. 534–566.

[23]
O. Goldreich and I. Shinkar, Two-sided error proximity oblivious
testing, Random Structures & Algorithms, 48 (2016), pp. 341–383.

[24]
W. Hanf, The Theory of Models, North Holland, 1965,
ch. Model-theoretic methods in the study of elementary logic, pp. 132–145.

[25]
A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak, Local graph
partitions for approximation and testing, in 2009 50th Annual IEEE Symposium
on Foundations of Computer Science, IEEE, 2009, pp. 22–31.

[26]
S. Hoory, N. Linial, and A. Wigderson, Expander graphs and their
applications, BULL. AMER. MATH. SOC., 43 (2006), pp. 439–561.

[27]
H. Ito, A. Khoury, and I. Newman, On the characterization of
$1$-sided error strongly-testable graph properties for bounded-degree
graphs, (to appear) Journal of Computational Complexity. arXiv:1909.09984,

[28]
K.-i. Kawarabayashi and Y. Yoshida, Testing subdivision-freeness:
property testing meets structural graph theory, in Proceedings of the
forty-fifth annual ACM symposium on Theory of computing, ACM, 2013,
pp. 437–446.

[29]
A. Kumar, C. Seshadhri, and A. Stolman, Random walks and forbidden
minors ii: a poly (d $\varepsilon$-1)-query tester for minor-closed
properties of bounded degree graphs, in Proceedings of the 51st Annual ACM
SIGACT Symposium on Theory of Computing, 2019, pp. 559–567.

[30]
L. Lovász, Large Networks and Graph Limits, vol. 60 of
Colloquium Publications, American Mathematical Society, 2012.

[31]
I. Newman and C. Sohler, Every property of hyperfinite graphs is
testable, SIAM Journal on Computing, 42 (2013), pp. 1095–1112.

[32]
L. S. R. Fagin and M. Vardi, On monadic np vs. monadic co-np,
Information and Computation, 120 (1995), pp. 78–92.

[33]
O. Reingold, S. Vadhan, and A. Wigderson, Entropy waves, the zig-zag
graph product, and new constant-degree expanders and extractors, in Annals
of Mathematics, 2000, pp. 157–187.

[34]
R. Rubinfeld and M. Sudan, Robust characterizations of polynomials
with applications to program testing, SIAM Journal on Computing, 25 (1996),
pp. 252–271.

[35]
Y. Yoshida and H. Ito, Property testing on $k$-vertex-connectivity
of graphs, Algorithmica, 62 (2012), pp. 701–712.

[type=symbols,title=List of Notation]

[description=the set of natural numbers including $0$]NN$\mathbb{N}$
[description=the set of all positive natural numbers]NNP$\Npos$

[description=the set $\{0,\dots,n-1\}$][n]$[n]$

[description=disjoint union]DU$\sqcup$
[description=symmetric difference]SD$\triangle$

[description=the neighbourhood of fixed radius $r$ around $x$, up to isomorphism]NBI$\tau_r(x)$

[description=asymtotic upper-bounds]big-O$\mathcal{O}(\cdot), o(\cdot)$

[description=zig-zag product]zz$\zigzag$

[description=expansion ratio of $G$]exp$h(G)$
[description=edges crossing $S$ and $T$ in $G$]croEd$\langle S,T\rangle_G$

[description=signature with one binary relation symbol $E$]sg$\sigma_{\textrm{graph}}$
[description=degree of vertex $v$ in $G$]deg$\deg_G(v)$
[description=distance between two vertices $v$ and $w$ in $A$]dist$\dist_A(v,w)$
[description=distance between structure $A$ and property $\classStruc{P}$]distSP$\dist(A,\classStruc{P})$
[description=rotation map of $G$]rot$\rot_{G}$

[description=the $(u,v)$ entry of the normalised adjacency matrix $M$ of $G$]nam$M_{u,v}$

[description=substracture of $A$ induced by $S$]induce$A[S]$
[description=the $r$-neighborhood of $a$ in structure $A$]rNBH$N_r^A(a)$

[description=arity of relation $R$]relation$\ar(R)$
[description=class of graphs of bounded degree $d$]CCn$\mathcal{C}_d$
[description=class of $\sigma$-structures of bounded degree $d$]Cn$\classStruc{C}_{\sigma,d}$
[description=property defined by formula $\varphi$]PPhi$\classStruc{P}_\phi$

[description=prefix classes with $i-1$ quantifier alterations]PC$\Sigma_i$, $\Pi_i$, $\Delta_i$
[description=is a model of]models$\models$
[description=equivalence of FO-formulas]equiv$\equiv$
[description=equivalence of FO-formulas on structures of bounded degree $d$]dEquiv$\equiv_d$
[description=logical negation, conjunction, disjunction, implication and biimplication]l$\lnot$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$
[description=existential and universal quantifier]quant$\exists$, $\forall$

[description=answer to query $q$ to structure $\mathcal{A}$]query$\operatorname{ans}_{\mathcal{A}}(q)$
[description=binary relation symbols for $i,j\in [D]^2$ and $k\in ([D]^2)^2$]binary$E_{i,j}$, $F_{k}$, $R$, $L_k$

[description=underlying graph of a model $\struc{A}$ of $\varphi_{\zigzag}$]underlying$\underlyingGraph{\struc{A}}$

[description=the formula definded in Section <ref> whose underlying graphs are expanders ]expander$\varphi_{\zigzag}$

[description=a set of models of some sentence in $\Sigma_2$ ]modelset$\mathfrak{M}$

[description=a maximal set of pairwise non-isomorphic structures in $\classStruc{C}_{\sigma,d}$]maximal$\mathfrak{H}$

[description=a conjunction of atomic (resp. negated) formulas containing both variables from tuples $\overline{x}$ and $\overline{y}$]positive$\operatorname{pos}^i(\overline{x},\overline{y}),\operatorname{neg}^i(\overline{x},\overline{y})$

[description=the number of maximal $i$-cliques containing $v$]maxcl$\maxcl^G(v,i)$

[description=the set of maximal cliques in $G$]setclique$\setOfMaxCliques$

[description=the $r$-type distribution of  $\struc{A}$]rho$\rho_{\struc{A},r}$

[description=the sampling distance of depth $r$ between two $\sigma$-structures $\struc{A}$ and $\struc{B}$ ]samplingdist$\delta_{\odot}^r(\struc{A},\struc{B})$

[description=Hanf normal form]HNFHNF
[description=proximity oblivious tester]POTPOT
[description=generalised subgraph freeness]GSFGSF