One-dimensional asymptotic classes of finite structures
HTML articles powered by AMS MathViewer
- by Dugald Macpherson and Charles Steinhorn PDF
- Trans. Amer. Math. Soc. 360 (2008), 411-448 Request permission
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.
References
- Michael H. Albert, Measures on the random graph, J. London Math. Soc. (2) 50 (1994), no. 3, 417–429. MR 1299447, DOI 10.1112/jlms/50.3.417
- T. Blossier, Ensembles minimaux localement modulaires, Ph.D. thesis, Université Paris VII, 2001.
- Béla Bollobás and Andrew Thomason, Graphs which contain all small graphs, European J. Combin. 2 (1981), no. 1, 13–15. MR 611926, DOI 10.1016/S0195-6698(81)80015-7
- Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
- Steven Buechler, Lascar strong types in some simple theories, J. Symbolic Logic 64 (1999), no. 2, 817–824. MR 1777789, DOI 10.2307/2586503
- Zoé Chatzidakis, Lou van den Dries, and Angus Macintyre, Definable sets over finite fields, J. Reine Angew. Math. 427 (1992), 107–135. MR 1162433
- Z. Chatzidakis and A. Pillay, Generic structures and simple theories, Ann. Pure Appl. Logic 95 (1998), no. 1-3, 71–92. MR 1650667, DOI 10.1016/S0168-0072(98)00021-9
- G. Cherlin, L. Harrington, and A. H. Lachlan, $\aleph _0$-categorical, $\aleph _0$-stable structures, Ann. Pure Appl. Logic 28 (1985), no. 2, 103–135. MR 779159, DOI 10.1016/0168-0072(85)90023-5
- Gregory Cherlin and Ehud Hrushovski, Finite structures with few types, Annals of Mathematics Studies, vol. 152, Princeton University Press, Princeton, NJ, 2003. MR 1961194
- Ambar Chowdhury, Bradd Hart, and Željko Sokolović, Affine covers of Lie geometries and the amalgamation property, Proc. London Math. Soc. (3) 85 (2002), no. 3, 513–563. MR 1936812, DOI 10.1112/S0024611502013783
- Klaus Doerk and Trevor Hawkes, Finite soluble groups, De Gruyter Expositions in Mathematics, vol. 4, Walter de Gruyter & Co., Berlin, 1992. MR 1169099, DOI 10.1515/9783110870138
- Lou van den Dries, Algebraic theories with definable Skolem functions, J. Symbolic Logic 49 (1984), no. 2, 625–629. MR 745390, DOI 10.2307/2274194
- R. Elwes, ‘Asymptotic classes of finite structures’, J. Symb. Logic, to appear.
- R. Elwes, H.D. Macpherson, ‘Measurable structures and asymptotic classes of finite structures’, in preparation.
- Ulrich Felgner, On $\aleph _{0}$-categorical extra-special $p$-groups, Logique et Anal. (N.S.) 18 (1975), no. 71-72, 407–428. MR 476493
- Chris Godsil and Gordon Royle, Algebraic graph theory, Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR 1829620, DOI 10.1007/978-1-4613-0163-9
- R. L. Graham and J. H. Spencer, A constructive solution to a tournament problem, Canad. Math. Bull. 14 (1971), 45–48. MR 292715, DOI 10.4153/CMB-1971-007-1
- Deirdre Haskell, Anand Pillay, and Charles Steinhorn (eds.), Model theory, algebra, and geometry, Mathematical Sciences Research Institute Publications, vol. 39, Cambridge University Press, Cambridge, 2000. MR 1773699, DOI 10.2977/prims/1145476103
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- Ehud Hrushovski, Unimodular minimal structures, J. London Math. Soc. (2) 46 (1992), no. 3, 385–396. MR 1190425, DOI 10.1112/jlms/s2-46.3.385
- E. Hrushovski, Y. Peterzil, A. Pillay, ‘Groups, measures, and the NIP’, J. Amer. Math. Soc., to appear.
- E. Hrushovski and A. Pillay, Definable subgroups of algebraic groups over finite fields, J. Reine Angew. Math. 462 (1995), 69–91. MR 1329903
- Ehud Hrushovski, Pseudo-finite fields and related structures, Model theory and applications, Quad. Mat., vol. 11, Aracne, Rome, 2002, pp. 151–212. MR 2159717
- W. M. Kantor, Martin W. Liebeck, and H. D. Macpherson, $\aleph _0$-categorical structures smoothly approximated by finite substructures, Proc. London Math. Soc. (3) 59 (1989), no. 3, 439–463. MR 1014866, DOI 10.1112/plms/s3-59.3.439
- Byunghan Kim and Anand Pillay, Simple theories, Ann. Pure Appl. Logic 88 (1997), no. 2-3, 149–164. Joint AILA-KGS Model Theory Meeting (Florence, 1995). MR 1600895, DOI 10.1016/S0168-0072(97)00019-5
- Jan Krajíček and Thomas Scanlon, Combinatorics with definable sets: Euler characteristics and Grothendieck rings, Bull. Symbolic Logic 6 (2000), no. 3, 311–330. MR 1803636, DOI 10.2307/421058
- Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
- I. D. Macdonald, Some explicit bounds in groups with finite derived groups, Proc. London Math. Soc. (3) 11 (1961), 23–56. MR 124433, DOI 10.1112/plms/s3-11.1.23
- B. H. Neumann, Groups covered by permutable subsets, J. London Math. Soc. 29 (1954), 236–248. MR 62122, DOI 10.1112/jlms/s1-29.2.236
- Anand Pillay and Bruno Poizat, Corps et chirurgie, J. Symbolic Logic 60 (1995), no. 2, 528–533 (French, with French and Esperanto summaries). MR 1335134, DOI 10.2307/2275848
- A. Pillay, T. Scanlon, and F. O. Wagner, Supersimple fields and division rings, Math. Res. Lett. 5 (1998), no. 4, 473–483. MR 1653312, DOI 10.4310/MRL.1998.v5.n4.a5
- Harold N. Shapiro, Introduction to the theory of numbers, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1983. MR 693458
- W. Szmielew, Elementary properties of Abelian groups, Fund. Math. 41 (1955), 203–271. MR 72131, DOI 10.4064/fm-41-2-203-271
- Andrew Thomason, Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 173–195. MR 905280
- Frank O. Wagner, Simple theories, Mathematics and its Applications, vol. 503, Kluwer Academic Publishers, Dordrecht, 2000. MR 1747713, DOI 10.1007/978-94-017-3002-0
- J. Wiegold, Groups with boundedly finite classes of conjugate elements, Proc. Roy. Soc. London Ser. A 238 (1957), 389–401. MR 83488, DOI 10.1098/rspa.1957.0007
Additional Information
- Dugald Macpherson
- Affiliation: Department of Pure Mathematics, University of Leeds, Leeds LS2 9JT, England
- MR Author ID: 224239
- 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
- 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.
- © Copyright 2007 American Mathematical Society
- 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
- MathSciNet review: 2342010