


\subsection{Definitions}

We first recall the definition of the splitter game due to Grohe et al.~\cite{GroheKS14}. Fix some graph $G$ and $\ell,m,d\in \mathbb N$. The {\em{$(\ell,m,d)$-splitter game}} on $G$ is a game played by two players: connector and splitter. The game proceeds in $\ell$ rounds. At the beginning of round $i+1$, the game is played on a subgraph $G_i$ of $G$ that we shall call the {\em{arena}}; the game starts with $G_0=G$. In round $i+1$, connector first picks an arbitrary vertex $v_{i+1}\in V(G_i)$ of the arena. Then, splitter chooses a subset $W_{i+1}\subseteq V(G_i)$ of size at most $m$. The arena gets trimmed to $G_{i+1}=G_i[N^d_{G_i}[v_{i+1}]\setminus W_{i+1}]$; that is, in the next round we consider only vertices that are at distance at most $d$ in $G_i$ from the vertex picked by connector, and moreover the vertices $W_{i+1}$ chosen by splitter are removed. Splitter wins the game if within $\ell$ rounds the arena becomes empty, i.e., $G_{i+1}$ is an empty graph for some $i\leq \ell$, and connector wins otherwise. 

A {\em{winning strategy}} for connector is simply a function $\sigma$ that maps sequences of the form $(v_1,W_1,v_2,W_2,\ldots,v_i,W_i)$ to vertices of $G$ such that (i) $\sigma(v_1,W_1,v_2,W_2,\ldots,v_i,W_i)$ is a valid move $v_{i+1}$ for connector; and (ii) by playing $v_{i+1}=\sigma(v_1,W_1,v_2,W_2,\ldots,v_i,W_i)$ in each round, where $v_1,v_2,\ldots,v_i$ and $W_1,W_2,\ldots,W_i$ are previous moves of connector and splitter, respectively, connector wins the $(\ell,m,d)$-splitter game. We similarly define winning strategies for splitter as functions $\tau$ the map sequences of the form $(v_1,W_1,v_2,W_2,\ldots,v_i,W_i,v_{i+1})$ to sets $W_{i+1}\subseteq V(G)$.

We will say that a class $\mathcal C$ of finite graphs is {\em{winning for splitter}} if for every $d\in \mathbb N$, there exist $\ell,m\in \mathbb N$ such that splitter has a winning strategy in the $(\ell,m,d)$-splitter game on every graph from $G$. Grohe et al.~\cite{GroheKS14} proved that $\mathcal C$ is winning for splitter if and only if it is nowhere dense. Our goal now is to give an alternative proof of this result by defining the limit variant of the splitter game, proving its equivalence with the standard variant by the means of Łoś's theorem, and then showing that splitter wins in the limit game if and only if the graph class is limit nowhere-dense.

Fix some graph $G$ and $d\in \mathbb N$. The {\em{limit $d$-splitter game}} has the same rules as the standard $(\ell,m,d)$-splitter game apart from the following differences:
\begin{itemize}
\item In splitter's moves, we require that $W_{i+1}$ is finite (instead of bounding its size by $m$).
\item Splitter wins if the arena becomes empty after a finite number of rounds (instead of after at most $\ell$ rounds).
\end{itemize}
The definitions of strategies for splitter and connector are the same as previously. We say that a class $\mathcal C$ of finite graphs is {\em{limit winning for splitter}} if for every $d\in \mathbb N$, splitter has a winning strategy in the limit $d$-splitter game on every graph from $\mathcal C^\star$.

The following simple observation shows that in fact we can restrict ourselves to the game, where splitter always pick singleton sets $W_i$.

\begin{lemma}\label{lem:one-move}
Let $G$ be a graph. If splitter has a winning strategy in the $(\ell,m,d)$-splitter game on $G$, then she has also a winning strategy in the $(\ell\cdot m,1,d)$-splitter game on $G$. If splitter has a winning strategy in the limit $d$-splitter game on $G$, then she has also a strategy in this game where in each round she picks $W_i$ of size $1$.
\end{lemma}

\begin{proof}
Both claims follow from an observation that instead of choosing a set $W$ in some round, splitter can use at most $|W|$ consecutive rounds to choose the vertices of $W$ one by one. The intermediate moves of connector can be ignored because they can only trim further the arena.
\end{proof}

Since for $\ell,m,d\in \mathbb N$ and a finite graph $G$, the $(\ell,m,d)$-splitter game on $G$ is finite, the fact that splitter does not have a winning strategy in this game implies that connector has one. This statement, however, is not obvious for the limit game. Even though it is not essential for our later reasonings, we state and prove it for the sake of completeness.

