On the VC Dimension of First-Order Logic with Counting and Weight Aggregation

van Bergerem, Steffen; Schweikardt, Nicole

doi:10.4230/LIPIcs.CSL.2025.15

On the VC Dimension of First-Order Logic
with Counting and Weight Aggregation

Steffen van Bergerem

Humboldt-Universität zu Berlin, Germany Nicole Schweikardt

Humboldt-Universität zu Berlin, Germany

Abstract

We prove optimal upper bounds on the Vapnik–Chervonenkis density of formulas in the extensions of first-order logic with counting ( $\textup{{FOC}}_{1}$ ) and with weight aggregation ( $\textup{{FOWA}}_{1}$ ) on nowhere dense classes of (vertex- and edge-)weighted finite graphs. This lifts a result of Pilipczuk, Siebertz, and Toruńczyk [14] from first-order logic on ordinary finite graphs to substantially more expressive logics on weighted finite graphs. Moreover, this proves that every $\textup{{FOC}}_{1}$ formula and every $\textup{{FOWA}}_{1}$ formula has bounded Vapnik–Chervonenkis dimension on nowhere dense classes of weighted finite graphs; thereby, it lifts a result of Adler and Adler [1] from first-order logic to $\textup{{FOC}}_{1}$ and $\textup{{FOWA}}_{1}$ .

Generalising another result of Pilipczuk, Siebertz, and Toruńczyk [14], we also provide an explicit upper bound on the ladder index of $\textup{{FOC}}_{1}$ and $\textup{{FOWA}}_{1}$ formulas on nowhere dense classes. This shows that nowhere dense classes of weighted finite graphs are $\textup{{FOC}}_{1}$ -stable and $\textup{{FOWA}}_{1}$ -stable.

Keywords and phrases:

VC dimension, VC density, stability, nowhere dense graphs, first-order logic with weight aggregation, first-order logic with counting

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Finite Model Theory

Acknowledgements:

We thank the anonymous reviewers for their valuable comments that helped to improve the presentation of this paper.

Funding:

This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 541000908 (gefördert durch die Deutsche Forschungsgemeinschaft (DFG) – Projektnummer 541000908).

DOI:

10.4230/LIPIcs.CSL.2025.15

Event:

33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Editors:

Jörg Endrullis and Sylvain Schmitz

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Vapnik–Chervonenkis dimension (for short: VC dimension) is a measure for the complexity of set systems; it was introduced in the 1970s [19, 17, 16] and has been widely studied since then. It is formally defined as follows. Let $X$ be a set and let $\mathcal{F}\subseteq 2^{X}$ be a family of subsets of $X$ . A set $Y\subseteq X$ is shattered by $\mathcal{F}$ if every subset of $Y$ can be obtained as the intersection of $Y$ with some $F\in\mathcal{F}$ , i. e., $\{Y\cap F:F\in\mathcal{F}\}=2^{Y}$ . The VC dimension of $\mathcal{F}$ is the maximum size of a set $Y\subseteq X$ that is shattered by $\mathcal{F}$ (or $\infty$ , if this maximum does not exist).

Given a logical formula $\varphi(\bar{x},\bar{y})$ with its free variables partitioned into a $k$ -tuple $\bar{x}$ and an $\ell$ -tuple $\bar{y}$ , the VC dimension of $\varphi(\bar{x},\bar{y})$ on a graph $G=(V(G),E(G))$ is defined as the VC dimension of the family $S^{\varphi}(G/V(G))\coloneqq S^{\varphi}_{G}(V(G)/V(G))$ , where for $V,W\subseteq V(G)$ we let

S^{\varphi}_{G}(V/W)\coloneqq\{\textup{tp}^{\varphi}_{G}(\bar{v}/W):\bar{v}\in V% ^{k}\},\quad\text{where}\quad\textup{tp}^{\varphi}_{G}(\bar{v}/W)\coloneqq\{% \bar{w}\in W^{\ell}:G\models\varphi[\bar{v},\bar{w}]\}.

We say that $\varphi(\bar{x},\bar{y})$ has bounded VC dimension on a class $\mathcal{C}$ of graphs if there is a number $c$ such that for every $G\in\mathcal{C}$ the VC dimension of $\varphi(\bar{x},\bar{y})$ on $G$ is at most $c$ . In the following, all graphs considered in this paper are finite.

Motivated by applications on the learnability of concept classes in the model of Probably Approximately Correct (PAC) learning, Grohe and Turán [9] showed that every first-order formula $\varphi(\bar{x},\bar{y})$ has bounded VC dimension on classes of graphs of bounded local clique-width (this, in particular, includes planar graphs). Adler and Adler [1] generalised this to all nowhere dense classes of graphs. The notion of nowhere dense classes was introduced by Nešetřil and Ossona de Mendez [12, 11] as a formalisation of classes of “sparse” graphs. It subsumes and extends many well-known classes of sparse graphs, including planar graphs, trees, classes of graphs of bounded tree-width or bounded degree, and all classes that exclude a fixed topological minor. It is a robust notion that has numerous equivalent characterisations; for details we refer to the book [13].

The goal of the present paper is to lift Adler and Adler’s result [1] from first-order logic FO to the substantially more expressive logics $\textup{{FOC}}_{1}$ and $\textup{{FOWA}}_{1}$ (introduced in [8, 5]) that enrich FO by mechanisms for counting and for weight aggregation. An obstacle in achieving this is that the proof in [1] relies on model-theoretic results of [15] based on the compactness of FO – and these are not available for $\textup{{FOC}}_{1}$ or $\textup{{FOWA}}_{1}$ . Fortunately, Pilipczuk, Siebertz and Toruńczyk [14] presented a different, constructive proof of Adler and Adler’s result. Their proof is based on Gaifman locality and Feferman–Vaught decompositions of FO. Similar locality results and decompositions were achieved for $\textup{{FOC}}_{1}$ and $\textup{{FOWA}}_{1}$ in [8, 5].

The logic FOC (first-order logic with counting terms) was introduced in [10] and further studied in [8, 3]. This logic extends FO by the ability to formulate counting terms that evaluate to integers, and by numerical predicates that allow to compare counting terms. If $\varphi$ is a formula with free variables $\bar{x}=(x_{1},\ldots,x_{k})$ and $\bar{y}=(y_{1},\ldots,y_{\ell})$ , then $\#\bar{y}.\varphi$ is a counting term with free variables $\bar{x}$ that specifies the number of tuples $\bar{y}$ that satisfy the formula $\varphi$ . Apart from this, every fixed integer is a counting term; and if $t_{1}$ and $t_{2}$ are counting terms, then so are $(t_{1}+t_{2})$ and $(t_{1}\cdot t_{2})$ . The results of terms can be combined into a formula by means of numerical predicates: an $m$ -ary numerical predicate $\mathsf{P}$ is an $m$ -ary relation on the integers (e. g. $\mathsf{P}_{\leqslant}$ is the binary relation consisting of all pairs $(i,j)$ of integers where $i\leqslant j$ ). The logic FOC allows formulas of the form $\mathsf{P}(t_{1},\ldots,t_{m})$ that evaluate to “true” if and only if the $m$ -tuple of integers obtained by evaluating the counting terms $t_{1},\ldots,t_{m}$ belongs to the relation $\mathsf{P}$ .

The logic FOWA (first-order logic with weight aggregation) was introduced in [5]. Formulas and terms of this logic are evaluated on weighted graphs, which extend ordinary undirected graphs by assigning weights (i. e., elements from particular rings or abelian groups) to vertices or edges present in the graph. Pairs that do not occur as edges of the graph receive the weight 0, i. e., the neutral element of the ring or abelian group. FOWA extends FO by the ability to formulate (weight aggregation) terms that evaluate to elements in the given ring (or abelian group), and by predicates that allow to compare these terms. Every fixed element of the ring or abelian group is a term, as well as every expression of the form $\mathtt{w}(x)$ or $\mathtt{w}(x,y)$ ; the latter yields the weight of vertex $x$ and edge $(x,y)$ , respectively. If $\varphi$ is a formula with free variables $\bar{x}=(x_{1},\ldots,x_{k})$ and $\bar{y}=(y_{1},\ldots,y_{\ell})$ , then $\sum\mathtt{w}(\bar{y}).\varphi$ is a (weight aggregation) term with free variables $\bar{x}$ that specifies the sum (w.r.t. the ring or abelian group) of the weights of all tuples $\bar{y}$ for which the formula $\varphi$ is satisfied. More generally, instead of a single expression $\mathtt{w}(\bar{y})$ , the term may also refer to a product (w.r.t. the given ring) of such expressions and fixed elements of the ring. Analogously as for FOC, terms can be combined using the operations present in the ring or abelian group; and the results of terms can be combined into a formula by means of predicates on the ring or abelian group: a formula of the form $\mathsf{P}(t_{1},\ldots,t_{m})$ expresses that the $m$ -tuple of elements in the ring or abelian group obtained by evaluating the terms $t_{1},\ldots,t_{m}$ belongs to the relation $\mathsf{P}$ .

FOC can be viewed as a special case of FOWA where the ring is the ring of integers, and every vertex of the graph is equipped with the weight $1$ . Thus, all results that are available for (fragments of) FOWA immediately translate into analogous results on (the corresponding fragment of) FOC (but not necessarily vice versa).

For each number $n$ , the fragments $\textup{{FOC}}_{n}$ and $\textup{{FOWA}}_{n}$ of FOC and FOWA restrict subformulas of the form $\mathsf{P}(t_{1},\ldots,t_{m})$ to have at most $n$ free variables.

In this paper, we follow the approach of Pilipczuk, Siebertz and Toruńczyk [14] and extend it to FOC and FOWA by utilising results of van Bergerem and Schweikardt [5] and Grohe and Schweikardt [8]. Our main results are as follows.

(1)

There is a formula $\varphi(x,y)$ of $\textup{{FOC}}_{2}$ that has unbounded VC dimension on the class $\mathcal{T}_{3}$ of unranked trees of height $\leqslant 3$ (note that $\mathcal{T}_{3}$ is nowhere dense). (Theorem 3.1)
(2)

Every formula $\varphi(\bar{x},\bar{y})$ of $\textup{{FOC}}_{1}$ or $\textup{{FOWA}}_{1}$ has bounded VC dimension on every nowhere dense class $\mathcal{C}$ of weighted graphs. (Corollary 5.3)

Result (1) is obtained by representing arbitrary graphs $G$ via unranked trees $T_{G}$ of height 3 in the same way as in [8]. Then, arbitrary FO formulas on $G$ can be translated into corresponding $\textup{{FOC}}_{2}$ formulas on $T_{G}$ . By applying this translation to the formula $E(x,y)$ , which has unbounded VC dimension on the class of all graphs, one obtains Result (1).

For obtaining Result (2), we combine the approach of [14] with the locality results of [8, 5]. This allows us to lift the following key result of [14] from FO to $\textup{{FOC}}_{1}$ and $\textup{{FOWA}}_{1}$ .

(3)

For every nowhere dense class $\mathcal{C}$ of weighted graphs, for every formula $\varphi(\bar{x},\bar{y})$ of $\textup{{FOWA}}_{1}$ or $\textup{{FOC}}_{1}$ , and for and every $\varepsilon>0$ , there exists a number $c$ such that for every $G\in\mathcal{C}$ and every non-empty $W\subseteq V(G)$ , we have $\left\lvert S^{\varphi}(G/W)\right\rvert\leqslant c\cdot\left\lvert W\right% \rvert^{\left\lvert\bar{x}\right\rvert+\varepsilon}$ , where $S^{\varphi}(G/W)\coloneqq S^{\varphi}_{G}(V(G),W)$ . (Theorem 5.1)

As an immediate consequence of this, by definition, we obtain the following result.

(4)

Every formula $\varphi(\bar{x},\bar{y})$ of $\textup{{FOWA}}_{1}$ or $\textup{{FOC}}_{1}$ has VC density at most $\left\lvert\bar{x}\right\rvert$ on every nowhere dense class $\mathcal{C}$ of weighted graphs. (Corollary 5.2)

Here, the VC density of $\varphi(\bar{x},\bar{y})$ on $\mathcal{C}$ is defined as the infimum of all reals $\alpha>0$ such that $\left\lvert S^{\varphi}(G/W)\right\rvert\in\mathcal{O}(\left\lvert W\right% \rvert^{\alpha})$ , for all $G\in\mathcal{C}$ and all $W\subseteq V(G)$ (where constants hidden in the $\mathcal{O}$ -notation may depend on $\alpha$ ). We want to remark that Result (4) implies Result (2), because the VC dimension is finite if and only if the VC density is finite (see, e. g., [2]).

For proving Result (3), we rely on a technical main lemma (see Lemma 4.1). The same statement was proven in [14] for FO instead of $\textup{{FOWA}}_{1}$ . Lifting this from FO to $\textup{{FOWA}}_{1}$ (and $\textup{{FOC}}_{1}$ ) was one of the main technical obstacles we had to overcome in this paper.

From [14], we know that the bounds provided by Results (3) and (4) are optimal (since FO is included in $\textup{{FOC}}_{1}$ and $\textup{{FOWA}}_{1}$ ) and, furthermore, that Results (2)–(4) cannot be extended to classes that are not nowhere dense but closed under taking subgraphs.

As another application of our main technical lemma (Lemma 4.1), we provide upper bounds (Theorem 6.1) on the ladder index, which is defined as follows. For a $\textup{{FOWA}}_{1}$ formula $\varphi(\bar{x},\bar{y})$ , a $\varphi$ -ladder of length $L$ in a weighted graph $G$ is a sequence $\bar{v}_{1},\dots,\bar{v}_{L},\bar{w}_{1},\dots,\bar{w}_{L}$ such that $\bar{v}_{i}\in\bigl{(}V(G)\bigr{)}{}^{\left\lvert\bar{x}\right\rvert}$ and $\bar{w}_{i}\in\bigl{(}V(G)\bigr{)}{}^{\left\lvert\bar{y}\right\rvert}$ for all $i\in[L]$ , and, for all $i,j\in[L]$ , it holds that $G\models\varphi[\bar{v}_{i},\bar{w}_{j}]$ if and only if $i\leqslant j$ . The smallest $L$ for which there is no $\varphi$ -ladder of length $L$ in $G$ is called the ladder index of $\varphi$ in $G$ .

A class $\mathcal{C}$ of graphs is called stable if the ladder index of every first-order formula $\varphi$ in every graph from $\mathcal{C}$ is bounded by a constant depending only on $\varphi$ and $\mathcal{C}$ [18]. Adler and Adler [1] showed that every nowhere dense class of graphs is stable. Using our bound on the ladder index (Theorem 6.1), we obtain the following result, which also implies Result (2).

(5)

Every nowhere dense class $\mathcal{C}$ of weighted graphs is $\textup{{FOC}}_{1}$ -stable and $\textup{{FOWA}}_{1}$ -stable, that is, the ladder index of every $\textup{{FOWA}}_{1}$ formula (and therefore also of every $\textup{{FOC}}_{1}$ formula) $\varphi$ in every weighted graph from $\mathcal{C}$ is bounded by a constant depending only on $\varphi$ and $\mathcal{C}$ . (Corollary 6.2)

The remainder of the paper is structured as follows. Section 2 provides the necessary background on graphs, nowhere dense classes, the logics FOC and FOWA, and the locality results that are known for these logics and used in our proofs. Section 3 presents the proof of Result (1). Section 4 is devoted to the main technical lemma (Lemma 4.1). In Section 5, we utilise this lemma to prove our Results (2)–(4). Section 6 proves Result (5) based on Lemma 4.1. We conclude in Section 7.

