One-dimensional asymptotic classes of finite structures

Abstract:

A collection ${\mathcal C}$ of finite $\mathcal {L}$-structures is a 1-dimensional asymptotic class if for every $m \in {\mathbb N}$ and every formula $\varphi (x,\bar {y})$, where $\bar {y}=(y_1,\ldots ,y_m)$:

[(i)] There is a positive constant $C$ and a finite set $E\subset {\mathbb R}^{>0}$ such that for every $M\in {\mathcal C}$ and $\bar {a}\in M^m$, either $|\varphi (M,\bar {a})|\leq C$, or for some $\mu \in E$, \[ \big ||\varphi (M,\bar {a})|-\mu |M|\big | \leq C|M|^{\frac {1}{2}}.\]

[(ii)] For every $\mu \in E$, there is an $\mathcal {L}$-formula $\varphi _{\mu }(\bar {y})$, such that $\varphi _{\mu }(M^m)$ is precisely the set of $\bar {a}\in M^m$ with \[ \big ||\varphi (M,\bar {a})|-\mu |M|\big | \leq C|M|^{\frac {1}{2}}.\]

One-dimensional asymptotic classes are introduced and studied here. These classes come equipped with a notion of dimension that is intended to provide for the study of classes of finite structures a concept that is central in the development of model theory for infinite structures. Connections with the model theory of infinite structures are also drawn.