\begin{proposition}\label{thm:determinacy}
Let $G$ be a (possibly infinite) graph and let $d\in \mathbb N$. Then splitter has a winning strategy in the $d$-splitter game on $G$ if and only if connector does not have a winning strategy in this game.
\end{proposition}
\begin{proof}
The $d$-splitter game on $G$ can be regarded as a Gale-Stewart game on $A:=P_{\text{fin}}(V(G))$, the set of finite subsets of $V(G)$, with an open winning condition. Namely, the players alternately choose consecutive entries of a sequence from $A^\omega$. Some moves are invalid for the players: for connector, it is invalid to choose a subset of cardinality different than $1$, and for both players it is invalid to choose any vertex outside the current arena. We assume that if some player performs an invalid move, then the game continues indefinitely with this player being the losing one at the end. Let $X_C$ and $X_S=A^\omega\setminus X_C$ be the sets of all sequences from $A^\omega$ that encode the plays winning for connector and splitter, respectively. Then $X_S$ is the set of all the infinite sequences where the first invalid move was performed by connector. It follows that $X_S$ is open in the product topology on $A^\omega$. Hence, the claim follows from Martin's theorem~\cite{Martin75} that states that Gale-Stewart games with a Borel winning condition are determined.
\end{proof}

\subsection{Linking the standard and limit games}

We first prove a simple auxiliary result.

\begin{lemma}\label{lem:fo-winning}
For every $\ell,m,d\in \mathbb N$, there exists a first-order sentence $\phi_{\ell,m,d}$ such that, for any graph $G$, $G\models \phi_{\ell,m,d}$ iff connector wins in the $(\ell,m,d)$-splitter game on $G$.
\end{lemma}
\begin{proof}
We simply quantify the existence of the strategy for connector. That is, $\phi_{\ell,m,d}$ has $2\ell$ alternating blocks of quantification, where connector's moves are quantified existentially as single vertices $v_i$, and splitter's moves are quantified universally as $m$ variables $w^1_i,w^2_i,\ldots,w^m_i$ (not required to be distinct). To verify that the quantified variables form a valid play of the $(\ell,m,d)$-splitter game on $G$, and at the end the arena is non-empty, we use formulas $\psi_i$ for $i=0,1,\ldots,\ell$ with the following syntax and semantics: Formula $\psi_i$ has free variables $ \{v_j\}_{j\leq i}\cup \{w^q_j\}_{q\leq m,\, j\leq i}\cup \{x\}$, and is true if and only if $x$ belongs to arena $G_i$ defined by the previous moves $\{v_j\}_{j\leq i}\cup \{w^q_j\}_{q\leq m,\, j\leq i}$. We can put $\psi_0=\top$, and $\psi_{i+1}$ can be defined inductively using $\psi_i$ as follows: $x$ belongs to $G_{i}$, $x$ is different from all $\{w^q_{i+1}\}_{q\leq m}$, and moreover there is a path in $G_i$ of length at most $d$ from $x$ to $v_{i+1}$.
\end{proof}

\begin{lemma}\label{lem:game}
Let $\mathcal C$ be a class of finite graphs. Then $\mathcal C$ is winning for splitter if and only if $\mathcal C$ is limit winning for splitter.
\end{lemma}
\begin{proof}
Suppose first that $\mathcal C$ is winning for splitter. Fix any $d\in \mathbb N$. Then there exist $\ell,m\in \mathbb N$ such that splitter wins in the $(\ell,m,d)$-splitter game on each graph of $\mathcal C$. We claim that splitter wins also in the $(\ell,m,d)$-splitter game on each graph of $\mathcal C^\star$, so in particular also in the limit $d$-splitter game on each graph of $\mathcal C^\star$. Indeed, take any graph $H\in \mathcal C^\star$; then $H$ is a subgraph of a graph of the form $G^\star = \prod_\ultra G_n$ for some sequence $(G_n)_{n\in \omega}$ of graphs from $\mathcal C$. To show that splitter wins in the $(\ell,m,d)$-splitter game on $H$, it suffices to show that she wins in this game on $G^\star$, because then the same strategy trimmed to $V(H)$ will work on $H$. However, this follows immediately from Lemma~\ref{lem:fo-winning} and Łoś's theorem: we have that $G_n\models \neg \phi_{\ell,m,d}$ for all $n\in \mathbb N$, so by Łoś's theorem also $G^\star\models \neg \phi_{\ell,m,d}$.