2 Preliminaries

We let $\mathbb{Z}$ , $\mathbb{N}$ , $\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ , $\mathbb{Q}_{>0}$ denote the sets of integers, non-negative integers, positive integers, and positive rationals, respectively. For $m,n\in\mathbb{Z}$ , we let $[m,n]\coloneqq\{\ell\in\mathbb{Z}:m\leqslant\ell\leqslant n\}$ and $[n]\coloneqq[1,n]$ . For a $k$ -tuple $\bar{v}=(v_{1},\dots,v_{k})$ , we write $\left\lvert\bar{v}\right\rvert$ to denote its length $k$ . We denote the power set of a set $S$ by $2^{S}$ .

A group $(G,\circ)$ is a set $G$ equipped with a binary operator $\circ\colon G\times G\to G$ that is associative (i. e. $(a\circ b)\circ c=a\circ(b\circ c)$ for all $a,b,c\in G$ ) and has a neutral element $e_{G}\in G$ (i. e. $a\circ e_{G}=e_{G}\circ a=a$ for all $a\in G$ ) such that each $a\in G$ has an inverse $a^{\prime}\in G$ (i. e. $a\circ a^{\prime}=a^{\prime}\circ a=e_{G}$ ); we write $a^{-1}$ for this $a^{\prime}$ . A group is abelian if $\circ$ is commutative (i. e. $a\circ b=b\circ a$ for all $a,b\in G$ ). A ring $(R,+,\cdot)$ is a set $R$ equipped with two binary operators $+$ (addition) and $\cdot$ (multiplication) such that $(R,+)$ is an abelian group with neutral element $0_{R}\in R$ , $\cdot$ is associative and has a neutral element $1_{R}\in R$ , and multiplication is distributive with respect to addition, i. e. $a\cdot(b+c)=(a\cdot b)+(a\cdot c)$ and $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$ for all $a,b,c\in R$ . A ring is commutative if $\cdot$ is commutative.

When referring to an abelian group (or ring), we will usually write $(S,+_{S})$ (or $(S,+_{S},{\cdot}_{S})$ ), we denote the neutral element of the group by $0_{S}$ , and $-a$ denotes the inverse of an element $a$ in $(S,+_{S})$ (and we denote the neutral element of the ring for $(S,{\cdot}_{S})$ by $1_{S}$ ).

$\sigma$ -Graphs

A (simple, undirected and finite) graph $G=(V(G),E(G))$ consists of a finite set $V(G)$ (the vertices of $G$ ) and a set $E(G)$ of subsets of $V(G)$ of size 2 (the edges of $G$ ).

A graph signature $\sigma$ is a finite set consisting of a symbol $E$ and a finite number of further symbols. The symbol $E$ as arity $\operatorname*{ar}(E)=2$ , while all other symbols $R\in\sigma\setminus\{E\}$ have arity $\operatorname*{ar}(R)\in\{0,1\}$ . Let $\sigma$ be a graph signature. A $\sigma$ -graph $G$ consists of a graph $(V(G),E(G))$ , and a relation $R(G)\subseteq\bigl{(}V(G)\bigr{)}{}^{\operatorname*{ar}(R)}$ for every $R\in\sigma\setminus\{E\}$ . Note that relations of arity 1 are subsets of $V(G)$ , and since $S^{0}=\{()\}$ for every set $S$ , there exist only two relations of arity 0, namely $\emptyset$ and $\{()\}$ . We identify the latter with true and the former with false.

The order of a $\sigma$ -graph $G$ is $\left\lvert G\right\rvert\coloneqq\left\lvert V(G)\right\rvert$ .

Weighted $\sigma$ -Graphs

Let $\sigma$ be a graph signature. Let $\mathbb{S}$ be a collection of rings and/or abelian groups. Let $\mathbf{W}$ be a finite set of weight symbols such that each $\mathtt{w}\in\mathbf{W}$ has an associated arity $\operatorname*{ar}(\mathtt{w})\in\{1,2\}$ and a type $\textup{type}(\mathtt{w})\in\mathbb{S}$ . A $(\sigma,\mathbf{W})$ -graph (or, $\mathbf{W}$ -weighted $\sigma$ -graph) is a $\sigma$ -graph $G$ that is enriched, for every $\mathtt{w}\in\mathbf{W}$ , by an interpretation $\mathtt{w}^{G}\colon\bigl{(}V(G)\bigr{)}{}^{\operatorname*{ar}(\mathtt{w})}\to% \textup{type}(\mathtt{w})$ , which satisfies the following edge condition for all $\mathtt{w}\in\mathbf{W}$ with $\operatorname*{ar}(\mathtt{w})=2$ : if $\mathtt{w}^{G}(v_{1},v_{2})\neq 0_{S}$ for $S\coloneqq\textup{type}(\mathtt{w})$ , and $v_{1},v_{2}\in V(G)$ , then $\{v_{1},v_{2}\}\in E(G)$ .

Standard notions used for graphs are defined for $(\mathbf{W},\sigma)$ -graphs $G$ by referring to their Gaifman graph $(V(G),E(G))$ . In particular, a path between two vertices $u$ and $v$ in $G$ is a path between $u$ and $v$ in the graph $(V(G),E(G))$ , and the distance $\operatorname{dist}^{G}(u,v)$ between vertices $u$ and $v$ is their distance in the graph $(V(G),E(G))$ . The degree $\deg(G)$ is the maximum degree of $(V(G),E(G))$ .

For a set $X\subseteq V(G)$ , the induced subgraph of $G$ on $X$ is the $(\sigma,\mathbf{W})$ -graph $G[X]$ with vertex set $V(G[X])=X$ , edge set $E(G[X])=\{e\in E(G):e\subseteq X\}$ , relations $R(G[X])=R(G)\cap X^{\operatorname*{ar}(R)}$ for every $R\in\sigma\setminus\{E\}$ , and weights $\mathtt{w}^{G[X]}(\bar{v})=\mathtt{w}^{G}(\bar{v})$ for every $\mathtt{w}\in\mathbf{W}$ and every $\bar{v}\in X^{\operatorname*{ar}(\mathtt{w})}$ . For a $(\sigma,\mathbf{W})$ -graph $G$ and a set $S\subseteq V(G)$ , we let $G\setminus S\coloneqq G[V(G)\setminus S]$ .

For a number $r\geqslant 0$ , the $r$ -ball around a vertex $v\in V(G)$ is $N_{r}^{G}(v)\coloneqq\{u\in V(G):\operatorname{dist}^{G}(v,u)\leqslant r\}$ , and the $r$ -ball around a set $S\subseteq V(G)$ is $N_{r}^{G}(S)\coloneqq\bigcup_{v\in S}N_{r}^{G}(v)$ . The $r$ -neighbourhood around $S$ is the $(\sigma,\mathbf{W})$ -graph $\mathcal{N}_{r}^{G}(S)\coloneqq G[N_{r}^{G}(S)]$ . For a tuple $\bar{a}=(a_{1},\ldots,a_{k})\in V(G)^{k}$ we let $\mathcal{N}_{r}^{G}(\bar{a})\coloneqq\mathcal{N}_{r}^{G}(S)$ and $N_{r}^{G}(\bar{a})\coloneqq N_{r}^{G}(S)$ for $S\coloneqq\{a_{1},\ldots,a_{k}\}$ .

Let $\sigma^{\prime}$ be a graph signature with $\sigma^{\prime}\supseteq\sigma$ , and let $\mathbf{W}^{\prime}$ be a finite set of weight symbols with $\mathbf{W}^{\prime}\supseteq\mathbf{W}$ . A $(\sigma^{\prime},\mathbf{W}^{\prime})$ -graph $G^{\prime}$ is a $(\sigma^{\prime},\mathbf{W}^{\prime})$ -expansion of a $(\sigma,\mathbf{W})$ -graph $G$ if $V(G^{\prime})=V(G)$ , $R(G^{\prime})=R(G)$ for all $R\in\sigma$ , and $\mathtt{w}^{G^{\prime}}=\mathtt{w}^{G}$ for every $\mathtt{w}\in\mathbf{W}$ . If $G^{\prime}$ is a $(\sigma^{\prime},\mathbf{W}^{\prime})$ -expansion of the $(\sigma,\mathbf{W})$ -graph $G$ , then $G$ is the $(\sigma,\mathbf{W})$ -reduct of $G^{\prime}$ .

Let $G$ and $H$ be two $(\sigma,\mathbf{W})$ -graphs with $V(G)\cap V(H)=\emptyset$ . The disjoint union of $G$ and $H$ is the $(\sigma,\mathbf{W})$ -graph $G\uplus H$ with vertex set $V(G\uplus H)=V(G)\cup V(H)$ , and $R(G\uplus H)=R(G)\cup R(H)$ for all $R\in\sigma$ , and weight functions as follows: For all unary $\mathtt{w}\in\mathbf{W}$ we have $\mathtt{w}^{G\uplus H}(v)=\mathtt{w}^{G}(v)$ for all $v\in V(G)$ and $\mathtt{w}^{G\uplus H}(v)=\mathtt{w}^{H}(v)$ for all $v\in V(H)$ . For all binary $\mathtt{w}\in\mathbf{W}$ we have $\mathtt{w}^{G\uplus H}(u,v)=\mathtt{w}^{G}(u,v)$ for all $(u,v)\in V(G)^{2}$ , $\mathtt{w}^{G\uplus H}(u,v)=\mathtt{w}^{H}(u,v)$ for all $(u,v)\in V(H)^{2}$ , and $\mathtt{w}^{G\uplus H}(u,v)=0_{S}$ for all $(u,v)\in(V(G)\times V(H))\cup(V(H)\times V(G))$ , where $S=\textup{type}(\mathtt{w})$ .

Nowhere Dense Classes

For $n\in\mathbb{N}$ , we write $K_{n}$ for the complete graph on $n$ vertices. A depth- $n$ minor of a graph $G=(V(G),E(G))$ is a subgraph of a graph obtained from $G$ by contracting mutually vertex-disjoint connected subgraphs of radius at most $n$ to single vertices.

As mentioned in Section 1, the notion of nowhere dense classes of graphs is a robust notion that has numerous equivalent characterisations; for an overview we refer to the introduction of [14]; details can be found in the book [13]. For the purpose of this paper, the following characterisation serves as our definition of the notion.

Definition 2.1.

A class $\mathcal{C}$ of graphs is nowhere dense if there is a function $t\colon\mathbb{N}\to\mathbb{N}$ such that for every $r\in\mathbb{N}$ , no graph $G\in\mathcal{C}$ contains the complete graph $K_{t(r)}$ as a depth- $r$ minor. A class $\mathcal{C}$ of $(\sigma,\mathbf{W})$ -graphs is nowhere dense if and only if the class $\{(V(G),E(G)):G\in\mathcal{C}\}$ is nowhere dense.

The following theorem was proved in [14] (there, it was formulated for classes of graphs; here we adapted the formulation to classes of $(\sigma,\mathbf{W})$ -graphs). We will use this result for proving our results on VC density in Section 5. The result uses the following notion. Let $G$ be a $(\sigma,\mathbf{W})$ -graph, let $r\in\mathbb{N}$ , and let $V,W,S\subseteq V(G)$ . We say that $V$ and $W$ are $r$ -separated by $S$ (in $G$ ) if every path of length at most $r$ in $G$ from a vertex in $V$ to a vertex in $W$ contains a vertex from $S$ . This notion naturally extends to tuples $\bar{v}=(v_{1},\dots,v_{k})$ and $\bar{w}=(w_{1},\dots,w_{\ell})$ for any $k,\ell\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ by considering the sets $\{v_{1},\dots,v_{k}\}$ and $\{w_{1},\dots,w_{\ell}\}$ , and it thereby also naturally extends to sets of tuples $V$ and $W$ .

Theorem 2.2 (Uniform quasi-wideness for tuples [14, Theorem 2.9]).

Let $r,t\in\mathbb{N}$ , and let $\mathcal{C}$ be a class of $(\sigma,\mathbf{W})$ -graphs $G$ whose Gaifman graph $(V(G),E(G))$ does not include $K_{t}$ as a depth- $18r$ minor. For every $d\in\mathbb{N}$ , there is a number $s$ and a polynomial $N\colon\mathbb{N}\to\mathbb{N}$ computable from $r, t$ , and $d$ with the following property.

For every $G\in\mathcal{C}$ , every $m\in\mathbb{N}$ , and every set $X\subseteq(V(G))^{d}$ with $\left\lvert X\right\rvert\geqslant N(m)$ , there are sets $S\subseteq V(G)$ and $Y\subseteq X$ with $\left\lvert S\right\rvert\leqslant s$ and $\left\lvert Y\right\rvert\geqslant m$ such that all distinct $\bar{v},\bar{v}^{\prime}\in Y$ are $r$ -separated by $S$ in $G$ .

The Weight Aggregation Logic FOWA

Fix a countably infinite set vars of variables. A $(\sigma,\mathbf{W})$ -interpretation $\mathcal{I}=(G,\beta)$ consists of a $(\sigma,\mathbf{W})$ -graph $G$ and an assignment $\beta\colon\textsf{vars}\to V(G)$ . For $k\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ , elements $a_{1},\ldots,a_{k}\in V(G)$ , and $k$ distinct variables $y_{1},\ldots,y_{k}$ , we write $\mathcal{I}\frac{a_{1},\ldots,a_{k}}{y_{1},\ldots,y_{k}}$ for the interpretation $(G,\beta\frac{a_{1},\ldots,a_{k}}{y_{1},\ldots,y_{k}})$ , where $\beta\frac{a_{1},\ldots,a_{k}}{y_{1},\ldots,y_{k}}$ is the assignment $\beta^{\prime}$ with $\beta^{\prime}(y_{i})=a_{i}$ for every $i\in[k]$ and $\beta^{\prime}(z)=\beta(z)$ for all $z\in\textsf{vars}\setminus\{y_{1},\ldots,y_{k}\}$ .

Recall that $\mathbb{S}$ is a collection of rings and/or abelian groups. An $\mathbb{S}$ -predicate collection is a 4-tuple $(\mathbb{P},\operatorname*{ar},\textup{type},\left\llbracket\cdot\right\rrbracket)$ , where $\mathbb{P}$ is a countable set of predicate names and, to each $\mathsf{P}\in\mathbb{P}$ , $\operatorname*{ar}$ assigns an arity $\operatorname*{ar}(\mathsf{P})\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ , type assigns a type $\textup{type}(\mathsf{P})\in\mathbb{S}^{\operatorname*{ar}(\mathsf{P})}$ , and $\left\llbracket\cdot\right\rrbracket$ assigns a semantics $\left\llbracket\mathsf{P}\right\rrbracket\subseteq\textup{type}(\mathsf{P})$ . For the remainder of this paper, fix an $\mathbb{S}$ -predicate collection $(\mathbb{P},\operatorname*{ar},\textup{type},\left\llbracket\cdot\right\rrbracket)$ .

For every $S\in\mathbb{S}$ that is not a ring but just an abelian group, a $\mathbf{W}$ -product of type $S$ is either an element in $S$ or an expression of the form $\mathtt{w}(\bar{z})$ , where $\mathtt{w}\in\mathbf{W}$ is of type $S$ and either $\operatorname*{ar}(\mathtt{w})=1$ and $\bar{z}$ is a single variable, or $\operatorname*{ar}(\mathtt{w})=2$ and $\bar{z}=(z_{1},z_{2})$ for distinct variables $z_{1},z_{2}$ .

