Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

One-dimensional asymptotic classes of finite structures


Authors: Dugald Macpherson and Charles Steinhorn
Journal: Trans. Amer. Math. Soc. 360 (2008), 411-448
MSC (2000): Primary 03C45; Secondary 03C13
Published electronically: August 14, 2007
MathSciNet review: 2342010
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 $ \vert\varphi(M,\bar{a})\vert\leq C$, or for some $ \mu\in E$,

$\displaystyle \big\vert\vert\varphi(M,\bar{a})\vert-\mu \vert M\vert\big\vert \leq C\vert M\vert^{\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

$\displaystyle \big\vert\vert\varphi(M,\bar{a})\vert-\mu \vert M\vert\big\vert \leq C\vert M\vert^{\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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03C45, 03C13

Retrieve articles in all journals with MSC (2000): 03C45, 03C13


Additional Information

Dugald Macpherson
Affiliation: Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, England
Email: pmthdm@maths.leeds.ac.uk

Charles Steinhorn
Affiliation: Department of Mathematics, Vassar College, 124 Raymond Avenue, Poughkeepsie, New York 12604
Email: steinhorn@vassar.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-07-04382-6
PII: S 0002-9947(07)04382-6
Received by editor(s): February 24, 2006
Published electronically: August 14, 2007
Additional Notes: This work was partially supported by NSF grants DMS-9704869 and DMS-0070743, EPSRC grant GR/R37388/01, and the London Mathematical Society.
Article copyright: © Copyright 2007 American Mathematical Society