Suppose now that $\mathcal C$ is limit winning for splitter. For the sake of contradiction, suppose $\mathcal C$ is not winning for splitter. This implies that there exist $d\in \mathbb N$ and a sequence of graphs $(G_n)_{n\in \mathbb N}$ such that, for each $n\in \mathbb N$, connector has a winning strategy $\sigma_n$ in the $(n,1,d)$-splitter game on $G_n$. Let $G^\star=\prod_\ultra G_n$. Using $(\sigma_n)_{n\in \mathbb N}$, we will construct a strategy $\sigma^\star$ for connector in the limit $d$-splitter game on $G^\star$ that wins with all the strategies of splitter, where splitter uses only singleton sets $W_i$. By Lemma~\ref{lem:one-move}, this will be a contradiction with $\mathcal C$ being limit winning for splitter.

Let $(\seq v_1,\seq w_1,\seq v_2,\seq w_2,\ldots,\seq v_i,\seq w_i)$ be the sequence of connector's and splitter's moves during the first $i$ rounds of the limit $d$-splitter game on $G^{\star}$. Here, we assume that splitter always answers with singleton sets, so we denote the $i$-th move of splitter as $\set{\seq w_i}$. Moreover, we suppose that each $\seq v_j$ and $\seq w_j$ is an arbitrarily chosen representative of its equivalence class with respect to $\sim_\mathcal{U}$. We denote $\seq v_j=(\seq v_{j,n})_{n\in \mathbb N}$, where $\seq v_{j,n}\in V(G_n)$ for all $n\in \mathbb N$, and similarly for $\seq w_j$. 

For $n\in \mathbb N$ and $i<n$, let 
$$\seq v_{i+1,n}=\sigma_n(\seq v_{1,n},\seq w_{1,n},\seq v_{2,n},\seq w_{2,n},\ldots,\seq v_{i,n},\seq w_{i,n}).$$
For $i\geq n$, define $\seq v_{i+1,n}$ to be an arbitrary vertex of $G_n$. Let us define 
$$\seq v_{i+1}=[(\seq v_{i+1,n})_{n\in \mathbb N}]_{\sim_\mathcal{U}}.$$
Note that the definition of $\seq v_{i+1}$ does not depend on the particular choice of representatives $\seq v_1,\seq w_1,\seq v_2,\seq w_2,\ldots,\seq v_i,\seq w_i$. Put
$$\sigma^\star(\seq v_1,\seq w_1,\seq v_2,\seq w_2,\ldots,\seq v_i,\seq w_i)=\seq v_{i+1}.$$
It remains to prove that $\sigma^\star$ indeed is a strategy that guarantees that connector wins against any strategy of splitter that uses only singleton sets. For this, we need to show that each move $\seq v_{i+1}$ of connector belongs to the arena $G_{i}$, for all $i\in \mathbb N$. 

To this end, define a first-order formula $\psi_i$ for $i\in \mathbb N$ as in the proof of Lemma~\ref{lem:fo-winning}: $\psi_i$ has free variables $\{v_1,w_1,\ldots,v_i,w_i,x\}$ and is true in $G,v_1,w_1,\ldots,v_i,w_i,x$ if and only if $x$ is in arena $G_i$ defined by previous moves $v_1,w_1,\ldots,v_i,w_i$ of connector and splitter. We can put $\psi_0=\top$, and define $\psi_{i+1}$ using $\psi_i$ inductively as follows: $x$ belongs to arena $G_{i}$, is different from $w_{i+1}$, and there is a path in $G_i$ of length at most $d$ from $x$ to $v_{i+1}$. By the definition of $\sigma_n$, we have that 
$$G_n,\seq v_{1,n},\seq w_{1,n},\seq v_{2,n},\seq w_{2,n},\ldots,\seq v_{i,n},\seq w_{i,n},\seq v_{i+1,n}\models \psi_{i}$$
for all $0\leq i<n$. Therefore, for a fixed $i\in \mathbb N$ and variable $n\in \mathbb N$, the above holds $\meas$-almost-everywhere\xspace. From Łoś's theorem we thus infer that
$$G^\star,\seq v_1,\seq w_1,\seq v_2,\seq w_2,\ldots,\seq v_{i},\seq w_{i},\seq v_{i+1}\models \psi_i$$
for all $i\in \mathbb N$. Hence, for all $i\in \mathbb N$ the $(i+1)$-st move of connector is always in the arena $G_{i}$, and thus is valid.
\end{proof}

We remark that by applying the proof of Lemma~\ref{lem:game} in both directions, and then Lemma~\ref{lem:one-move}, we obtain the following corollary: If splitter wins in the limit $d$-splitter game on every graph from $\mathcal C^\star$, then there is a constant $\ell\in \mathbb N$ such that she wins in the $(\ell,1,d)$-splitter game on every graph from $\mathcal C^\star$. In other words, the lengths of the game can be bounded universally.