For every ring $S\in\mathbb{S}$ , a $\mathbf{W}$ -product of type $S$ is an expression of the form $t_{1}{\cdot}\cdots{\cdot}t_{\ell}$ , where $\ell\in\mathbb{N}_{\scriptscriptstyle\geqslant 1}$ , and for each $i\in[\ell]$ , either $t_{i}\in S$ or there exists a $\mathtt{w}\in\mathbf{W}$ with $\textup{type}(\mathtt{w})=S$ and either $\operatorname*{ar}(\mathtt{w})=1$ and $t_{i}$ is of the form $\mathtt{w}(z)$ for a variable $z$ or $\operatorname*{ar}(\mathtt{w})=2$ and $t_{i}$ is of the form $\mathtt{w}(z_{1},z_{2})$ for distinct variables $z_{1},z_{2}$ . By $\textup{vars}(p)$ , we denote the set of all variables that occur in a $\mathbf{W}$ -product $p$ . The syntax and semantics of first-order logic with weight aggregation FOWA is defined as follows.

Definition 2.3.

For $\textup{{FOWA}}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ , the set of formulas and $\mathbb{S}$ -terms is built according to the following rules.

(1)

$x_{1}{=}x_{2}$ and $R(x_{1},\dots,x_{k})$ are formulas for $x_{1},\dots,x_{k}\in\textsf{vars}$ and $R\in\sigma$ with $\operatorname*{ar}(R)=k$ .
(2)

If $\mathtt{w}\in\mathbf{W}$ , $S=\textup{type}(\mathtt{w})$ , $s\in S$ , $k=\operatorname*{ar}(\mathtt{w})$ , and $\bar{x}=(x_{1},\dots,x_{k})$ is a tuple of $k$ pairwise distinct variables, then $\bigl{(}s=\mathtt{w}(\bar{x})\bigr{)}$ is a formula.
(3)

If $\varphi$ and $\psi$ are formulas, then $\neg\varphi$ and $(\varphi\lor\psi)$ are also formulas.
(4)

If $\varphi$ is a formula and $x\in\textsf{vars}$ , then $\exists x\,\varphi$ is a formula.
(5)

If $\varphi$ is a formula, $\mathtt{w}\in\mathbf{W}$ , $S=\textup{type}(\mathtt{w})$ , $s\in S$ , $k=\operatorname*{ar}(\mathtt{w})$ , and $\bar{x}=(x_{1},\dots,x_{k})$ is a tuple of $k$ pairwise distinct variables, then $\bigl{(}s=\sum\mathtt{w}(\bar{x}).\varphi\bigr{)}$ is a formula.
(6)

If $\mathsf{P}\in\mathbb{P}$ , $m=\operatorname*{ar}(\mathsf{P})$ , and $t_{1},\dots,t_{m}$ are $\mathbb{S}$ -terms with $\textup{type}(\mathsf{P})=\bigl{(}\textup{type}(t_{1}),\dots,\textup{type}(t_{% m})\bigr{)}$ , then $\mathsf{P}(t_{1},\dots,t_{m})$ is a formula.
(7)

For every $S\in\mathbb{S}$ and every $s\in S$ , $s$ is an $\mathbb{S}$ -term of type $S$ .
(8)

For every $S\in\mathbb{S}$ , every $\mathtt{w}\in\mathbf{W}$ of type $S$ , and every tuple $(x_{1},\dots,x_{k})$ of $k\coloneqq\operatorname*{ar}(\mathtt{w})$ pairwise distinct variables in vars, $\mathtt{w}(x_{1},\dots,x_{k})$ is an $\mathbb{S}$ -term of type $S$ .
(9)

If $t_{1}$ and $t_{2}$ are $\mathbb{S}$ -terms of the same type $S$ , then $(t_{1}+t_{2})$ and $(t_{1}-t_{2})$ are also $\mathbb{S}$ -terms of type $S$ ; furthermore, if $S$ is a ring (and not just an abelian group), then also $(t_{1}{\cdot}t_{2})$ is an $\mathbb{S}$ -term of type $S$ .
(10)

If $\varphi$ is a formula, $S\in\mathbb{S}$ , and $p$ is a $\mathbf{W}$ -product of type $S$ , then $\sum{p}.{\varphi}$ is an $\mathbb{S}$ -term of type $S$ .

Let $\mathcal{I}=(G,\beta)$ be a $(\sigma,\mathbf{W})$ -interpretation. For a formula or $\mathbb{S}$ -term $\xi$ from $\textup{{FOWA}}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ , the semantics $\left\llbracket\xi\right\rrbracket^{\mathcal{I}}$ is defined as follows.

(1)

$\left\llbracket x_{1}{=}x_{2}\right\rrbracket^{\mathcal{I}}=1$ if $\beta(x_{1})=\beta(x_{2})$ , and $\left\llbracket x_{1}{=}x_{2}\right\rrbracket^{\mathcal{I}}=0$ otherwise; $\left\llbracket E(x_{1},x_{2})\right\rrbracket^{\mathcal{I}}=1$ if $\{\beta(x_{1}),\beta(x_{2})\}\in E(G)$ , and $\left\llbracket E(x_{1},x_{2})\right\rrbracket^{\mathcal{I}}=0$ otherwise; for all $R\in\sigma$ with $\operatorname*{ar}(R)=1$ , we have $\left\llbracket R(x_{1})\right\rrbracket^{\mathcal{I}}=1$ if $\beta(x_{1})\in R(G)$ , and $\left\llbracket R(x_{1})\right\rrbracket^{\mathcal{I}}=0$ otherwise; for all $R\in\sigma$ with $\operatorname*{ar}(R)=0$ , we have $\left\llbracket R()\right\rrbracket^{\mathcal{I}}=1$ if $()\in R(G)$ , and $\left\llbracket R()\right\rrbracket^{\mathcal{I}}=0$ otherwise.
(2)

$\left\llbracket\bigl{(}s=\mathtt{w}(\bar{x})\bigr{)}\right\rrbracket{}^{% \mathcal{I}}=1$ if $s=\mathtt{w}^{G}\bigl{(}\beta(x_{1}),\dots,\beta(x_{k})\bigr{)}$ , and $\left\llbracket\bigl{(}s=\mathtt{w}(\bar{x})\bigr{)}\right\rrbracket{}^{% \mathcal{I}}=0$ otherwise.
(3)

$\left\llbracket\neg\varphi\right\rrbracket^{\mathcal{I}}=1-\left\llbracket% \varphi\right\rrbracket^{\mathcal{I}}$ and $\left\llbracket(\varphi\lor\psi)\right\rrbracket=\max\bigl{\{}\left\llbracket% \varphi\right\rrbracket^{\mathcal{I}},\left\llbracket\psi\right\rrbracket^{% \mathcal{I}}\bigr{\}}$ .
(4)

$\left\llbracket\exists x\,\varphi\right\rrbracket^{\mathcal{I}}=\max\bigl{\{}% \left\llbracket\varphi\right\rrbracket^{\mathcal{I}\frac{v}{x}}\ \mathrel{:}\ % v\in V(G)\bigr{\}}$ .
(5)

$\left\llbracket\bigl{(}s=\sum\mathtt{w}(\bar{x}).\varphi\bigr{)}\right% \rrbracket^{\mathcal{I}}=1$ if $s=\sum_{S}\bigl{\{}\mathtt{w}^{G}(\bar{v})\ \mathrel{:}\ \bar{v}=(v_{1},\dots,% v_{k})\in(V(G))^{k}\text{ with }\left\llbracket\varphi\right\rrbracket^{% \mathcal{I}\frac{v_{1},\dots,v_{k}}{x_{1},\dots,x_{k}}}=1\bigr{\}}$ , and $\left\llbracket\bigl{(}s=\sum\mathtt{w}(\bar{x}).\varphi\bigr{)}\right% \rrbracket^{\mathcal{I}}=0$ otherwise. As usual, $\sum_{S}X=0_{S}$ if $X=\emptyset$ .
(6)

$\left\llbracket\mathsf{P}(t_{1},\dots,t_{m})\right\rrbracket^{\mathcal{I}}=1$ if $\bigl{(}\left\llbracket t_{1}\right\rrbracket^{\mathcal{I}},\dots,\left% \llbracket t_{m}\right\rrbracket^{\mathcal{I}}\bigr{)}\in\left\llbracket% \mathsf{P}\right\rrbracket$ , and $\left\llbracket\mathsf{P}(t_{1},\ldots,t_{m})\right\rrbracket^{\mathcal{I}}=0$ otherwise.
(7)

$\left\llbracket s\right\rrbracket^{\mathcal{I}}=s$ for $s\in S$ for some $S\in\mathbb{S}$ .
(8)

$\left\llbracket\mathtt{w}(x_{1},\dots,x_{k})\right\rrbracket^{\mathcal{I}}=% \mathtt{w}^{G}\bigl{(}\beta(x_{1}),\dots,\beta(x_{k})\bigr{)}$ .
(9)

$\left\llbracket(t_{1}\ast t_{2})\right\rrbracket^{\mathcal{I}}=\left\llbracket t% _{1}\right\rrbracket^{\mathcal{I}}\ast_{S}\left\llbracket t_{2}\right% \rrbracket^{\mathcal{I}}$ , for $\ast\in\{+,-,{\cdot}\}$ .
(10)

$\left\llbracket\sum{p}.{\varphi}\right\rrbracket^{\mathcal{I}}=\sum_{S}\bigl{% \{}\left\llbracket p\right\rrbracket^{\mathcal{I}\frac{v_{1},\dots,v_{k}}{x_{1% },\dots,x_{k}}}\ \mathrel{:}\ v_{1},\dots,v_{k}\in V(G),\left\llbracket\varphi% \right\rrbracket^{\mathcal{I}\frac{v_{1},\dots,v_{k}}{x_{1},\dots,x_{k}}}=1% \bigr{\}}$ , where $\textup{vars}(p)=\{x_{1},\dots,x_{k}\}$ , $k=|\textup{vars}(p)|$ and $\left\llbracket p\right\rrbracket^{\mathcal{I}}=\left\llbracket t_{1}\right% \rrbracket^{\mathcal{I}}{\cdot}_{S}\cdots{\cdot}_{S}\left\llbracket t_{\ell}% \right\rrbracket^{\mathcal{I}}$ if $p=t_{1}{\cdot}\cdots{\cdot}t_{\ell}$ is of type $S$ .

An expression is a formula or an $\mathbb{S}$ -term. The set $\textup{vars}(\xi)$ of an expression $\xi$ is defined as the set of all variables in vars that occur in $\xi$ . The free variables $\operatorname*{free}(\xi)$ of $\xi$ are inductively defined as follows.

(1)

$\operatorname*{free}(x_{1}{=}x_{2})=\{x_{1},x_{2}\}$ and $\operatorname*{free}\bigl{(}R(x_{1},\dots,x_{k})\bigr{)}=\{x_{1},\dots,x_{k}\}$ for $R\in\sigma$ .
(2)

$\operatorname*{free}\Big{(}\bigl{(}s=\mathtt{w}(x_{1},\dots,x_{k})\bigr{)}\Big% {)}=\{x_{1},\dots,x_{k}\}$ .
(3)

$\operatorname*{free}(\neg\varphi)=\operatorname*{free}(\varphi)$ and $\operatorname*{free}(\varphi\lor\psi)=\operatorname*{free}(\varphi)\cup% \operatorname*{free}(\psi)$ .
(4)

$\operatorname*{free}(\exists x\,\varphi)=\operatorname*{free}(\varphi)% \setminus\{x\}$ .
(5)

$\operatorname*{free}\Big{(}\bigl{(}s=\sum\mathtt{w}(x_{1},\dots,x_{k}).\varphi% \bigr{)}\Big{)}=\operatorname*{free}(\varphi)\setminus\{x_{1},\dots,x_{k}\}$ ,
(6)

$\operatorname*{free}\bigl{(}\mathsf{P}(t_{1},\dots,t_{m})\bigr{)}=\bigcup_{i=1% }^{m}\operatorname*{free}(t_{i})$ .
(7)

$\operatorname*{free}(s)=\emptyset$ for $s\in S$ for some $S\in\mathbb{S}$ .
(8)

$\operatorname*{free}\bigl{(}\mathtt{w}(x_{1},\dots,x_{k})\bigr{)}=\{x_{1},% \dots,x_{k}\}$ .
(9)

$\operatorname*{free}\bigl{(}(t_{1}\ast t_{2})\bigr{)}=\operatorname*{free}(t_{% 1})\cup\operatorname*{free}(t_{2})$ for $\ast\in\{+,-,{\cdot}\}$ .
(10)

$\operatorname*{free}(\sum p.\varphi)=\operatorname*{free}(\varphi)\setminus% \textup{vars}(p)$ .

We write $\xi(x_{1},\dots,x_{k})$ to indicate that $\operatorname*{free}(\xi)\subseteq\{x_{1},\dots,x_{k}\}$ . A sentence is a formula without free variables, and a ground $\mathbb{S}$ -term is an $\mathbb{S}$ -term without free variables.

For a formula $\varphi$ and a $(\sigma,\mathbf{W})$ -interpretation $\mathcal{I}$ , we write $\mathcal{I}\models\varphi$ to indicate that $\left\llbracket\varphi\right\rrbracket^{\mathcal{I}}=1$ . Likewise, $\mathcal{I}\not\models\varphi$ indicates that $\left\llbracket\varphi\right\rrbracket^{\mathcal{I}}=0$ . For a formula $\varphi$ , a $(\sigma,\mathbf{W})$ -graph $G$ , and a tuple $\bar{v}=(v_{1},\dots,v_{k})\in\bigl{(}V(G)\bigr{)}{}^{k}$ , we write $G\models\varphi[\bar{v}]$ or $(G,\bar{v})\models\varphi$ to indicate that $(G,\beta)\models\varphi$ for one (and hence every) assignment $\beta$ with $\beta(x_{i})=v_{i}$ for all $i\in[k]$ . Furthermore, we set $\left\llbracket\varphi(\bar{v})\right\rrbracket^{G}\coloneqq 1$ if $G\models\varphi[\bar{v}]$ , and $\left\llbracket\varphi(\bar{v})\right\rrbracket^{G}\coloneqq 0$ otherwise. Similarly, for an $\mathbb{S}$ -term $t(\bar{x})$ , we write $t^{G}[\bar{v}]$ to denote $\left\llbracket t\right\rrbracket^{\mathcal{I}}$ . The fragments $\textup{{FOWA}}_{n}$ and $\textup{{FOW}}_{1}$ of FOWA are defined as follows.

Definition 2.4.

For every $n\in\mathbb{N}$ , the set of expressions of $\textup{{FOWA}}_{n}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ is built according to the same rules as for the logic $\textup{{FOWA}}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ , with the following restrictions:

$\blacksquare$

rule (5) can only be applied if $S$ is finite,
$\blacksquare$

rule (6) can only be applied if $\left\lvert\operatorname*{free}(t_{1})\cup\cdots\cup\operatorname*{free}(t_{m}% )\right\rvert\leqslant n$ .

