Remote Access Transactions of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0002-9947-07-04382-6
Published electronically: August 14, 2007
MathSciNet review: 2342010
Full-text PDF

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?)

  • 1. M.H. Albert, `Measures on the random graph', J. London Math. Soc. (2) 50 (1994), 417-429. MR 1299447 (95j:05155)
  • 2. T. Blossier, Ensembles minimaux localement modulaires, Ph.D. thesis, Université Paris VII, 2001.
  • 3. B. Bollobás, A. Thomason, `Graphs which contain all small graphs', Europ. J. Comb. 2 (1981), 13-15. MR 611926 (82d:05071)
  • 4. B. Bollobás, Random Graphs, Academic Press, New York, 1985. MR 809996 (87f:05152)
  • 5. S. Buechler, `Lascar strong types in some simple theories', J. Symb. Logic 64 (1999), 817-824. MR 1777789 (2001k:03071)
  • 6. Z. Chatzidakis, L. van den Dries, A.J. Macintyre, `Definable sets over finite fields', J. Reine Angew. Math. 427 (1992), 107-135. MR 1162433 (94c:03049)
  • 7. Z. Chatzidakis, A. Pillay, `Generic structures and simple theories', Ann. Pure Appl. Logic 95 (1998), 71-92. MR 1650667 (2000c:03028)
  • 8. G. Cherlin, L. Harrington, A.H. Lachlan, `$ \aleph_0$-categorical, $ \aleph_0$-stable structures', Ann. Pure Appl. Logic 28 (1985), 103-135. MR 779159 (86g:03054)
  • 9. G. Cherlin, E. Hrushovski, Finite structures with few types, Annals of Mathematics Studies No. 152, Princeton University Press, Princeton, 2003. MR 1961194 (2004c:03037)
  • 10. A. Chowdhury, B. Hart, Z. Sokolovic, `Affine covers of Lie geometries and the amalgamation property', Proc. London Math. Soc. (3) 85 (2002), 513-563. MR 1936812 (2003j:03041)
  • 11. K. Doerk, T, Hawkes, Finite soluble groups, de Gruyter, Berlin, 1992. MR 1169099 (93k:20033)
  • 12. L. van den Dries, `Algebraic theories with definable Skolem functions', J. Symb. Logic 49 (1984), 625-629. MR 745390 (85e:03076)
  • 13. R. Elwes, `Asymptotic classes of finite structures', J. Symb. Logic, to appear.
  • 14. R. Elwes, H.D. Macpherson, `Measurable structures and asymptotic classes of finite structures', in preparation.
  • 15. U. Felgner, `On $ \aleph_0$-categorical extra-special $ p$-groups', Logique et Anal. (N.S.) 18 (1975), 407-428. MR 0476493 (57:16054)
  • 16. C. Godsil, G. Royle, Algebraic graph theory, Springer, Berlin, 2001. MR 1829620 (2002f:05002)
  • 17. R. L. Graham, J. H. Spencer, `A constructive solution to a tournament problem', Canad. Math. Bull. 14 (1971), 45-48. MR 0292715 (45:1798)
  • 18. D. Haskell, A. Pillay, and C. Steinhorn (Eds.), Model Theory, Algebra, and Geometry, Mathematical Sciences Research Institute Publications, v. 39, Cambridge University Press, Cambridge, 2000. MR 1773699 (2001d:03004)
  • 19. W. Hodges, Model Theory, Cambridge University Press, Cambridge, 1993. MR 1221741 (94e:03002)
  • 20. E. Hrushovski, `Unimodular minimal structures', J. London Math. Soc. (2) 46 (1992), 385-396. MR 1190425 (94b:03062)
  • 21. E. Hrushovski, Y. Peterzil, A. Pillay, `Groups, measures, and the NIP', J. Amer. Math. Soc., to appear.
  • 22. E. Hrushovski, A. Pillay, `Definable subgroups of algebraic groups over finite fields', J. Reine Angew. Math. 462 (1995), 69-91. MR 1329903 (97f:20059)
  • 23. E. Hrushovski, `Pseudofinite fields and related structures', in Model theory and applications (Eds. L. Bélair, Z. Chatzidakis, P. D'Aquino, D.Marker, M. Otero, F. Point, A. Wilkie), Quaderni di Matematica, vol. 11, Caserta, 2005, 151-212. MR 2159717 (2006d:03059)
  • 24. W.M. Kantor, M.W. Liebeck, H.D. Macpherson, `$ \aleph_0$-categorical structures smoothly approximated by finite substructures', Proc. London Math. Soc. (3) 59 (1989), 439-463. MR 1014866 (91e:03033)
  • 25. B. Kim, A. Pillay, `Simple theories', Ann. Pure Appl. Logic 88 (1997), 149-164. MR 1600895 (99b:03049)
  • 26. J. Krajícek and T. Scanlon, `Combinatorics with definable sets: Grothendieck rings and Euler characteristics', Bull. Symb. Logic 6 (2000), 311-330. MR 1803636 (2001k:03063)
  • 27. S. Lang, Algebra, Addison-Wesley, Menlo Park, 1984. MR 0197234 (33:5416)
  • 28. I.D. Macdonald, `Some explicit bounds in groups with finite derived subgroups', Proc. London Math. Soc. (3) 11 (1961), 23-56. MR 0124433 (23:A1745)
  • 29. B.H. Neumann, `Groups covered by permutable subsets', J. London Math. Soc. 29 (1954), 236-248. MR 0062122 (15:931b)
  • 30. A. Pillay, B. Poizat, `Corps et Chirurgie', J. Symb. Logic 60 (1995), 528-533. MR 1335134 (96e:12005)
  • 31. A. Pillay, T. Scanlon, F.O. Wagner, `Supersimple fields and division rings', Math. Research Letters 5 (1998), 473-483. MR 1653312 (2000b:03124)
  • 32. H.N. Shapiro, Introduction to the theory of numbers, Wiley, New York, 1983. MR 693458 (84f:10001)
  • 33. W. Szmielew, `Elementary properties of abelian groups', Fund. Math. 41 (1955), 203-271. MR 0072131 (17:233e)
  • 34. A. Thomason, `Random graphs, strongly regular graphs, and pseudo-random graphs', in Surveys in Combinatorics 1987 (ed. C. Whitehead), London Math. Soc. Lecture Notes 123, Cambridge University Press, Cambridge, 1987, 173-195. MR 905280 (88m:05072)
  • 35. F.O. Wagner, Simple theories, Kluwer, Dordrecht, 2000. MR 1747713 (2001b:03035)
  • 36. J. Wiegold, `Groups with boundedly finite classes of conjugate elements', Proc. Royal Soc. A 238 (1956), 389-401. MR 0083488 (18:716a)

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: https://doi.org/10.1090/S0002-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

American Mathematical Society