\subsection{Equivalence with nowhere-denseness and quasi-wideness}

The proofs in this section are inspired by the analogous proofs for the finite variants, due to Grohe et al.~\cite{GroheKS14}.

\begin{lemma}\label{lem:qw-gm}
If a class of finite graphs $\mathcal C$ is uniformly limit quasi-wide, then $\mathcal C$ is limit winning for splitter.
\end{lemma}
\begin{proof}
Fix a graph $G\in \mathcal C^\star$ and $d\in \mathbb N$. We give a winning strategy $\tau$ for splitter in the limit $d$-splitter game on $G$. Suppose $(v_1,W_1,v_2,W_2,\ldots,v_{i-1},W_{i-1},v_i)$ were the previously performed moves in the game. Since connector's move $v_i$ is within the arena $G_{i-1}$ and the arenas in the game form a chain in the subgraph order, for each $1\leq j<i$ there exists a path $P_{j,i}$ in arena $G_{j-1}$ that has endpoints $v_j$ and $v_i$, and length at most $d$. Then splitter answers with move $W_i:=(\{v_i\}\cup \bigcup_{0\leq j<i} V(P_{j,i}))\cap V(G_{i-1})$; note that thus $W_i$ is finite and contains $v_i$.

Suppose that this strategy is not winning for splitter, that is, there exists an infinite sequence $(v_1,v_2,\ldots)$ of connector's moves that are always within the arena. Since $v_i\in W_i$ for each $i=1,2,\ldots$, all $v_i$-s are pairwise different. Let $M=\{v_1,v_2,\ldots\}$; then $M$ is infinite. As $G\in \mathcal C^\star$ and $\mathcal C$ is uniformly limit quasi-wide, there is a finite set $S\subseteq V(G)$ and infinite subset $M'\subseteq M\setminus S$ that is $d$-scattered in $G\setminus S$.

For $n\in \mathbb N$, let $R_n=\bigcup_{1\leq j<i\leq n} V(P_{j,i})$. Since $(R_n)_{n\in \mathbb N}$ is an increasing inclusion chain and $S$ is finite, there exists $N\in \mathbb N$ such that $S\cap (R_m\setminus R_N)=\emptyset$ for all $m\geq N$. Note that by the definition of the sets $W_i$ it follows that $R_N\cap V(G_N)=\emptyset$. Since $M'$ is infinite, there exist two distinct indices $m>n>N$ such that $v_{m},v_{n}\in M'$. Consider the path $P_{n,m}$. This path is entirely contained in arena $G_{m-1}\subseteq G_N$, and hence $R_N\cap V(P_{n,m})=\emptyset$. Therefore, $V(P_{n,m})\subseteq R_{m}\setminus R_N$, and hence $P_{n,m}$ does not traverse any vertex of $S$. However, $P_{n,m}$ has length at most $d$ and connects two different vertices of $M'$. This is a contradiction with $M'$ being $d$-scattered in $G\setminus S$.
\end{proof}

\begin{lemma}\label{lem:gm-tnd}
If a class of finite graphs $\mathcal C$ is limit winning for splitter, then $\mathcal C$ is limit topologically nowhere dense.
\end{lemma}
\begin{proof}
The proof is by the contraposition. Suppose there is $d\in\mathbb N$ such that $K_\omega\in \mathcal C^\star\mathop{\tilde \triangledown} d$. Since $\mathcal C^\star$ is closed under taking subgraphs by definition, we have that there is a graph $H\in \mathcal C^\star$ such that $H$ can be obtained from $K_\omega$ by subdividing each edge at most $2d$ times. We now present a strategy for connector in the limit $(4d+2)$-splitter game.

Let $A$ be the set of vertices of infinite degree in $H$. Every pair of vertices $\{u,v\}\subseteq A$ can be connected by an infinite family of internally vertex-disjoint paths of length at most $4d+2$. Hence, for every finite set $W\subseteq V(G)$, all the vertices of $A\setminus W$ belong to the same connected component of $H\setminus W$, and moreover they are pairwise at distance at most $4d+2$ in $H\setminus W$. 

The strategy for connector is as follows: in each round, pick an arbitrary vertex of $A$ that was not chosen by splitter in the previous rounds. Such a vertex always exists, because $A$ is infinite and after any finite number of rounds, only a finite number of vertices have been chosen by splitter. If connector follows this strategy, then the argument of the previous paragraph shows that all the vertices of $A$ apart from the ones chosen by splitter will be always in the arena. Hence the moves of connector will be always valid and the arena will never become empty.
\end{proof}