$\textup{{FOW}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ is the restriction of $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ where rule (10) cannot be applied.

As pointed out in [5], $\textup{{FOW}}_{1}$ can be viewed as an extension of first-order logic with modulo-counting quantifiers, and FOWA and $\textup{{FOWA}}_{1}$ can be viewed as extensions of the counting logics FOC and $\textup{{FOC}}_{1}$ of [10] and [8]. In fact, every formula in FOC can be viewed as a formula in FOWA.

Note that first-order logic FO is the restriction of $\textup{{FOW}}_{1}$ where only rules (1), (3), and (4) can be applied. As usual, we write $(\varphi\land\psi)$ and $\forall x\,\varphi$ as shorthands for $\neg(\neg\varphi\lor\neg\psi)$ and $\neg\exists x\,\neg\varphi$ . The quantifier rank $\operatorname*{qr}(\xi)$ of an $\textup{{FOWA}}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ expression $\xi$ is defined as the maximum nesting depth of constructs using rules (4) and (5) in order to construct $\xi$ . The aggregation depth $\operatorname{d_{\textup{ag}}}(\xi)$ of $\xi$ is defined as the maximum nesting depth of term constructions using rule (10) in order to construct $\xi$ .

Example 2.5.

Consider the following setting. $\mathbb{S}$ consists of a single ring, the ring $(\mathbb{Z},+,\cdot)$ of integers with the natural addition and multiplication. $\mathbb{P}$ consists of a single predicate, the binary equality predicate $\mathsf{P}_{=}$ with $\left\llbracket\mathsf{P}_{=}\right\rrbracket=\{(i,i):i\in\mathbb{Z}\}$ . $\mathbf{W}$ consists of a single weight symbol $\mathtt{w}$ , and $\operatorname*{ar}(\mathtt{w})=2$ . Furthermore, $\sigma=\{E\}$ . We interpret a $(\sigma,\mathbf{W})$ -graph $G=(V(G),E(G),\mathtt{w}^{G})$ as a flow network, where $\mathtt{w}^{G}(u,v)$ indicates the flow through edge $\{u,v\}$ in the direction from $u$ to $v$ , and $\mathtt{w}^{G}(v,u)$ indicates the flow through edge $\{u,v\}$ in the direction from $v$ to $u$ .

The fact that a node $x$ is a source node, i.e., all edges incident with $x$ have weight 0 in the direction into $x$ , can be described by the $\textup{{FOW}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula $\textit{source}(x)\coloneqq\forall z\;(0=\mathtt{w}(z,x)).\,$ Similarly, $\textit{target}(y)\coloneqq\forall z\;(0=\mathtt{w}(y,z))$ is an $\textup{{FOW}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula expressing that node $y$ is a target node, i.e., all edges incident with $y$ have weight 0 in the direction outgoing from $y$ . Furthermore, $t_{\textit{in}}(z)\coloneqq\sum\mathtt{w}(u,z^{\prime}).(z^{\prime}{=}z\land E% (u,z^{\prime}))$ is a term of $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ which specifies the total flow through edges incoming into node $z$ . Moreover, $t_{\textit{out}}(z)\coloneqq\sum\mathtt{w}(z^{\prime},u).(z^{\prime}{=}z\land E% (z^{\prime},u))$ is a term of $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ which specifies the total flow through edges going out of node $z$ . Thus, $\psi(z)\coloneqq\mathsf{P}_{=}(t_{\textit{in}}(z),t_{\textit{out}}(z))$ is a $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula expressing that for node $z$ , the incoming flow is equal to its outgoing flow. Finally, $\varphi(x,y)\coloneqq((\textit{source}(x)\land\textit{target}(y))\land\forall z% \;((z{=}x\lor z{=}y)\lor\psi(z)))$ is a $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula expressing the following: $G\models\varphi[s,t]$ for nodes $s,t\in V(G)$ if and only if $\mathtt{w}^{G}$ is a feasible flow for the flow network $G$ with source and sink nodes $s$ and $t$ , i.e., for all vertices $v\in V(G)\setminus\{s,t\}$ the incoming flow is equal to its outgoing flow.

Locality Results

For proving the main results (2)–(5) stated in Section 1, we heavily rely on the following two locality results achieved in [5].

Theorem 2.6 (Feferman–Vaught decompositions for $\textup{{FOW}}_{1}$ [5, Theorem 4.3]).

Let $k,\ell\in\mathbb{N}$ , and let $\bar{x}=(x_{1},\dots,x_{k})$ , $\bar{y}=(y_{1},\dots,y_{\ell})$ be tuples of $k+\ell$ pairwise distinct variables. For every $\textup{{FOW}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula $\varphi$ with free variables among $\{x_{1},\dots,x_{k},y_{1},\dots,y_{\ell}\}$ , there is a finite, non-empty set $\Delta$ of pairs $(\alpha,\beta)$ of $\textup{{FOW}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formulas with $\operatorname*{free}(\alpha)\subseteq\{x_{1},\dots,x_{k}\}$ and $\operatorname*{free}(\beta)\subseteq\{y_{1},\dots,y_{\ell}\}$ such that the following holds. For all $(\sigma,\mathbf{W})$ -graphs $G$ and $H$ with $V(G)\cap V(H)=\emptyset$ and all $\bar{v}\in(V(G))^{k}$ and $\bar{w}\in(V(H))^{\ell}$ , we have $G\uplus H\models\varphi[\bar{v},\bar{w}]$ if and only if there is a pair $(\alpha,\beta)\in\Delta$ with $G\models\alpha[\bar{v}]$ and $H\models\beta[\bar{w}]$ .

Furthermore, all formulas occurring in $\Delta$ have quantifier rank at most $\operatorname*{qr}(\varphi)$ , and they only use those $\mathsf{P}\in\mathbb{P}$ and $S\in\mathbb{S}$ that occur in $\varphi$ and only those $\mathbb{S}$ -terms that occur in $\varphi$ or that are of the form $s$ for an $s\in S$ with $S\in\mathbb{S}$ where $S$ is finite and occurs in $\varphi$ .

Moreover, there is an algorithm that computes $\Delta$ upon input of $\varphi$ , $\bar{x}$ , and $\bar{y}$ .

For stating the second locality result, we need the following notation of local formulas. Let $r\in\mathbb{N}$ . A FOWA formula $\varphi(\bar{x})$ with free variables $\bar{x}=(x_{1},\ldots,x_{d})$ is $r$ -local (around $\bar{x}$ ) if for every $(\sigma,\mathbf{W})$ -graph $G$ and all $\bar{a}\in V(G)^{d}$ , we have $G\models\varphi[\bar{a}]\iff\mathcal{N}_{r}^{G}(\bar{a})\models\varphi[\bar{a}]$ . A formula is local if it is $r$ -local for some $r\in\mathbb{N}$ .

Theorem 2.7 (Localisation Theorem for $\textup{{FOWA}}_{1}$ [5, Theorem 4.7]).

Let $d\in\mathbb{N}$ . For every formula $\varphi(x_{1},\dots,x_{d})$ of $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ , there is an $r\in\mathbb{N}$ , an extension $\sigma^{\prime}$ of $\sigma$ with relation symbols of arity $\leqslant 1$ , and an $\textup{{FOW}}_{1}(\mathbb{P})[\sigma^{\prime},\mathbb{S},\mathbf{W}]$ formula $\varphi^{\prime}(x_{1},\dots,x_{d})$ that is a Boolean combination of $r$ -local formulas and statements of the form $R()$ for a $0$ -ary relation symbol $R\in\sigma^{\prime}$ such that the following holds. There is an algorithm that, upon input of a $(\sigma,\mathbf{W})$ -graph $G$ , computes in time $|V(G)|\cdot(\deg(G))^{\mathcal{O}(1)}$ a $(\sigma^{\prime},\mathbf{W})$ -expansion $G^{\prime}$ of $G$ such that, for all $\bar{v}\in V(G)^{d}$ , it holds that $G^{\prime}\models\varphi^{\prime}[\bar{v}]$ if and only if $G\models\varphi[\bar{v}]$ . Furthermore, $r$ , $\sigma^{\prime}$ , and $\varphi^{\prime}$ are computable from $\varphi$ .

3 $\textup{{FOC}}_{2}$ has Unbounded VC Dimension

This section proves main result (1) stated in Section 1. Let $\sigma\coloneqq\{E\}$ . Let $\mathbb{S}$ consist of the integer ring $(\mathbb{Z},+,\cdot)$ , and let $\mathbf{W}$ consist of a unary weight symbol $\mathtt{one}$ . We identify a graph $G=(V(G),E(G))$ with a $(\sigma,\mathbf{W})$ -graph by letting $\mathtt{one}^{G}(v)=1$ for all $v\in V(G)$ . For a formula $\varphi$ , we write $\#{(y_{1},\ldots,y_{j})}.{\varphi}$ for the weight aggregation term $\sum p.\varphi$ for $p\coloneqq\mathtt{one}(y_{1})\cdots\mathtt{one}(y_{j})$ . Note that this term evaluates to the number of tuples $(a_{1},\ldots,a_{j})\in V(G)^{j}$ for which the formula $\varphi$ is satisfied when assigning the variables $y_{1},\ldots,y_{j}$ the vertices $a_{1},\ldots,a_{j}$ . Let $\mathbb{P}$ be the predicate collection consisting only of the equality predicate $\mathsf{P}_{=}$ , where $\left\llbracket\mathsf{P}_{=}\right\rrbracket=\{(i,i):i\in\mathbb{Z}\}$ . The logic $\textup{{FOC}}(\mathbb{P})[\sigma]$ considered in [8] precisely corresponds to the logic $\textup{{FOWA}}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ , and $\textup{{FOC}}_{n}(\mathbb{P})[\sigma]$ corresponds to $\textup{{FOWA}}_{n}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ , for $n\in\mathbb{N}$ .

Theorem 3.1.

Let $\mathcal{T}_{3}$ be the class of undirected, unranked trees of height at most 3. There is an $\textup{{FOC}}_{2}(\mathbb{P})[\sigma]$ formula $\psi(x,y)$ such that, for every $n\in\mathbb{N}$ , there exist $H\in\mathcal{T}_{3}$ and $W^{\prime}\subseteq V(H)$ with $|W^{\prime}|=n$ and $|S^{\varphi}_{H}(V(H)/W^{\prime})|=2^{|W^{\prime}|}$ . In particular, this implies that $\psi(x,y)$ has unbounded VC dimension on $\mathcal{T}_{3}$ .

Proof.

Recall the notions introduced at the beginning of Section 1. In particular, we write $S^{\varphi}(G/W)$ as a shorthand for $S^{\varphi}_{G}(V(G)/W)$ .

Let $\mathcal{C}_{\textit{all}}$ be the class of all graphs. The proof of [8, Theorem 4.1] associates with every $G\in\mathcal{C}_{\textit{all}}$ a tree $H_{G}\in\mathcal{T}_{3}$ and an injective mapping $\pi_{G}$ from $V(G)$ to $V(H_{G})$ . Furthermore, the construction presented there allows associating with every $\textup{{FO}}[\sigma]$ formula $\varphi(x,y)$ an $\textup{{FOC}}_{2}(\mathbb{P})[\sigma]$ formula $\hat{\varphi}(x,y)$ such that the following is true for every $G\in\mathcal{C}_{\textit{all}}$ :

1.

For all $v,w\in V(G)$ , we have: $G\models\varphi[v,w]$ $\iff$ $H_{G}\models\hat{\varphi}[\pi_{G}(v),\pi_{G}(w)]$ .
2.

For all $v^{\prime},w^{\prime}\in V(H_{G})$ with $v^{\prime}\not\in\mathrm{img}(\pi_{G})$ or $w^{\prime}\not\in\mathrm{img}(\pi_{G})$ , we have: $H_{G}\not\models\hat{\varphi}[v^{\prime},w^{\prime}]$ .

This implies that for all $W\subseteq V(G)$ and all $v\in V(G)$ we have:
$\pi_{G}(\textup{tp}^{\varphi}_{G}(v/W))=\{w^{\prime}\in\pi_{G}(W):H_{G}\models% \hat{\varphi}[\pi_{G}(v),w^{\prime}]\}=\textup{tp}^{\hat{\varphi}}_{H_{G}}(\pi% _{G}(v)/\pi_{G}(W))$ .
Hence, $\pi_{G}(S^{\varphi}(G/W))\subseteq S^{\hat{\varphi}}(H_{G}/\pi_{G}(W))$ , and thus

|\,S^{\varphi}(G/W)\,|\ \ \leqslant\ \ |\,S^{\hat{\varphi}}(H_{G}/\pi_{G}(W))% \,|.

(1)

Consider the FO formula $\varphi(x,y)\coloneqq E(x,y)$ . For every $n\in\mathbb{N}$ , there is a graph $G\in\mathcal{C}_{\textit{all}}$ and a set $W\subseteq V(G)$ with $\left\lvert W\right\rvert=n$ and $\left\lvert S^{\varphi}(G/W)\right\rvert=2^{\left\lvert W\right\rvert}$ . For example, we could use the graph $G$ with $V(G)\coloneqq[n]\uplus\{0,1\}^{n}$ , $E(G)\coloneqq\bigl{\{}\{i,\bar{w}\}\ \mathrel{:}\ i\in\mathbb{N},\bar{w}\in\{0% ,1\}^{n},w_{i}=1\bigr{\}}$ , and $W\coloneqq[n]$ . Let $W^{\prime}\coloneqq\pi_{G}(W)$ , and note that $|W^{\prime}|=|W|=n$ . From Equation 1, we obtain that $2^{|W|}=|S^{\varphi}(G/W)|\leqslant|S^{\hat{\varphi}}(H_{G}/W^{\prime})|% \leqslant 2^{|W^{\prime}|}=2^{|W|}$ . Therefore, $|S^{\hat{\varphi}}(H_{G}/W^{\prime})|=2^{|W^{\prime}|}$ . Choosing $\psi(x,y)$ to be the formula $\hat{\varphi}(x,y)$ thus proves the first statement of Theorem 3.1. The second statement of the theorem is an immediate consequence of its first statement and the definition of the notion of VC dimension. $\hfill\blacktriangleleft$

4 Bound on the Number of Types

In this section, we prove the main technical tool for this paper. For that, we use the following notation. For every $k\in\mathbb{N}$ , $I=\{i_{1},\dots,i_{\ell}\}\subseteq[k]$ with $i_{1}<i_{2}<\cdots<i_{\ell}$ , and for a tuple $\bar{v}=(v_{1},\dots,v_{k})$ , we let $\bar{v}_{I}\coloneqq(v_{i_{1}},v_{i_{2}},\dots,v_{i_{\ell}})$ be the tuple obtained from $\bar{v}$ by keeping only entries at positions contained in $I$ .

Lemma 4.1.

There are computable functions $T\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\times% \mathbb{N}\to\mathbb{N}$ and $r\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\to\mathbb% {N}$ such that, for every $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula $\varphi(\bar{x},\bar{y})$ , every $m\in\mathbb{N}$ , every $(\sigma,\mathbf{W})$ -graph $G$ , and all $V,W\subseteq V(G)$ that are $r(\varphi)$ -separated by a set of size at most $m$ , we have $\left\lvert S^{\varphi}_{G}(V/W)\right\rvert\leqslant T(\varphi,m)$ .

Proof.

Let $\varphi(\bar{x},\bar{y})\in\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},% \mathbf{W}]$ , $k\coloneqq\left\lvert\bar{x}\right\rvert$ , and $\ell\coloneqq\left\lvert\bar{y}\right\rvert$ . W.l.o.g., we assume that $\mathbb{P}$ , $\sigma$ , $\mathbb{S}$ , and $\mathbf{W}$ only contain elements that occur in $\varphi$ . Using Theorem 2.7, from $\varphi$ , we can compute an $r^{\prime}\in\mathbb{N}$ , an extension $\sigma^{\prime}$ of $\sigma$ with relation symbols of arity $\leqslant 1$ , and an $\textup{{FOW}}_{1}(\mathbb{P})[\sigma^{\prime},\mathbb{S},\mathbf{W}]$ formula $\varphi^{\prime}(\bar{x},\bar{y})$ that is a Boolean combination of $r^{\prime}$ -local formulas and statements of the form $R()$ for a $0$ -ary relation symbol $R\in\sigma^{\prime}$ such that the following holds. For every $(\sigma,\mathbf{W})$ -graph $G$ , there is a $(\sigma^{\prime},\mathbf{W})$ -expansion $G^{\prime}$ of $G$ such that for all $\bar{v}\in\bigl{(}V(G)\bigr{)}{}^{k}$ and $\bar{w}\in\bigl{(}V(G)\bigr{)}{}^{\ell}$ , it holds that $G\models\varphi[\bar{v},\bar{w}]$ if and only if $G^{\prime}\models\varphi^{\prime}[\bar{v},\bar{w}]$ . We set $r(\varphi)\coloneqq 2r^{\prime}+1$ . Note that, for all $V,W\subseteq V(G)$ , we have that $S_{\varphi}^{G}(V/W)=S_{\varphi^{\prime}}^{G^{\prime}}(V/W)$ .

Let $m\in\mathbb{N}$ . We extend $\sigma^{\prime}$ and $\mathbf{W}$ to be able to remove a set of vertices of size at most $m$ from $G^{\prime}$ and encode the missing information in the remaining graph. For that, for every $i,j\in[m]$ , we introduce a new $0$ -ary relation symbol $R_{i}$ for every unary relation symbol $R\in\sigma^{\prime}$ , we introduce the new unary relation symbol $E_{i}$ , and we introduce the new $0$ -ary relation symbol $E_{i,j}$ . Analogously, for every $i\in[m]$ , we introduce two new unary weight symbols $\mathtt{w}_{i,1},\mathtt{w}_{i,2}$ for every binary weight symbol $\mathtt{w}\in\mathbf{W}$ . In addition, for all $i,j\in[m]$ , for all weight symbols $\mathtt{w}\in\mathbf{W}$ , for all $s\in\textup{type}(\mathtt{w})$ that occur in $\varphi^{\prime}$ (and $\textup{type}(\mathtt{w})$ may be infinite) and all $s\in\textup{type}(\mathtt{w})$ if $\textup{type}(\mathtt{w})$ is finite, we add the new $0$ -ary relation symbol $R_{\mathtt{w},i,s}$ if $\mathtt{w}$ is a unary weight symbol, and we add the new $0$ -ary relation symbol $R_{\mathtt{w},i,j,s}$ if $\mathtt{w}$ is a binary weight symbol. Let $\sigma_{m}$ and $\mathbf{W}_{m}$ denote the resulting signature and the resulting set of weight symbols, respectively. Note that both $\sigma_{m}$ and $\mathbf{W}_{m}$ are finite.

Claim 4.2.

Let $H$ be a $(\sigma^{\prime},\mathbf{W})$ -graph, let $z_{1},\dots,z_{t}\in V(H)$ be pairwise distinct vertices with $t\leqslant m$ , let $Z\coloneqq\{z_{1},\dots,z_{t}\}$ , and let $\psi(x^{\prime}_{1},\dots,x^{\prime}_{p})\in\textup{{FOW}}_{1}(\mathbb{P})[% \sigma^{\prime},\mathbb{S},\mathbf{W}]$ for some $p\in\mathbb{N}$ .

There is a $(\sigma_{m},\mathbf{W}_{m})$ -expansion $H_{\bar{z},\psi}$ of $H\setminus Z$ such that for every mapping $f\colon[p]\to[0,t]$ , there is a $\textup{{FOW}}_{1}(\mathbb{P})[\sigma_{m},\mathbb{S},\mathbf{W}_{m}]$ formula $\psi_{H,\bar{z},f}(\bar{x}^{\prime\prime})$ , where $\bar{x}^{\prime\prime}$ is obtained from $\bar{x}^{\prime}$ by dropping all variables $x^{\prime}_{i}$ with $f(i)\neq 0$ , with the following properties.

For all $\bar{v}\in(V(H))^{p}$ , we have that $H\models\psi[\bar{v}]$ if and only if $H_{\bar{z},\psi}\models\psi_{H,\bar{z},f}[\bar{v}^{\prime}]$ , where $\bar{v}^{\prime}$ is obtained from $\bar{v}$ by dropping all elements that are contained in $Z$ , and $f\colon[p]\to[0,t]$ maps $i\in[p]$ to $j\in[t]$ if $v_{i}=z_{j}$ , and it maps $i\in[p]$ to $0$ if $v_{i}\not\in Z$ .

Further, for a fixed formula $\psi$ and a fixed mapping $f$ , the formulas $\psi_{H,\bar{z},f}$ are structurally identical. That is, the syntax trees of all the formulas $\psi_{H,\bar{z},f}$ have the same inner nodes, and the leaf nodes that do not represent constants from rule (7) coincide. Hence, the dependence on $H$ and $\bar{z}$ is only reflected in the use of different constants for rule (7).

Proof.

Let $H$ be a $(\sigma^{\prime},\mathbf{W})$ -graph, let $z_{1},\dots,z_{t}\in V(H)$ be pairwise distinct vertices with $t\leqslant m$ , let $Z\coloneqq\{z_{1},\dots,z_{t}\}$ , and let $\psi(x^{\prime}_{1},\dots,x^{\prime}_{p})\in\textup{{FOWA}}_{1}(\mathbb{P})[% \sigma,\mathbb{S},\mathbf{W}]$ for some $p\in\mathbb{N}$ .

We use the new relation symbols $R_{i}$ and $E_{i,j}$ to encode whether $z_{i}\in R(H)$ and $\{z_{i},z_{j}\}\in E(H)$ , and we let $E_{i}$ include all vertices $v$ such that $\{z_{i},v\}\in E(H)$ . The relation symbols $R_{\mathtt{w},i,s}$ and $R_{\mathtt{w}^{\prime},i,j,s}$ are used to encode whether $\mathtt{w}^{H}(z_{i})=s$ and $(\mathtt{w}^{\prime})^{H}(z_{i},z_{j})=s$ . Finally, the unary weight symbols $\mathtt{w}_{i,1}$ and $\mathtt{w}_{i,2}$ are used to encode the weights $\mathtt{w}^{H}(z_{i},v)$ and $\mathtt{w}^{H}(v,z_{i})$ for all $v\in V(H)\setminus Z$ . Formally, we let $H_{\bar{z},\psi}$ be the $(\sigma_{m},\mathbf{W}_{m})$ -expansion of $H\setminus Z$ with

$\blacksquare$

$R_{i}(H_{\bar{z},\psi})\coloneqq\top$ if and only if $i\in[t]$ and $z_{i}\in R$ , for all unary $R\in\sigma^{\prime}$ and $i\in[m]$ ,
$\blacksquare$

$E_{i}(H_{\bar{z},\psi})\coloneqq N_{1}^{H}(z_{i})$ , for all $i\in[t]$ ,
$\blacksquare$

$E_{i}(H_{\bar{z},\psi})\coloneqq\emptyset$ , for all $i\in[m]\setminus[t]$ ,
$\blacksquare$

$E_{i,j}(H_{\bar{z},\psi})\coloneqq\top$ if and only if $i,j\in[t]$ and $\{z_{i},z_{j}\}\in E(H)$ , for all $i,j\in[m]$ ,
$\blacksquare$

$R_{\mathtt{w},i,s}(H_{\bar{z},\psi})\coloneqq\top$ if and only if $i\in[t]$ and $\mathtt{w}^{H}(z_{i})=s$ , for all unary $\mathtt{w}\in\mathbf{W}$ and all $s\in\textup{type}(\mathtt{w})$ that occur in $\psi$ and all $s\in\textup{type}(\mathtt{w})$ if $\textup{type}(\mathtt{w})$ is finite,
$\blacksquare$

$R_{\mathtt{w},i,j,s}(H_{\bar{z},\psi})\coloneqq\top$ if and only if $i,j\in[t]$ and $\mathtt{w}^{H}(z_{i},z_{j})=s$ , for all binary $\mathtt{w}\in\mathbf{W}$ and all $s\in\textup{type}(\mathtt{w})$ that occur in $\psi$ and all $s\in\textup{type}(\mathtt{w})$ if $\textup{type}(\mathtt{w})$ is finite,
$\blacksquare$

$\mathtt{w}_{i,1}^{H_{\bar{z},\psi}}\colon V(H_{\bar{z},\psi})\to\textup{type}(% \mathtt{w}),v\mapsto\mathtt{w}^{H}(z_{i},v)$ , for all binary $\mathtt{w}\in\mathbf{W}$ and $i\in[t]$ ,
$\blacksquare$

$\mathtt{w}_{i,2}^{H_{\bar{z},\psi}}\colon V(H_{\bar{z},\psi})\to\textup{type}(% \mathtt{w}),v\mapsto\mathtt{w}^{H}(v,z_{i})$ , for all binary $\mathtt{w}\in\mathbf{W}$ and $i\in[t]$ , and
$\blacksquare$

$\mathtt{w}_{i,j}^{H_{\bar{z},\psi}}\colon V(H_{\bar{z},\psi})\to\textup{type}(% \mathtt{w}),v\mapsto 0$ , for all binary $\mathtt{w}\in\mathbf{W}$ , $j\in[2]$ , and $i\in[m]\setminus[t]$ .

Next, for every mapping $f\colon[p]\to[0,t]$ , we recursively construct a $\textup{{FOW}}_{1}(\mathbb{P})[\sigma_{m},\mathbb{S},\mathbf{W}_{m}]$ formula $\psi_{H,\bar{z},f}(\bar{x}^{\prime\prime})$ , where $\bar{x}^{\prime\prime}$ is obtained from $\bar{x}^{\prime}$ by dropping all variables $x^{\prime}_{i}$ with $f(i)\neq 0$ . Intuitively, if $f(i)\neq 0$ , then this indicates that the variable $x^{\prime}_{i}$ should be replaced by the vertex $z_{f(i)}$ . For all $i\in[p]$ and $j\in[0,t]$ , we let $f_{i\to j}\colon[p]\to[0,t]$ be the mapping with $f_{i\to j}(i^{\prime})\coloneqq f(i^{\prime})$ for all $i^{\prime}\neq i$ and $f_{i\to j}(i)\coloneqq j$ . Moreover, for $i,i^{\prime}\in[p]$ and $j,j^{\prime}\in[0,t]$ , we analogously define $f_{i\to j,i^{\prime}\to j^{\prime}}\colon[p]\to[0,t]$ .

(1)

If $\psi$ is of the form $x^{\prime}_{i}{=}x^{\prime}_{j}$ , then we let $\psi_{H,\bar{z},f}\coloneqq\psi$ if $f(i)=f(j)=0$ , $\psi_{H,\bar{z},f}\coloneqq\top$ if $f(i)=f(j)\neq 0$ , and $\psi_{H,\bar{z},f}\coloneqq\bot$ else. If $\psi$ is of the form $R()$ , or $\psi$ is of the form $R(x^{\prime}_{i})$ and $f(i)=0$ , or $\psi$ is of the form $E(x^{\prime}_{i},x^{\prime}_{j})$ and $f(i)=f(j)=0$ , then we let $\psi_{H,\bar{z},f}\coloneqq\psi$ . If $\psi$ is of the form $R(x^{\prime}_{i})$ and $f(i)\neq 0$ , then we let $\psi_{H,\bar{z},f}\coloneqq R_{f(i)}()$ . If $\psi$ is of the form $E(x^{\prime}_{i},x^{\prime}_{j})$ and $f(i)\neq 0$ and $f(j)=0$ , then we let $\psi_{H,\bar{z},f}\coloneqq E_{f(i)}(x^{\prime}_{j})$ . If $\psi$ is of the form $E(x^{\prime}_{i},x^{\prime}_{j})$ and $f(i)=0$ and $f(j)\neq 0$ , then we let $\psi_{H,\bar{z},f}\coloneqq E_{f(j)}(x^{\prime}_{i})$ . If $\psi$ is of the form $E(x^{\prime}_{i},x^{\prime}_{j})$ and $f(i),f(j)\neq 0$ , then we let $\psi_{H,\bar{z},f}\coloneqq E_{f(i),f(j)}()$ .
(2)

If $\psi$ is of the form $\bigl{(}s{=}\mathtt{w}(x^{\prime}_{i})\bigr{)}$ and $f(i)=0$ , or $\psi$ is of the form $\bigl{(}s{=}\mathtt{w}(x^{\prime}_{i},x^{\prime}_{j})\bigr{)}$ and $f(i)=f(j)=0$ , then we let $\psi_{H,\bar{z},f}\coloneqq\psi$ . If $\psi$ is of the form $\bigl{(}s{=}\mathtt{w}(x^{\prime}_{i})\bigr{)}$ and $f(i)\neq 0$ , then we let $\psi_{H,\bar{z},f}\coloneqq R_{\mathtt{w},f(i),s}$ . If $\psi$ is of the form $\bigl{(}s{=}\mathtt{w}(x^{\prime}_{i},x^{\prime}_{j})\bigr{)}$ and $f(i),f(j)\neq 0$ , then we let $\psi_{H,\bar{z},f}\coloneqq R_{\mathtt{w},f(i),f(j),s}$ . If $\psi$ is of the form $\bigl{(}s{=}\mathtt{w}(x^{\prime}_{i},x^{\prime}_{j})\bigr{)}$ and $f(i)\neq 0$ and $f(j)=0$ , then we let $\psi_{H,\bar{z},f}\coloneqq\bigl{(}s{=}\mathtt{w}_{f(i),1}(x^{\prime}_{j})% \bigr{)}$ . If $\psi$ is of the form $\bigl{(}s{=}\mathtt{w}(x^{\prime}_{i},x^{\prime}_{j})\bigr{)}$ and $f(i)=0$ and $f(j)\neq 0$ , then we let $\psi_{H,\bar{z},f}\coloneqq\bigl{(}s{=}\mathtt{w}_{f(j),2}(x^{\prime}_{i})% \bigr{)}$ .
(3)

If $\psi$ is of the form $(\psi^{\prime}\lor\psi^{\prime\prime})$ , then we recursively construct $\psi^{\prime}_{H,\bar{z},f}$ and $\psi^{\prime\prime}_{H,\bar{z},f}$ , and we let $\psi_{H,\bar{z},f}\coloneqq(\psi^{\prime}_{H,\bar{z},f}\lor\psi^{\prime\prime}% _{H,\bar{z},f})$ . If $\psi$ is of the form $\neg\psi^{\prime}$ , then we recursively construct $\psi^{\prime}_{H,\bar{z},f}$ , and we let $\psi_{H,\bar{z},f}\coloneqq\neg\psi^{\prime}_{H,\bar{z},f}$ .
(4)

If $\psi$ is of the form $\exists x^{\prime}_{i}\,\psi^{\prime}$ , then we recursively construct $\psi^{\prime}_{H,\bar{z},f_{i\to j}}$ for all $j\in[0,t]$ . We let $\psi_{H,\bar{z},f}\coloneqq(\exists x^{\prime}_{i}\,\psi^{\prime}_{H,\bar{z},f% _{i\to 0}}\lor\bigvee_{j=1}^{t}\psi^{\prime}_{H,\bar{z},f_{i\to j}})$ .

(5)

If $\psi$ is of the form $\bigl{(}s{=}\sum{\mathtt{w}(x^{\prime}_{i})}.{\psi^{\prime}}\bigr{)}$ for a unary weight symbol $\mathtt{w}\in\mathbf{W}$ of finite type $S\coloneqq\textup{type}(\mathtt{w})$ , then we recursively construct $\psi^{\prime}_{H,\bar{z},f_{i\to j}}$ for all $j\in[0,t]$ . We let

\psi_{H,\bar{z},f}\coloneqq\bigvee_{\begin{subarray}{c}s_{0},s_{1},\dots,s_{t}% \in S\\ s_{0}+s_{1}+\dots+s_{t}=s\end{subarray}}\Bigl{(}s_{0}{=}\sum{\mathtt{w}(x^{% \prime}_{i})}.{\bigl{(}\psi^{\prime}_{H,\bar{z},f_{i\to 0}}}\land\bigwedge_{j=% 1}^{t}(R_{\mathtt{w},j,s_{j}}\land\psi^{\prime}_{H,\bar{z},f_{i\to j}})\bigr{)% }\Bigr{)}.

If $\psi$ is of the form $\bigl{(}s{=}\sum{\mathtt{w}(x^{\prime}_{i},x^{\prime}_{i^{\prime}})}.{\psi^{% \prime}}\bigr{)}$ for a binary weight symbol $\mathtt{w}\in\mathbf{W}$ of finite type $S\coloneqq\textup{type}(\mathtt{w})$ , then we recursively construct $\psi^{\prime}_{H,\bar{z},f_{i\to j,i^{\prime}\to j^{\prime}}}$ for all $j,j^{\prime}\in[0,t]$ . We let

	$\displaystyle\psi_{H,\bar{z},f}\coloneqq\bigvee_{\begin{subarray}{c}s_{0,0},s_% {0,1},\dots,s_{0,t},s_{1_{0}},\dots,s_{t,t}\in S\\ s_{0_{0}}+s_{0,1}+\dots+s_{t,t}=s\end{subarray}}$	$\displaystyle\Bigl{(}s_{0}{=}\sum{\mathtt{w}(x^{\prime}_{i},x^{\prime}_{i^{% \prime}})}.{\bigl{(}\psi^{\prime}_{H,\bar{z},f_{i\to 0,i^{\prime}\to 0}}}$
		$\displaystyle\land\bigwedge_{j=1}^{t}\bigwedge_{j^{\prime}=1}^{t}(R_{\mathtt{w% },j,j^{\prime},s_{j,j^{\prime}}}\land\psi^{\prime}_{H,\bar{z},f_{i\to j,i^{% \prime}\to j^{\prime}}})\bigr{)}\Bigr{)}.$

(6)

Finally, if $\psi$ is of the form $\mathsf{P}(t_{1},\dots,t_{j})$ , then $t_{1},\dots,t_{j}$ are terms according to rules (7)–(9), and they have at most one free variable, say $x^{\prime}_{i}$ . If $f(i)=0$ , then we let $\psi_{H,\bar{z},f}\coloneqq\psi$ . Otherwise, we let $t^{\prime}_{1},\dots,t^{\prime}_{j}$ be the terms obtained from $t_{1},\dots,t_{j}$ by replacing every occurrence of a term of the form $\mathtt{w}(x^{\prime}_{i})$ by the constant $\mathtt{w}^{H}(z_{f(i)})$ and every occurrence of a term of the form $\mathtt{w}(x^{\prime}_{i},x^{\prime}_{i})$ by the constant $\mathtt{w}^{H}(z_{f(i)},z_{f(i)})$ . We set $\psi_{H,\bar{z},f}\coloneqq\mathsf{P}(t^{\prime}_{1},\dots,t^{\prime}_{j})$ .

It follows from the construction that, for all $\bar{v}\in(V(H))^{p}$ , we have $H\models\psi[\bar{v}]$ if and only if $H_{\bar{z},\psi}\models\psi_{H,\bar{z},f}[\bar{v}^{\prime}]$ , where $\bar{v}^{\prime}$ is obtained from $\bar{v}$ by dropping all elements that are contained in $Z$ , and $f\colon[p]\to[0,t]$ maps $i\in[p]$ to $j\in[t]$ if $v_{i}=z_{j}$ , and it maps $i\in[p]$ to $0$ if $v_{i}\not\in Z$ .

Moreover, for a fixed formula $\psi$ and a fixed mapping $f$ , the formulas $\psi_{H,\bar{z},f}$ are structurally identical. That is, the syntax trees of all the formulas $\psi_{H,\bar{z},f}$ have the same inner nodes, and even the leaf nodes that do not represent constants from some abelian group or ring (rule (7)) coincide. Hence, the dependence on $H$ and $\bar{z}$ is only reflected in the use of different constants for rule (7). $\hfill\vartriangleleft$

Let $V,W\subseteq V(G)$ , let $z_{1},\dots,z_{t}\in V(G)$ be pairwise distinct vertices with $t\leqslant m$ such that $V$ and $W$ are $r(\varphi)$ -separated in $G$ (and thus also in $G^{\prime}$ ) by the set $Z\coloneqq\{z_{1},\dots,z_{t}\}$ , and let $\bar{z}\coloneqq(z_{1},\dots,z_{t})$ . W.l.o.g., we may assume that every vertex from $Z$ is contained in some path from $V$ to $W$ in $G$ of length at most $r(\varphi)=2r^{\prime}+1$ , so $Z\subseteq V\bigl{(}\mathcal{N}_{r^{\prime}}^{G^{\prime}}(V\cup W)\bigr{)}$ .

By applying 4.2 to $H\coloneqq\mathcal{N}_{r^{\prime}}^{G^{\prime}}(V\cup W)$ , $z_{1},\dots,z_{t}$ , and $\varphi^{\prime}$ , we obtain a $(\sigma_{m},\mathbf{W}_{m})$ -expansion $H_{\bar{z},\varphi^{\prime}}$ of $H\setminus Z$ and, for every mapping $f\colon[k+\ell]\to[0,t]$ , a $\textup{{FOW}}_{1}(\mathbb{P})[\sigma_{m},\mathbb{S},\mathbf{W}_{m}]$ formula $\varphi^{\prime}_{H,\bar{z},f}$ . Since $V$ is $(2r^{\prime}+1)$ -separated from $W$ by $Z$ , there is no path from $V\setminus Z$ to $W\setminus Z$ in $H\setminus Z=\mathcal{N}_{r^{\prime}}^{G^{\prime}}(V\cup W)\setminus Z$ . Hence, there are $(\sigma_{m},\mathbf{W}_{m})$ -graphs $H_{V}$ and $H_{W}$ such that $V\setminus Z\subseteq V(H_{V})$ , $W\setminus Z\subseteq V(H_{W})$ , and $H_{\bar{z},\varphi^{\prime}}=H_{V}\uplus H_{W}$ .

Let $\bar{v}\in V^{k}$ and $\bar{w}\in W^{\ell}$ . We have $G\models\varphi[\bar{v},\bar{w}]$ if and only if $G^{\prime}\models\varphi^{\prime}[\bar{v},\bar{w}]$ . Moreover, since $\varphi^{\prime}$ is a Boolean combination of $r^{\prime}$ -local formulas and statements of the form $R()$ for a $0$ -ary relation symbol $R\in\sigma^{\prime}$ , we have that $G^{\prime}\models\varphi^{\prime}[\bar{v},\bar{w}]$ if and only if $\mathcal{N}_{r^{\prime}}^{G^{\prime}}(\bar{v}\bar{w})\models\varphi^{\prime}[% \bar{v},\bar{w}]$ if and only if $\mathcal{N}_{r^{\prime}}^{G^{\prime}}(V\cup W)\models\varphi^{\prime}[\bar{v},% \bar{w}]$ . Furthermore, by 4.2, it holds that $\mathcal{N}_{r^{\prime}}^{G^{\prime}}(V\cup W)\models\varphi^{\prime}[\bar{v},% \bar{w}]$ if and only if $H_{\bar{z},\varphi^{\prime}}\models\varphi^{\prime}_{H,\bar{z},f}[\bar{v}^{% \prime},\bar{w}^{\prime}]$ , where $\bar{v}^{\prime}$ and $\bar{w}^{\prime}$ are obtained from $\bar{v}$ and $\bar{w}$ , respectively, by dropping all entries that are contained in $Z$ , and $f\colon[k+\ell]\to[0,t]$ is defined by $f(i)\coloneqq j$ if $i\leqslant k$ and $v_{i}=z_{j}$ or $i>k$ and $w_{i-k}=z_{j}$ , and $f(i)\coloneqq 0$ if $i\leqslant k$ and $v_{i}\not\in Z$ or $i>k$ and $w_{i-k}\not\in Z$ . Let $\bar{x}^{\prime}$ and $\bar{y}^{\prime}$ be the tuples of variables obtained analogously from $\bar{x}$ and $\bar{y}$ , respectively.

Using Theorem 2.6, we obtain a Feferman–Vaught decomposition $\Delta_{\varphi^{\prime}_{H,\bar{z},f}}$ of $\varphi^{\prime}_{H,\bar{z},f}(\bar{x}^{\prime},\bar{y}^{\prime})$ w.r.t. $(\bar{x}^{\prime};\bar{y}^{\prime})$ , that is, a set of pairs $\bigl{(}\alpha(\bar{x}^{\prime}),\beta(\bar{y}^{\prime})\bigr{)}$ of $\textup{{FOW}}_{1}(\mathbb{P})[\sigma_{m},\mathbb{S},\mathbf{W}_{m}]$ formulas such that $H_{\bar{z},\varphi^{\prime}}\models\varphi^{\prime}_{H,\bar{z},f}[\bar{v}^{% \prime},\bar{w}^{\prime}]$ if and only if there is a pair $\bigl{(}\alpha(\bar{x}^{\prime}),\beta(\bar{y}^{\prime})\bigr{)}$ in $\Delta_{\varphi^{\prime}_{H,\bar{z},f}}$ such that $H_{V}\models\alpha[\bar{v}^{\prime}]$ and $H_{W}\models\beta[\bar{w}^{\prime}]$ . Since the structure of $\varphi^{\prime}_{H,\bar{z},f}$ is independent of $H$ and $\bar{z}$ , and only the used constants might differ, it is easy to see from the proof of Theorem 2.6 (see [5] for details) that the size of $\Delta_{\varphi^{\prime}_{H,\bar{z},f}}$ only depends on $\varphi$ and $f$ , and that it is independent of $H$ and $\bar{z}$ . Furthermore, the number of mappings $f\colon[k+\ell]\to[0,t]$ only depends on $\varphi$ and $m$ (recall that $t\leqslant m$ ), so we can let $T^{\prime}(\varphi,m)\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},% \mathbf{W}]\times\mathbb{N}\to\mathbb{N}$ be an upper bound on the number of pairs in the decomposition $\Delta_{\varphi^{\prime}_{H,\bar{z},f}}$ for all $H$ , $\bar{z}$ , and $f$ .

All in all, we have $G\models\varphi[\bar{v},\bar{w}]$ if and only if there is a pair $\bigl{(}\alpha(\bar{x}^{\prime}),\beta(\bar{y}^{\prime})\bigr{)}$ in $\Delta_{\varphi^{\prime}_{H,\bar{z},f}}$ such that $H_{V}\models\alpha[\bar{v}^{\prime}]$ and $H_{W}\models\beta[\bar{w}^{\prime}]$ . Hence, for every $\bar{v}\in V^{k}$ , $\textup{tp}^{\varphi}_{G}(\bar{v}/W)$ only depends on

$\blacksquare$

which vertices of $\bar{v}$ are contained in $Z$ and
$\blacksquare$

which formulas $\alpha$ of pairs $(\alpha,\beta)$ in any of the $\Delta_{\varphi^{\prime}_{H,\bar{z},f}}$ are satisfied by $\bar{v}^{\prime}$ , where $\bar{v}^{\prime}$ is obtained from $\bar{v}$ by dropping all entries that are contained in $Z$ , and $f$ ranges over all mappings $f\colon[k+\ell]\to[0,t]$ with, for all $i\in[k]$ , $f(i)=j$ if $v_{i}=z_{j}$ , and $f(i)=0$ if $v_{i}\not\in Z$ .

Since the number of possibilities for both can be bounded in terms of $\varphi$ and $m$ , there is a function $T\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\times% \mathbb{N}\to\mathbb{N}$ such that $\left\lvert S^{\varphi}_{G}(V/W)\right\rvert=\left\lvert\{\textup{tp}^{\varphi% }_{G}(\bar{v}/W):\bar{v}\in V^{k}\}\right\rvert\leqslant T(\varphi,m)$ . This is the statement of Lemma 4.1. $\hfill\blacktriangleleft$

5 VC Density and VC Dimension

In this section, we prove Results (2)–(4) stated in Section 1. Our main result of this section is the following.

Theorem 5.1.

Let $\mathcal{C}$ be a nowhere dense class of $(\sigma,\mathbf{W})$ -graphs, and let $\varphi(\bar{x},\bar{y})$ be a $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula. For every $\varepsilon>0$ , there exists a constant $c\in\mathbb{N}$ such that for every $G\in\mathcal{C}$ and every non-empty $W\subseteq V(G)$ , we have $\left\lvert S^{\varphi}(G/W)\right\rvert\leqslant c\cdot\left\lvert W\right% \rvert^{\left\lvert\bar{x}\right\rvert+\varepsilon}$ .

As discussed in the introduction, this immediately implies the following bound on the VC density of $\textup{{FOWA}}_{1}$ formulas.

Corollary 5.2.

Let $\mathcal{C}$ be a nowhere dense class of $(\sigma,\mathbf{W})$ -graphs, and let $\varphi(\bar{x},\bar{y})$ be a $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula. The VC density of $\varphi(\bar{x},\bar{y})$ on $\mathcal{C}$ is at most $\left\lvert\bar{x}\right\rvert$ .

Moreover, this implies that the VC dimension of $\textup{{FOWA}}_{1}$ formulas on nowhere dense classes is bounded.

Corollary 5.3.

Let $\mathcal{C}$ be a nowhere dense class of $(\sigma,\mathbf{W})$ -graphs, and let $\varphi(\bar{x},\bar{y})$ be a $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula. It holds that $\varphi(\bar{x},\bar{y})$ has bounded VC dimension on $\mathcal{C}$ .

Proof.

As described in the introduction, Corollary 5.2 already implies Corollary 5.3, since the VC dimension is finite if and only if the VC density is finite (see, e. g., [2]). However, since we find it short and instructive, we also give a proof of Corollary 5.3 based on Theorem 5.1.

Let $k\coloneqq\left\lvert\bar{x}\right\rvert$ , $\ell\coloneqq\left\lvert\bar{y}\right\rvert$ , let $\varepsilon>0$ , and let $c\in\mathbb{N}$ be the constant from Theorem 5.1 applied to $\mathcal{C}$ , $\varphi(\bar{x},\bar{y})$ , and $\varepsilon$ . Moreover, let $m_{0}\in\mathbb{N}$ be such that $c\cdot(\ell m)^{k+\varepsilon}<2^{m}$ for all $m\geqslant m_{0}$ .

Let $G\in\mathcal{C}$ and $Y\subseteq\bigl{(}V(G)\bigr{)}^{\ell}$ such that $\left\lvert Y\right\rvert\eqqcolon m\geqslant m_{0}$ . Let $W\subseteq V(G)$ be the set of vertices appearing in any tuple in $Y$ . We have $\left\lvert W\right\rvert\leqslant\ell\cdot\left\lvert Y\right\rvert=\ell m$ . Moreover, we have $\{Y\cap F:F\in S^{\varphi}(G/V(G))\}\subseteq S^{\varphi}(G/W)$ . Hence, by Theorem 5.1, we have $\left\lvert\{Y\cap F:F\in S^{\varphi}(G/V(G))\}\right\rvert\leqslant\left% \lvert S^{\varphi}(G/W)\right\rvert\leqslant c\cdot(\ell m)^{k+\varepsilon}<2^% {m}$ . This shows that $\{Y\cap F:F\in S^{\varphi}(G/V(G))\}\neq 2^{Y}$ , so $Y$ is not shattered by $S^{\varphi}(G/V(G))$ . Thus, the VC dimension of $S^{\varphi}(G/V(G))$ is less than $m_{0}$ . Since $m_{0}$ does not depend on $G$ , this proves that $\varphi(\bar{x},\bar{y})$ has bounded VC dimension on $\mathcal{C}$ . $\hfill\blacktriangleleft$

For the proof of Theorem 5.1, we rely on the following lemma on the neighbourhood complexity in nowhere dense graph classes. Let $G$ be a $(\sigma,\mathbf{W})$ -graph, and let $X\subseteq V(G)$ . For vertices $v\in X$ and $w\in V(G)$ , a path $P$ from $v$ to $w$ in $G$ is called $X$ -avoiding if all vertices on the path except for $v$ are not contained in $X$ . For an $r\in\mathbb{N}$ and $w\in V(G)$ , the $r$ -projection of $w$ on $X$ , denoted by $M_{r}^{G}(w,X)$ , is the set of all vertices $v\in X$ that are connected to $w$ by an $X$ -avoiding path of length at most $r$ .

Lemma 5.4 ([6, Lemmas 21 and 22]).

Let $\mathcal{C}$ be a nowhere dense class of graphs. There is a function $f_{\textup{cl}}\colon\mathbb{N}\times\mathbb{Q}_{>0}\to\mathbb{N}$ and an algorithm¹¹1In [6], the authors even show that this can be computed by a polynomial-time algorithm. However, running-time bounds are not relevant for our purposes. that, given a graph $G\in\mathcal{C}$ , $X\subseteq V(G)$ , $r\in\mathbb{N}$ , and $\delta\in\mathbb{Q}_{>0}$ , computes a set $\textup{cl}_{r,\delta}(X)$ , called the $r$ -closure of $X$ w.r.t. $\delta$ , with the following properties.

1.

$X\subseteq\textup{cl}_{r,\delta}(X)\subseteq V(G)$ ,
2.

$\left\lvert\textup{cl}_{r,\delta}(X)\right\rvert\leqslant f_{\textup{cl}}(r,% \delta)\cdot\left\lvert X\right\rvert^{1+\delta}$ , and
3.

$\left\lvert M_{r}^{G}\bigl{(}u,\textup{cl}_{r,\delta}(X)\bigr{)}\right\rvert% \leqslant f_{\textup{cl}}(r,\delta)\cdot\left\lvert X\right\rvert^{\delta}$ for all $u\in V(G)\setminus\textup{cl}_{r,\delta}(X)$ .

Moreover, for all $X\subseteq V(G)$ , it holds that

4.

$\left\lvert\bigl{\{}M_{r}^{G}(u,X)\ \mathrel{:}\ u\in V(G)\bigr{\}}\right% \rvert\leqslant f_{\textup{cl}}(r,\delta)\cdot\left\lvert X\right\rvert^{1+\delta}$ .

We can now prove Theorem 5.1.

Proof of Theorem 5.1.

The proof is similar to the proof of the analogous result for first-order logic in [14], using Lemma 4.1 instead of the corresponding result for FO.

Let $\mathcal{C}$ be a nowhere dense class of $(\sigma,\mathbf{W})$ -graphs, let $\varphi(\bar{x},\bar{y})$ be a $\textup{{FOWA}}_{1}$ formula, and let $\varepsilon>0$ . Let $k\coloneqq\left\lvert\bar{x}\right\rvert$ , $\ell\coloneqq\left\lvert\bar{y}\right\rvert$ , let $r\colon\textup{{FOWA}}_{1}\to\mathbb{N}$ and $T\colon\textup{{FOWA}}_{1}\times\mathbb{N}\to\mathbb{N}$ be the functions from Lemma 4.1, let $t\colon\mathbb{N}\to\mathbb{N}$ be the function from Definition 2.1, and let $r\coloneqq r(\varphi)$ and $t\coloneqq t(36r)$ . We have that no graph $G\in\mathcal{C}$ contains $K_{t}$ as a depth- $36r$ minor.

By Theorem 2.2, there is a number $s\in\mathbb{N}$ and a polynomial $N\colon\mathbb{N}\to\mathbb{N}$ such that, for every graph $G\in\mathcal{C}$ , every $m\in\mathbb{N}$ , and every set $X\subseteq(V(G))^{k}$ with $\left\lvert X\right\rvert\geqslant N(m)$ , there are sets $S\subseteq V(G)$ and $Y\subseteq X$ with $\left\lvert S\right\rvert\leqslant s$ and $\left\lvert Y\right\rvert\geqslant m$ such that all distinct $\bar{v},\bar{v}^{\prime}\in Y$ are $2r$ -separated by $S$ in $G$ . Let $d$ be the degree of $N$ .

Let $G\in\mathcal{C}$ , and let $W\subseteq V(G)$ be a non-empty set of vertices. We set $\delta\coloneqq\frac{\varepsilon}{4k+4d}$ , and we let $W^{\prime}\coloneqq\textup{cl}_{r,\delta}(W)$ be the $r$ -closure of $W$ w.r.t. $\delta$ , obtained via Lemma 5.4. We shall prove that

\left\lvert S^{\varphi}(G/W^{\prime})\right\rvert\in\mathcal{O}_{\varepsilon,% \varphi}\bigl{(}\left\lvert W^{\prime}\right\rvert^{k+\varepsilon^{\prime}}% \bigr{)}\qquad\text{for }\varepsilon^{\prime}\coloneqq\varepsilon/2>0,

(

\star

)

where $\mathcal{O}_{\varepsilon,\varphi}(\cdot)$ omits factors depending only on $\varepsilon$ and $\varphi$ . Since $W\subseteq W^{\prime}$ , we have $\left\lvert S^{\varphi}(G/W)\right\rvert\leqslant\left\lvert S^{\varphi}(G/W^{% \prime})\right\rvert$ . Moreover, by Lemma 5.4, we have $\left\lvert W^{\prime}\right\rvert=\left\lvert\textup{cl}_{r,\delta}(W)\right% \rvert\leqslant f_{\textup{cl}}(r,\delta)\cdot\left\lvert W\right\rvert^{1+\delta}$ , and we have $(1+\delta)(k+\varepsilon^{\prime})=(1+\delta)(k+\varepsilon/2)\leqslant k+\varepsilon$ by the choice of $\delta$ , so

\left\lvert S^{\varphi}(G/W)\right\rvert\in\mathcal{O}_{\varepsilon,\varphi}% \Bigl{(}\bigl{(}f_{\textup{cl}}(r,\delta)\cdot\left\lvert W\right\rvert^{1+% \delta}\bigr{)}^{k+\varepsilon^{\prime}}\Bigr{)}\subseteq\mathcal{O}_{% \varepsilon,\varphi}\bigl{(}\left\lvert W\right\rvert^{k+\varepsilon}\bigr{)},

which is the statement of Theorem 5.1.

It remains to prove ( $\star$ ‣ 5). Recall that $S^{\varphi}(G/W^{\prime})=\bigl{\{}\textup{tp}^{\varphi}_{G}(\bar{v}/W^{\prime% })\ \mathrel{:}\ \bar{v}\in\bigl{(}V(G)\bigr{)}^{k}\bigr{\}}$ . We partition the tuples $\bar{v}=(v_{1},\dots,v_{k})\in\bigl{(}V(G)\bigr{)}^{k}$ based on their projection $M_{r}^{G}(\bar{v},W^{\prime})\coloneqq\bigcup_{i=1}^{k}M_{r}(v_{i},W^{\prime})$ into sets $V_{1},\dots,V_{p}$ . That is, two tuples $\bar{v},\bar{v}^{\prime}\in\bigl{(}V(G)\bigr{)}^{k}$ are contained in the same set $V_{j}$ for some $j\in[p]$ if and only if $M_{r}^{G}(\bar{v},W^{\prime})=M_{r}^{G}(\bar{v}^{\prime},W^{\prime})$ . By Item 4 of Lemma 5.4, there are at most $f_{\textup{cl}}(r,\delta)\cdot\left\lvert W^{\prime}\right\rvert^{1+\delta}$ different projections of vertices in $V(G)$ on $W^{\prime}$ , so we have $p\in\mathcal{O}_{\varepsilon,\varphi}\bigl{(}\left\lvert W^{\prime}\right% \rvert^{(1+\delta)k}\bigr{)}$ . Hence, to prove ( $\star$ ‣ 5), it suffices to show that

\left\lvert\bigl{\{}\textup{tp}^{\varphi}_{G}(\bar{v}/W^{\prime})\ \mathrel{:}% \ \bar{v}\in V_{j}\bigr{\}}\right\rvert\in\mathcal{O}_{\varepsilon,\varphi}% \bigl{(}\left\lvert W^{\prime}\right\rvert^{\varepsilon^{\prime\prime}}\bigr{)% }\qquad\text{for }\varepsilon^{\prime\prime}\coloneqq\varepsilon^{\prime}-k% \delta>0,

(

\star\star

)

for all $j\in[p]$ , since then $\left\lvert S^{\varphi}(G/W^{\prime})\right\rvert\in\mathcal{O}_{\varepsilon,% \varphi}\bigl{(}\left\lvert W^{\prime}\right\rvert^{(1+\delta)k}\left\lvert W^% {\prime}\right\rvert^{\varepsilon^{\prime}-k\delta}\bigr{)}=\mathcal{O}_{% \varepsilon,\varphi}\bigl{(}\left\lvert W^{\prime}\right\rvert^{k+\varepsilon^% {\prime}}\bigr{)}$ .

Let $j\in[p]$ , and let $X\coloneqq M_{r}^{G}(\bar{v},W^{\prime})$ be the $r$ -projection of $\bar{v}$ on $W^{\prime}$ for any (and, due to the definition of $V_{j}$ , for all) $\bar{v}\in V_{j}$ . By Item 3 of Lemma 5.4, we have $\left\lvert X\right\rvert\leqslant k\cdot f_{\textup{cl}}(r,\delta)\cdot\left% \lvert W\right\rvert^{\delta}\in\mathcal{O}_{\varepsilon,\varphi}\bigl{(}\left% \lvert W\right\rvert^{\delta}\bigr{)}$ .

Let $V^{\prime}_{j}$ be a maximal subset of $V_{j}$ such that all pairwise distinct tuples $\bar{v},\bar{v}^{\prime}$ from $V^{\prime}_{j}$ have different types $\textup{tp}^{\varphi}_{G}(\bar{v}/W^{\prime})\neq\textup{tp}^{\varphi}_{G}(% \bar{v}^{\prime}/W^{\prime})$ . Note that $\left\lvert\bigl{\{}\textup{tp}^{\varphi}_{G}(\bar{v}/W^{\prime})\ \mathrel{:}% \ \bar{v}\in V_{j}\bigr{\}}\right\rvert=\left\lvert V^{\prime}_{j}\right\rvert$ . Now let $m\in\mathbb{N}$ be the maximum number with $\left\lvert V^{\prime}_{j}\right\rvert\geqslant N(m)$ . Then $\left\lvert V^{\prime}_{j}\right\rvert<N(m+1)\in\mathcal{O}_{\varepsilon,% \varphi}(m^{d})$ .

By Theorem 2.2, as described above, there are sets $S\subseteq V(G)$ and $Y\subseteq V^{\prime}_{j}$ with $\left\lvert S\right\rvert\leqslant s$ and $\left\lvert Y\right\rvert\geqslant m$ such that all distinct $\bar{v},\bar{v}^{\prime}\in Y$ are $2r$ -separated by $S$ in $G$ .

We partition $Y$ into two sets $Y_{1}\uplus Y_{2}$ , where $Y_{1}$ contains all tuples that are $r$ -separated by $S$ from $W^{\prime}$ , and $Y_{2}$ contains the remaining tuples. By Lemma 4.1, since all tuples in $Y_{1}$ are $r$ -separated by $S$ from $W^{\prime}$ , and all tuples in $Y_{1}$ have distinct types, we know that $\left\lvert Y_{1}\right\rvert\leqslant T(\varphi,s)\in\mathcal{O}_{\varepsilon% ,\varphi}(1)$ . Moreover, for every tuple $\bar{v}\in Y_{2}$ , there is a vertex $w\in W^{\prime}$ such that $\bar{v}$ and $w$ are not $r$ -separated by $S$ in $G$ . Note that we can choose $w$ to be contained in $X$ . Moreover, since all tuples in $Y_{2}$ are mutually $2r$ -separated by $S$ in $G$ , we know that for two distinct tuples $\bar{v},\bar{v}^{\prime}\in Y_{2}$ , the vertices in $C$ connected to them by paths of length at most $r$ avoiding $S$ must also be distinct. This shows that $\left\lvert Y_{2}\right\rvert\leqslant\left\lvert X\right\rvert$ . Combined, we obtain that $\left\lvert Y\right\rvert\in\mathcal{O}_{\varepsilon,\delta}(\left\lvert X% \right\rvert)$ . Furthermore, since $\left\lvert Y\right\rvert\geqslant m$ , we have

\left\lvert V^{\prime}_{j}\right\rvert\in\mathcal{O}_{\varepsilon,\varphi}(m^{% d})\subseteq\mathcal{O}_{\varepsilon,\varphi}(\left\lvert Y\right\rvert^{d})% \subseteq\mathcal{O}_{\varepsilon,\varphi}(\left\lvert X\right\rvert^{d})% \subseteq\mathcal{O}_{\varepsilon,\varphi}(\left\lvert W^{\prime}\right\rvert^% {d\delta})\subseteq\mathcal{O}_{\varepsilon,\varphi}(\left\lvert W^{\prime}% \right\rvert^{\varepsilon^{\prime\prime}}),

where the last inclusion holds because $\varepsilon^{\prime\prime}=\varepsilon/2-k\delta\leqslant\varepsilon/4% \leqslant d\delta$ by the choice of $\delta$ . This proves ( $\star\star$ ‣ 5), which, as discussed above, implies the statement of Theorem 5.1. $\hfill\blacktriangleleft$

6 Stability

In this section, we provide the following bound on the ladder index of $\textup{{FOC}}_{1}$ formulas and $\textup{{FOWA}}_{1}$ formulas on nowhere dense classes of weighted graphs. Based on this, we prove Result (5) stated in Section 1.

Theorem 6.1.

There are computable functions $f\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\times% \mathbb{N}\to\mathbb{N}$ and $g\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\to\mathbb% {N}$ such that, for every $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula $\varphi$ , for every $t\in\mathbb{N}$ , and for every $(\sigma,\mathbf{W})$ -graph $G$ excluding $K_{t}$ as a depth- $g(\varphi)$ minor, the ladder index of $\varphi$ in $G$ is at most $f(\varphi,t)$ .

Proof.

The proof is similar to the proof of the analogous statement in [14] for first-order formulas. Let $r\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\to\mathbb% {N}$ and $T\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\times% \mathbb{N}\to\mathbb{N}$ be the functions from Lemma 4.1. We set $g\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\to\mathbb% {N},\varphi\mapsto 18r(\varphi)$ .

Let $\varphi(\bar{x},\bar{y})$ be a $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ formula, let $t\in\mathbb{N}$ , and let $\mathcal{C}$ be the class of $(\sigma,\mathbf{W})$ -graphs excluding $K_{t}$ as a depth- $g(\varphi)$ minor. Let $d\coloneqq\left\lvert\bar{x}\right\rvert+\left\lvert\bar{y}\right\rvert$ , and let $s\in\mathbb{N}$ be the number and $N\colon\mathbb{N}\to\mathbb{N}$ be the polynomial computed from $r(\varphi)$ , $t$ , and $d$ using Theorem 2.2. Moreover, let $L\coloneqq f(\varphi,t)\coloneqq N\bigl{(}2T(\varphi,s)+1\bigr{)}$ . (Note that $N$ and $s$ can be computed from $\varphi$ and $t$ .) We show that every $\varphi$ -ladder in every graph $G\in\mathcal{C}$ has length less than $L$ .

Towards a contradiction, suppose there are a graph $G\in\mathcal{C}$ and tuples $\bar{v}_{1},\dots,\bar{v}_{L}\in\bigl{(}V(G)\bigr{)}^{\left\lvert x\right\rvert}$ and $\bar{w}_{1},\dots,\bar{w}_{L}\in\bigl{(}V(G)\bigr{)}^{\left\lvert y\right\rvert}$ that form a $\varphi$ -ladder in $G$ , that is, $G\models\varphi[\bar{v}_{i},\bar{w}_{j}]$ if and only if $i\leqslant j$ . In particular, the tuples $\bar{v}_{1},\dots,\bar{v}_{L}$ are pairwise distinct, and the same holds for the tuples $\bar{w}_{1},\dots,\bar{w}_{L}$ . Let $X\coloneqq\{\bar{v}_{i}\bar{w}_{i}:i\in[L]\}\subseteq\bigl{(}V(G)\bigr{)}^{d}$ . By Theorem 2.2, for $m\coloneqq 2T(\varphi,s)+1$ , since $\left\lvert X\right\rvert\geqslant N(m)$ , there are sets $S\subseteq V(G)$ and $Y\subseteq X$ with $\left\lvert S\right\rvert\leqslant s$ and $\left\lvert Y\right\rvert\geqslant m$ such that all distinct $\bar{u},\bar{u}^{\prime}\in Y$ are $r(\varphi)$ -separated by $S$ in $G$ . Let $I\coloneqq\{i\in[\ell]:\bar{v}_{i}\bar{w}_{i}\in Y\}$ . Let $I_{1},I_{2}$ be an alternating partition of $I$ , that is, for all successive $i,j\in I_{1}$ , there is exactly one $k\in I_{2}$ with $i<k<j$ . Note that $\left\lvert I_{1}\right\rvert\geqslant T(\varphi,s)+1$ . Let $V\subseteq V(G)$ be the set of vertices appearing in a tuple $\bar{v}_{i}\bar{w}_{i}$ with $i\in I_{1}$ , and let $W\subseteq V(G)$ be the set of vertices appearing in a tuple $\bar{v}_{i}\bar{w}_{i}$ with $i\in I_{2}$ . Since all distinct $\bar{u},\bar{u}^{\prime}\in Y$ are $r(\varphi)$ -separated by $S$ in $G$ , it also holds that the sets $V$ and $W$ are $r(\varphi)$ -separated by $S$ in $G$ .

Now we can apply Lemma 4.1 to $V$ and $W$ , and we obtain $\left\lvert S^{\varphi}_{G}(V/W)\right\rvert\leqslant T(\varphi,s)<\left\lvert I% _{1}\right\rvert$ . Hence, there are two indices $i,j\in I_{1}$ with $i<j$ such that $\textup{tp}^{\varphi}_{G}(\bar{v}_{i}/W)=\textup{tp}^{\varphi}_{G}(\bar{v}_{j}% /W)$ . Let $k\in I_{2}$ with $i<k<j$ . Then $\bar{w}_{k}\in\textup{tp}^{\varphi}_{G}(\bar{v}_{i}/W)$ if and only if $\bar{w}_{k}\in\textup{tp}^{\varphi}_{G}(\bar{v}_{j}/W)$ , so $G\models\varphi[\bar{v}_{i},\bar{w}_{k}]$ if and only if $G\models\varphi[\bar{v}_{j},\bar{w}_{k}]$ . However, this contradicts $\bar{v}_{1},\dots,\bar{v}_{\ell}$ and $\bar{w}_{1},\dots,\bar{w}_{\ell}$ being a $\varphi$ -ladder, because we need to have $G\models\varphi[\bar{v}_{i},\bar{w}_{k}]$ (since $i<k$ ) and $G\not\models\varphi[\bar{v}_{j},\bar{w}_{k}]$ (since $j>k$ ). This shows that there is no $\varphi$ -ladder in $G$ of size at least $L=f(\varphi,t)$ , so the ladder index of $\varphi$ in $G$ is at most $f(\varphi,t)$ . $\hfill\blacktriangleleft$

We call a class $\mathcal{C}$ of weighted graphs $\textup{{FOWA}}_{1}$ -stable ( $\textup{{FOC}}_{1}$ -stable) if the ladder index of every $\textup{{FOWA}}_{1}$ ( $\textup{{FOC}}_{1}$ ) formula $\varphi$ in every weighted graph from $\mathcal{C}$ is bounded by a constant depending only on $\varphi$ and $\mathcal{C}$ .

Corollary 6.2.

Every nowhere dense class of weighted graphs is $\textup{{FOC}}_{1}$ -stable and $\textup{{FOWA}}_{1}$ -stable.

Proof.

Let $\mathcal{C}$ be a nowhere dense class of $(\sigma,\mathbf{W})$ -graphs, let $\varphi(\bar{x},\bar{y})$ be a formula in $\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]$ , and let $k\coloneqq\left\lvert\bar{x}\right\rvert$ and $\ell\coloneqq\left\lvert\bar{y}\right\rvert$ . By Definition 2.1, there is a function $t\colon\mathbb{N}\to\mathbb{N}$ such that for all $r\in\mathbb{N}$ and $G\in\mathcal{C}$ , it holds that $G$ does not contain $K_{t(r)}$ as a depth- $r$ minor.

