\newcommand{\tup}[1]{\bar{#1}}
\newcommand{\adj}{\mathsf{adj}}

\section{From powers to interpretations}\label{sec:interpretations}

We now use the results obtained in the previous sections to prove a generalization to the setting of classes obtained from nowhere dense ones using (one-dimensional) First Order interpretations. 
That is, we prove Theorem~\ref{thm:interpretations}.
Note that the statement of this result does not involve the notion of $\FO$ interpretations explicitly, but a reader familiar with this concept should see a connection.
We refer to the work of Gajarsk\'y et al.~\cite{GajarskyKNMPST18} for a broader discussion of $\FO$ interpretations and their relation with the notions of sparsity.

\medskip

We assume basic familiarity with the First Order logic ($\FO$) on undirected graphs. 
Recall that in this logic, variables correspond to single vertices and formulas are built recursively from smaller subformulas using the following constructs: existential and universal quantification, and standard boolean
connectives. The basic ({\em{atomic}}) formulas are of the form $x=y$ and $\adj(x,y)$; they respectively check whether vertices assigned to variables $x$ and $y$ are equal or adjacent.
For instance, for a nonnegative integer $d$, the following inductive definition gives a formula $\delta_d(x,y)$ such that $\delta_d(u,v)$ is true in a graph $G$ if and only if \(\dist_G(u, v) \le d\).
\begin{eqnarray*}
 \delta_0(x,y) & \coloneqq & (x=y)\\
 \delta_d(x,y) & \coloneqq & \delta_{d-1}(x,y)\vee \\
 & & \left[\exists_{z_1}\ldots\exists_{z_{d-1}}\ \adj(x,z_1)\wedge \adj(z_1,z_2)\wedge\ldots \wedge \adj(z_{d-2},z_{d-1})\wedge \adj(z_{d-1},y)\right].
\end{eqnarray*}
If $\varphi(\tup x)$ is a formula with a tuple of free variables $\tup x$ and $\tup u\colon \tup x\to V(G)$ is an evaluation of variables of $\tup x$ in a graph $G$, then we write $G\models \varphi(\tup u)$ to
denote that $\varphi$ holds in $G$ when each variable of $\tup x$ is evaluated as prescribed by $\tup u$.

The main tool that will replace results on neighborhood complexity (Theorem~\ref{thm:distance-profile-complexity}) are the bounds on the number of {\em{$\FO$-types}} in nowhere dense classes, 
which were recently proved by Pilipczuk et al.~\cite{PilipczukST18a}.
We refer to this work for a broader discussion, while we will rely on the following corollary, which follows easily from~\cite[Theorem~1.3 and Lemma~3.1]{PilipczukST18a}.

\begin{lemma}[\cite{PilipczukST18a}]\label{lem:types}
Let $\Cc$ be a nowhere dense class of graphs and $\varphi(x,y)$ be an $\FO$ formula with two free variables. 
Then there exist positive integers $c$ and $d$ such that for every graph $G$ in $\Cc$ and vertex subset $S\subseteq V(G)$, there exists a coloring $\lambda$ of vertices of $G$ with at most $c\cdot |S|^c$ colors such that the following holds:
for every triple of vertices $u,v,v'\in V(G)$ such that $\lambda(v)=\lambda(v')$ and $S$ intersects every path of length at most $d$ connecting $u$ with any of $\{v,v'\}$, we have
$$G\models \varphi(u,v)\qquad\textrm{if and only if}\qquad G\models \varphi(u,v').$$
\end{lemma}

\medskip 

We are now ready to prove Theorem~\ref{thm:interpretations}.

\begin{proof}[Proof of Theorem~\ref{thm:interpretations}]
 Let $c$ and $d$ be the constants given by Lemma~\ref{lem:types} for the class $\Cc$ and formula $\varphi(x,y)$. Let $k=|A\cup B|$ and let $\eps'$ be a positive real, to be determined later.
 Assuming that $k$ is large enough depending on $\Cc$, $d$, and $\eps'$, we may apply Lemma~\ref{lem:new-abs} to $A$ and $B$ and constants $d$ and~$\eps'$. 
 Thus, we find disjoint subsets $A_0$ and $B_0$ of $A$ and $B$, respectively, and a vertex subset $S$ such that
 \begin{itemize}
  \item $|A_0|\geq (1-\eps')|A|$, $|B_0|\geq |B|/k^{\eps'}$, and $|S|\leq k^{\eps'}$; and
  \item for every $a\in A_0$ and $b\in B_0$, every path of length at most $d$ connecting $a$ and $b$ intersects~$S$.
 \end{itemize}
 Now let $\lambda$ be the coloring of vertices of $G$ provided by Lemma~\ref{lem:types}.
 Then $\lambda$ uses at most $c\cdot |S|^c\leq c\cdot k^{c\eps'}$ colors, hence there is a subset $B'\subseteq B_0$ such that $|B'|\geq \frac{|B|}{c\cdot k^{(c+1)\eps'} }$ and $B'$ is monochromatic in $\lambda$.
 By Lemma~\ref{lem:types} and the second point above, for every $a\in A_0$ we either have $G\models \varphi(a,b)$ for all $b\in B'$, or $G\models \neg \varphi(a,b)$ for all $b\in B'$.
 Hence, we may set $A'=A_0$.
 It remains to note that by choosing $k_0$ and $\eps'<\frac{\eps}{c+1}$ appropriately, we have $|A'|\geq \left(1-\eps\right) |A|$ and $|B'|\geq |B|/k^{\eps}$.
\end{proof}
{"config": "arxiv", "file": "2006.01500/interpretations.tex"}