\section{Introduction}\label{sec:intro}
\input{intro}

\section{Preliminaries}\label{sec:prelims}
\input{prelims}

\section{Nowhere denseness}\label{sec:nowhere}
\input{nowhere}

\section{Quasi-wideness}\label{sec:quasi}
\input{quasi}

\section{Splitter game}\label{sec:game}
\input{game}

\section{Conclusions}\label{sec:conc}
\input{conclusions}

\bibliographystyle{abbrv}


\section*{\indexname}]



\subsection{Definitions}\label{sec:quasi-def}

Suppose $G$ is a graph and $d\in \mathbb N$. Recall that we say that a vertex subset $X\subseteq V(G)$ is {\em{$d$-scattered}} if for all distinct $u,v\in X$, the distance between $u$ and $v$ is larger than $2d$. Equivalently, balls $\set{N_G^d[u]}_{u\in X}$ are pairwise disjoint.
For the remainder of this section, let us fix some class $\mathcal C$ of finite graphs. 

Let $s\colon \mathbb N\to\mathbb N$ be a function. We say that $\mathcal C$ is \emph{quasi-wide (\emph{QW}) with margin $s$}  if for all $d,m\in \mathbb N$ there exists an $N\in \mathbb N$ such that the following holds: For every graph $G\in \mathcal C$ with $|V(G)|\geq N$, there exists $S\subseteq V(G)$ with $|S|\leq s(d)$ such that $G-S$ contains a $d$-scattered set of size $m$. We say that $\mathcal C$ is \emph{uniformly quasi-wide ({UQW}) with margin $s$} if for all $d,m\in \mathbb N$ there exists an $N\in \mathbb N$ such that the following holds: For every graph $G\in \mathcal C$ and every vertex subset $W\subseteq V(G)$ with $|W|\geq N$, there exists $S\subseteq V(G)$ with $|S|\leq s(d)$ such that in $G-S$ one can find a $d$-scattered set of size $m$ contained in $W$. Note that uniform quasi-wideness implies quasi-wideness with the same margin by taking $W=V(G)$. 

It is a known result of the theory of sparse graphs (cf. Theorem 8.2 of~\cite{sparsity}) that a hereditary class $\mathcal C$ of finite graphs is (uniformly) quasi-wide with some margin if and only if $\mathcal C$ is nowhere dense. The goal of this section is to give an alternative proof of this statement by proving it for the limit counterparts of (uniform) quasi-wideness, and then transferring this result to the standard definitions by the means of Łoś's theorem. 

To this end, we now give limit counterparts of the notions of (uniform) quasi-wideness. There will be four variants: the definition will either contain the uniformity requirement or not, and the margin will be either uniformly bounded by some function $s$, or just required to be finite. As we will see later, for hereditary $\mathcal C$ all these notions will be equivalent, and equivalent to (limit) nowhere denseness and standard (uniform) quasi-wideness.

We shall say that $\mathcal C$ is \emph{limit quasi-wide} (\emph{LQW}) if for every $d\in \mathbb N$ and every infinite graph $G\in \mathcal C^\star$, there exists a finite set $S\subseteq V(G)$ such that in $G\setminus S$ one can find an infinite $d$-scattered set. We shall also say that $\mathcal C$ is \emph{uniformly limit quasi-wide} (\emph{ULQW}) if for every $d\in \mathbb N$, every graph $G\in \mathcal C^\star$, and every infinite set $W\subseteq V(G)$, there exists a finite set $S\subseteq V(G)$ such that in $G\setminus S$ one can find an infinite $d$-scattered set contained in $W$.

Let $s\colon \mathbb N\to \mathbb N$ be a function. We shall say that $\mathcal C$ is \emph{strongly limit quasi-wide ({SLQW}) with margin $s$}  if for every $d\in \mathbb N$ and every infinite graph $G\in \mathcal C^\star$, there exists a set $S\subseteq V(G)$ with $|S|\leq s(d)$ such that in $G\setminus S$ one can find an infinite $d$-scattered set. We shall also say that $\mathcal C$ is \emph{strongly uniformly limit quasi-wide ({SULQW}) with margin $s$}  if for every $d\in \mathbb N$, every graph $G\in \mathcal C^\star$, and every infinite set $W\subseteq V(G)$, there exists a set $S\subseteq V(G)$ with $|S|\leq s(d)$ such that in $G\setminus S$ one can find an infinite $d$-scattered set contained in $W$.

The following implications are trivial: If $\mathcal C$ is strongly limit quasi-wide with some margin, then it is also limit quasi wide. The same holds for the uniform variants: SULQW implies UQW. By taking $W=V(G)$, we obtain that uniform limit quasi-wideness implies limit quasi-wideness, and strong uniform limit quasi-wideness with some margin $s$ implies strong limit quasi-wideness with the same margin.