Let $f\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\times% \mathbb{N}\to\mathbb{N}$ and $g\colon\textup{{FOWA}}_{1}(\mathbb{P})[\sigma,\mathbb{S},\mathbf{W}]\to\mathbb% {N}$ be the functions from Theorem 6.1. For all $G\in\mathcal{C}$ , we have that $G$ does not contain $K_{t(g(\varphi))}$ as a depth- $g(\varphi)$ minor. Thus, by Theorem 6.1, for every $G\in\mathcal{C}$ , the ladder index of $\varphi$ in $G$ is at most $L\coloneqq f\bigl{(}\varphi,t(g(\varphi))\bigr{)}$ , which only depends on $\varphi$ and $\mathcal{C}$ . $\hfill\blacktriangleleft$

7 Final Remarks

In this paper, we have presented upper bounds on the VC dimension and the ladder index as well as optimal bounds on the VC density of formulas in the first-order logic with counting $\textup{{FOC}}_{1}$ and the first-order logic with weight aggregation $\textup{{FOWA}}_{1}$ on nowhere dense classes of vertex- and edge-weighted graphs. This lifts results of Adler and Adler [1] and results of Pilipczuk, Siebertz, and Toruńczyk [14] from first-order logic to substantially more expressive logics.

In [4], van Bergerem, Grohe, and Ritzert combined the result by Adler and Adler with the fixed-parameter tractable (fpt) model-checking result for FO on nowhere dense graph classes [7] to prove learnability results for FO on nowhere dense graph classes in the Probably Approximately Correct (PAC) learning framework. We remark that, by combining our results on the VC dimension for $\textup{{FOC}}_{1}$ formulas with the fpt model-checking result for $\textup{{FOC}}_{1}$ by Grohe and Schweikardt [8], we also obtain fpt PAC learnability for $\textup{{FOC}}_{1}$ -definable concepts over nowhere dense graph classes. We are currently working on lifting these model-checking and learnability results from $\textup{{FOC}}_{1}$ to $\textup{{FOWA}}_{1}$ .