\begin{comment}

$$\begin{cases}
 G\in\mathcal C \\
 |G| \geq N
 \end{cases}
 \qquad\implies\qquad
 \begin{cases}
 \exists_{S\subseteq V(G)} |S| \leq s(r)\\
 G-S \textrm{\qquad contains an $r$-scattered set of size at least $m$}
 \end{cases}
 $$

We say that $\mathcal C$ is \emph{uniformly quasi-wide with margin $s$} if for all $r,m\geq 0$ there exists an $N>0$ such that:
$$\begin{cases}
 G\in\mathcal C \\
 W\subset V(G)\\
 |W| \geq N
 \end{cases}
 \qquad\implies\qquad
 \begin{cases}
 \exists_{S\subseteq V(G)} |S| \leq s(r)\\
 W \textrm{\qquad contains an $r$-scattered subset of $G-S$ of size at least $m$}
 \end{cases}
 $$
Note that uniform quasi-wideness implies quasi-wideness, since we can always take $W=V(G)$.

\subsection{Limit versions}
Let $\mathcal C$ be a class of finite graphs
We say that $\mathcal C$ is \emph{limit quasi-wide} if for all $r\geq 0$,

$$\begin{cases}
 G\in\mathcal C^\star \\
 |G| \geq \omega
 \end{cases}
 \qquad\implies\qquad
 \begin{cases}
 \exists_{S\subseteq V(G)} S\textrm{ finite}\\
 G-S \textrm{\qquad contains an infinite $r$-scattered set}
 \end{cases}
 $$
 We say that $\mathcal C$ is \emph{limit uniformly quasi-wide} if for all $r\geq 0$,

 $$\begin{cases}
  G\in\mathcal C^\star \\
  W\subseteq V(G)\\
  |W| \geq \omega
  \end{cases}
  \qquad\implies\qquad
  \begin{cases}
  \exists_{S\subseteq V(G)} S\textrm{ finite}\\
  W \textrm{\qquad contains an infinite $r$-scattered subset of $G-S$}
  \end{cases}
  $$

\subsection{Strong limit versions}
Let $\mathcal C$ be a class of finite graphs and let $s:\mathbb N\to\mathbb N$ be a function.
We say that $\mathcal C$ is \emph{strongly limit quasi-wide with margin $s$} if for all $m,r\geq 0$,

$$\begin{cases}
 G\in\mathcal C^\star \\
 |G| \geq \omega
 \end{cases}
 \qquad\implies\qquad
 \begin{cases}
 \exists_{S\subseteq V(G)} |S| \leq s(r)\\
 G-S \textrm{\qquad contains an infinite $r$-scattered set}
 \end{cases}
 $$
 
 We say that $\mathcal C$ is \emph{strongly limit uniformly quasi-wide with margin $s$} if for all $m,r\geq 0$,

 $$\begin{cases}
  G\in\mathcal C^\star \\
  W\subseteq V(G)\\
  |W| \geq \omega
  \end{cases}
  \qquad\implies\qquad
  \begin{cases}
  \exists_{S\subseteq V(G)} |S| \leq s(r)\\
  W \textrm{\qquad contains an infinite $r$-scattered subset of $G-S$}
  \end{cases}
  $$
\end{comment}

\subsection{Linking standard and limit notions}

We now link the standard notions of (uniform) quasi-wideness with their limit counterparts. For technical reasons, we can prove this connection directly only for the strong variants of the notion. This technical caveat is the main reason why we introduced the strong variants in the first place.

\begin{lemma}\label{lem:quasi-los}
Let $s\colon \mathbb N\to \mathbb N$ be a function. Then the following implications hold:
\begin{itemize}
\item[(a)] If $\mathcal C$ is strongly limit quasi-wide with margin $s$, then $\mathcal C$ is quasi-wide with margin $s$.
\item[(b)] If $\mathcal C$ is strongly uniformly limit quasi-wide with margin $s$, then $\mathcal C$ is uniformly quasi-wide with margin $s$.
\end{itemize}
\end{lemma}
\begin{proof}
We first prove (b), and then discuss how to modify the reasoning to obtain a proof of (a).