References

[1] Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. Eur. J. Comb., 36:322–330, 2014. doi:10.1016/j.ejc.2013.06.048.
[2] Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, and Sergei Starchenko. Vapnik–Chervonenkis density in some theories without the independence property, I. Transactions of the American Mathematical Society, 368(8):5889–5949, August 2016. doi:10.1090/tran/6659.
[3] Steffen van Bergerem. Learning concepts definable in first-order logic with counting. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24–27, 2019, pages 1–13. IEEE, 2019. doi:10.1109/LICS.2019.8785811.
[4] Steffen van Bergerem, Martin Grohe, and Martin Ritzert. On the parameterized complexity of learning first-order logic. In PODS 2022: International Conference on Management of Data, Philadelphia, PA, USA, June 12–17, 2022, pages 337–346. ACM, 2022. doi:10.1145/3517804.3524151.
[5] Steffen van Bergerem and Nicole Schweikardt. Learning concepts described by weight aggregation logic. In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, Ljubljana, Slovenia (Virtual Conference), January 25–28, 2021, volume 183 of LIPIcs, pages 10:1–10:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CSL.2021.10.
[6] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10–14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 63:1–63:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPICS.ICALP.2017.63.
[7] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1–17:32, 2017. doi:10.1145/3051095.
[8] Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2018, Houston, TX, USA, June 10–15, 2018, pages 253–266. ACM, 2018. doi:10.1145/3196959.3196970.
[9] Martin Grohe and György Turán. Learnability and definability in trees and similar structures. Theory Comput. Syst., 37(1):193–220, 2004. doi:10.1007/s00224-003-1112-8.
[10] Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavík, Iceland, June 20–23, 2017, pages 1–12. IEEE Computer Society, 2017. doi:10.1109/LICS.2017.8005133.
[11] Jaroslav Nešetřil and Patrice Ossona de Mendez. First order properties on nowhere dense structures. J. Symb. Log., 75(3):868–887, 2010. doi:10.2178/jsl/1278682204.
[12] Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb., 32(4):600–617, 2011. doi:10.1016/j.ejc.2011.01.006.
[13] Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity – Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.
[14] Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. On the number of types in sparse graphs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09–12, 2018, pages 799–808. ACM, 2018. doi:10.1145/3209108.3209178.
[15] Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fundamenta Mathematicae, 100(2):101–107, 1978. URL: http://eudml.org/doc/210953.
[16] Norbert Sauer. On the density of families of sets. J. Comb. Theory A, 13(1):145–147, 1972. doi:10.1016/0097-3165(72)90019-2.
[17] Saharon Shelah. A combinatorial problem: stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247–261, 1972. doi:10.2140/pjm.1972.41.247.
[18] Katrin Tent and Martin Ziegler. A Course in Model Theory. Lecture Notes in Logic. Cambridge University Press, 2012. doi:10.1017/CBO9781139015417.
[19] Vladimir Naumovich Vapnik and Alexey Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264–280, 1971. doi:10.1137/1116025.

[bib.bib1] [1] Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. Eur. J. Comb., 36:322–330, 2014. doi:10.1016/j.ejc.2013.06.048.

[bib.bib2] [2] Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, and Sergei Starchenko. Vapnik–Chervonenkis density in some theories without the independence property, I. Transactions of the American Mathematical Society, 368(8):5889–5949, August 2016. doi:10.1090/tran/6659.

[bib.bib3] [3] Steffen van Bergerem. Learning concepts definable in first-order logic with counting. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24–27, 2019, pages 1–13. IEEE, 2019. doi:10.1109/LICS.2019.8785811.

[bib.bib4] [4] Steffen van Bergerem, Martin Grohe, and Martin Ritzert. On the parameterized complexity of learning first-order logic. In PODS 2022: International Conference on Management of Data, Philadelphia, PA, USA, June 12–17, 2022, pages 337–346. ACM, 2022. doi:10.1145/3517804.3524151.

[bib.bib5] [5] Steffen van Bergerem and Nicole Schweikardt. Learning concepts described by weight aggregation logic. In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, Ljubljana, Slovenia (Virtual Conference), January 25–28, 2021, volume 183 of LIPIcs, pages 10:1–10:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CSL.2021.10.

[bib.bib6] [6] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10–14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 63:1–63:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPICS.ICALP.2017.63.