For the sake of contradiction, suppose $\mathcal C$ is not uniformly quasi-wide with margin $s$. This means that there are some $d,m\in \mathbb N$, a sequence of graphs $(G_n)_{n\in \mathbb N}$, and a sequence of sets $(W_n)_{n\in \mathbb N}$, where $W_n\subseteq V(G_n)$ for each $n\in \mathbb N$, such that the following holds for every $n\in \mathbb N$:
\begin{itemize}
\item $|W_n|\geq n$, and
\item for any set $S\subseteq V(G_n)$ with $|S|\leq s(d)$, in $G_n\setminus S$ there is no $d$-scattered set $X$ with $X\subseteq W_n$ and $|X|=m$.
\end{itemize}
Let $G^\star=\prod_\ultra G_n$ and $W^\star=\prod_\ultra W_n$. Then $G^\star\in \mathcal C^\star$, and the same reasoning as in Example~\ref{ex:cliques} shows that $W^\star$ is infinite.

Consider a first order formula $\phi$ in the language of graphs with a specified vertex subset $W$ (encoded as a unary relation) that says the following: ``There are vertices $u_1,u_2,\ldots,u_{s(d)},v_1,v_2,\ldots,v_m$ such that (i) all $\set{v_i}_{1\leq i\leq m}$ are pairwise different, different from all $\set{u_j}_{1\leq j\leq s(d)}$, and contained in $W$; and (ii) for all $1\leq i<i'\leq m$ there is no path of length at most $2d$ between $v_i$ and $v_{i'}$ that would avoid all the vertices $\set{u_j}_{1\leq j\leq s(d)}$''. By our assumption about $G_n$ and $W_n$, we have that $G_n,W_n\nvDash \phi$ for all $n\in \mathbb N$. However, since $\mathcal C$ is strongly uniformly limit quasi-wide with margin $s$, and $W^\star$ is infinite, there is a set $S\subseteq G^\star$ with $|S|\leq s(d)$ such that in $G^\star\setminus S$ there is an infinite $d$-scattered set contained in $W^\star$. In particular there is one of size $m$, so $G^\star,W^\star\models \phi$. This is a contradiction with Łoś's theorem.

The proof of (a) follows the same lines, but we do not need to consider sets $\set{W_n}_{n\in \mathbb N}$ and $W^\star$. Consequently, $\phi$ is simply in the language of graphs and does not require $\set{v_i}_{1\leq i\leq m}$ to be contained in $W$. The rest of the reasoning is the same.
\end{proof}

Lemma~\ref{lem:quasi-los} provides only one direction of implications: from limit variants to the standard ones. Unfortunately, it seems difficult to directly prove the reverse implications. This is because the definition of (uniform) limit quasi-wideness is not hereditary. More precisely, in order to prove that $\mathcal C$ is strongly (uniformly) limit quasi-wide, we need to consider an arbitrary subgraph $G^\star$ of an ultraproduct $\prod_\ultra G_n$ of graphs from $\mathcal C$. In case of the uniformity condition, also an arbitrary subset $W^\star$ of its vertices needs to be considered. Both $G^\star$ and $W^\star$ may not be defined as ultraproducts themselves, while the existence of large scattered sets in $\prod_\ultra G_n$ can have nothing to do with the existence of large scattered sets in $G^\star$. Therefore, it seems difficult to use the assumed quasi-wideness of $\mathcal C$ to reason about $G^\star$ and $W^\star$.

For this reason, we resort to invoking an implication known from the literature.

\begin{lemma}[Lemma 8.9 and Theorem 8.2 of~\cite{sparsity}]\label{lem:finite-qw}
Let $\mathcal C$ be a hereditary class of finite graphs. If $\mathcal C$ is quasi-wide with some margin $s$, then $\mathcal C$ is also topologically nowhere dense.
\end{lemma}

Note that Lemma~\ref{lem:finite-qw} provides the easy implication of the equivalence between quasi-wideness and nowhere denseness. Its proof essentially boils down to observing that a sufficiently large clique with each edge subdivided at most $2d$ times is a counterexample for quasi-wideness. For the harder implication --- from nowhere denseness to quasi-wideness --- in the next section we provide a proof for the limit variants. By combining this with Lemmas~\ref{lem:dense} and~\ref{lem:quasi-los}, we can infer the same implication for the standard variants.

We note that the assumption that $\mathcal C$ is hereditary is necessary in Lemma~\ref{lem:finite-qw}. This is not the case for the implications starting with the limit variants of quasi-wideness, because we explicitly defined $\mathcal C^\star$ to be closed under taking subgraphs.

\begin{comment}
We study some implications between the various quasi-wideness notions defined above.
For this, let us use shorthand notations, 
where SL is shorthand for \emph{strong limit}, L is shorthand for \emph{limit}, U is shorthand for uniform and QW is shorthand for \emph{quasi-wide}.
The set of  possible combinations of these symbols is $\set{\textrm{SL},\textrm{L},\varepsilon}\set{\textrm{U},\varepsilon}\textrm{QW}$,
e.g. SLQW is the property of being ``strongly limit quasi wide graph''. Formally, a property is just a class of classes of finite graphs, and an implication among properties is an inclusion of classes.