[bib.bib7] [7] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1–17:32, 2017. doi:10.1145/3051095.

[bib.bib8] [8] Martin Grohe and Nicole Schweikardt. First-order query evaluation with cardinality conditions. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2018, Houston, TX, USA, June 10–15, 2018, pages 253–266. ACM, 2018. doi:10.1145/3196959.3196970.

[bib.bib9] [9] Martin Grohe and György Turán. Learnability and definability in trees and similar structures. Theory Comput. Syst., 37(1):193–220, 2004. doi:10.1007/s00224-003-1112-8.

[bib.bib10] [10] Dietrich Kuske and Nicole Schweikardt. First-order logic with counting. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavík, Iceland, June 20–23, 2017, pages 1–12. IEEE Computer Society, 2017. doi:10.1109/LICS.2017.8005133.

[bib.bib11] [11] Jaroslav Nešetřil and Patrice Ossona de Mendez. First order properties on nowhere dense structures. J. Symb. Log., 75(3):868–887, 2010. doi:10.2178/jsl/1278682204.

[bib.bib12] [12] Jaroslav Nešetřil and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb., 32(4):600–617, 2011. doi:10.1016/j.ejc.2011.01.006.

[bib.bib13] [13] Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity – Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. doi:10.1007/978-3-642-27875-4.

[bib.bib14] [14] Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. On the number of types in sparse graphs. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09–12, 2018, pages 799–808. ACM, 2018. doi:10.1145/3209108.3209178.

[bib.bib15] [15] Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fundamenta Mathematicae, 100(2):101–107, 1978. URL: http://eudml.org/doc/210953.

[bib.bib16] [16] Norbert Sauer. On the density of families of sets. J. Comb. Theory A, 13(1):145–147, 1972. doi:10.1016/0097-3165(72)90019-2.

[bib.bib17] [17] Saharon Shelah. A combinatorial problem: stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247–261, 1972. doi:10.2140/pjm.1972.41.247.

[bib.bib18] [18] Katrin Tent and Martin Ziegler. A Course in Model Theory. Lecture Notes in Logic. Cambridge University Press, 2012. doi:10.1017/CBO9781139015417.

[bib.bib19] [19] Vladimir Naumovich Vapnik and Alexey Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264–280, 1971. doi:10.1137/1116025.

On the VC Dimension of First-Order Logic with Counting and Weight Aggregation

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Preliminaries

𝝈-Graphs

Weighted 𝝈-Graphs

Nowhere Dense Classes

Definition 2.1.

Theorem 2.2 (Uniform quasi-wideness for tuples [14, Theorem 2.9]).

The Weight Aggregation Logic FOWA

Definition 2.3.

Definition 2.4.

Example 2.5.

Locality Results

Theorem 2.6 (Feferman–Vaught decompositions for FOW1 [5, Theorem 4.3]).

Theorem 2.7 (Localisation Theorem for FOWA1 [5, Theorem 4.7]).

3 FOC𝟐 has Unbounded VC Dimension

Theorem 3.1.

Proof.

4 Bound on the Number of Types

Lemma 4.1.

Proof.

Claim 4.2.

Proof.

5 VC Density and VC Dimension

Theorem 5.1.

Corollary 5.2.

Corollary 5.3.

Proof.

Lemma 5.4 ([6, Lemmas 21 and 22]).

Proof of Theorem 5.1.

6 Stability

Theorem 6.1.

Proof.

Corollary 6.2.

Proof.

7 Final Remarks

References

On the VC Dimension of First-Order Logic
with Counting and Weight Aggregation

$\sigma$ -Graphs

Weighted $\sigma$ -Graphs

Theorem 2.6 (Feferman–Vaught decompositions for $\textup{{FOW}}_{1}$ [5, Theorem 4.3]).

Theorem 2.7 (Localisation Theorem for $\textup{{FOWA}}_{1}$ [5, Theorem 4.7]).

3 $\textup{{FOC}}_{2}$ has Unbounded VC Dimension