\begin{prop}\label{prop:qw}The following implications hold among the properties listed above.
$$
\xymatrix{
\textrm{LUQW } \ar[r] & \textrm{LQW }\\	
\textrm{SLUQW} \ar[r]\ar[d]\ar[u] & \textrm{SLQW}\ar[d]\ar[u]\\
\textrm{UQW  } \ar[r] & \textrm{QW  }
}$$
\end{prop}

\begin{proof}\label{pf:}
	The left-to-right arrows are obvious. The upward arrows are clear too. 
It remains to argue for the downward arrows.

	Consider the case of SLQW. Suppose that a class $\mathcal C$ is strongly limit quasi-wide with margin $s$.
	We show that $\mathcal C$ is quasi-wide with the same margin. Assume otherwise. Then, there exist $r,m>0$ such that for arbitrarily large graphs $G\in \mathcal C$, for every subset $S\subset V(G)$ of at most $s(r)$ elements,
  	 $G-S$ does not contain an $r$-scattered set of size at least $m$.
	Let $G_1,G_2,\ldots$ be a sequence of such graphs, of increasing size.
	Let $\tilde G$ be their ultraproduct. 
	Since $\mathcal C$ is strongly limit quasi-wide with margin $s$, there is a set 	$S$ of size at most $s(r)$ such that 
  $\tilde G-S$ contains an infinite $r$-scattered set,
  in particular, an $r$-scattered set of size at least $m$.
  
  By Łoś'ss theorem,  $G_n$ contains a subset of size at most $s(r)$ such that $G_n-S$ contains an $r$-scattered set of size at least $m$, $\meas$-almost-everywhere\xspace wrt. $n$. This contradicts the assumption on the graphs $G_n$. Therefore, $\mathcal C$ is quasi-wide with margin $s$.
	
	The same proof works for the implication SLUQW$\rightarrow$UQW.
It remains to show that if $\mathcal C$ is uniformly quasi-wide, then $\mathcal C$ is limit quasi-wide.

Suppose that $\mathcal C$ is uniformly quasi-wide with margin $s$.
Let $G\in \mathcal C^\star$ be an infinite graph, and let $r\in \mathbb N$.

In particular,
$G$ is a subgraph of a graph $\tilde G$ which is an ultraproduct of a sequence $G_1,G_2,\ldots$ of graphs in $\mathcal C$.
TODO: finish this implication.
\end{proof}

	It follows that the strongest property among all the six properties studied in this section is the SLUQW property,
and the weakest property is the LQW property.
\end{comment}

\subsection{Quasi-wideness and nowhere denseness}

We now link the limit variants of quasi-wideness and nowhere denseness. First we prove the easier direction.

\begin{lemma}\label{lem:qw-tnd}
If $\mathcal C$ is limit quasi-wide, then $\mathcal C$ is limit topologically nowhere dense.
\end{lemma}
\begin{proof}
  To prove the contrapositive, suppose that for some $d\in \mathbb N$ it holds that $K_\omega\in \mathcal C^\star\mathop{\tilde \triangledown} d$. We show that $\mathcal C$ is not quasi-wide.
  
  Since $\mathcal C^\star$ is closed under taking subgraphs by definition, there is a graph $H\in \mathcal C^\star$ that can be obtained from $K_\omega$ by subdividing each edge at most $2d$ times. Let $A$ be the set of vertices of infinite degree in $H$. Let $S\subseteq V(H)$ be any finite subset of vertices. Observe that every two vertices of $A$ can be connected by an infinite family of internally vertex-disjoint paths in $H$ of length at most $4d+2$. As $S$ is finite, it follows that all the vertices of $A\setminus S$ belong to the same connected component $C_0$ of $H\setminus S$, and moreover they are pairwise at distance at most $4d+2$ within $C_0$. Since each path connecting a pair of vertices from $A$ has length at most $2d+1$, we infer that the diameter of $C_0$ is at most $8d+2$. Each connected component of $H\setminus S$ apart from $C_0$ is contained in the internal vertices of some path connecting a pair of vertices of $A$, and hence has size at most $2d-1$. Moreover, there can be at most $\binom{|S|}{2}$ such components. We conclude that $H\setminus S$ has a finite number of connected components, each of diameter at most $8d+2$. As $S$ was chosen arbitrarily,  $\mathcal C$ cannot be limit quasi-wide.
\end{proof}


\input{big-proof.tex}



