Binary simple homogeneous structures are supersimple with finite rank
HTML articles powered by AMS MathViewer
- by Vera Koponen PDF
- Proc. Amer. Math. Soc. 144 (2016), 1745-1759 Request permission
Abstract:
Suppose that $\mathcal {M}$ is an infinite structure with finite relational vocabulary such that every relation symbol has arity at most 2. If $\mathcal {M}$ is simple and homogeneous, then its complete theory is supersimple with finite SU-rank which cannot exceed the number of complete 2-types over the empty set.References
- A. Aranda López, Omega-categorical simple theories, Ph.D. thesis, The University of Leeds (2014).
- Ove Ahlman and Vera Koponen, On sets with rank one in simple homogeneous structures, Fund. Math. 228 (2015), no. 3, 223–250. MR 3294610, DOI 10.4064/fm228-3-2
- M. Bodirsky, M. Pinsker, Reducts of Ramsey structures, in M. Grohe, J. A. Makowsky (eds.), Model Theoretic Methods in Finite Combinatorics, Contemporary Mathematics 558, Americal Mathematical Society (2011).
- Enrique Casanovas, Simple theories and hyperimaginaries, Lecture Notes in Logic, vol. 39, Association for Symbolic Logic, Chicago, IL; Cambridge University Press, Cambridge, 2011. MR 2814891, DOI 10.1017/CBO9781139003728
- Gregory L. Cherlin, The classification of countable homogeneous directed graphs and countable homogeneous $n$-tournaments, Mem. Amer. Math. Soc. 131 (1998), no. 621, xiv+161. MR 1434988, DOI 10.1090/memo/0621
- Gregory Cherlin and Ehud Hrushovski, Finite structures with few types, Annals of Mathematics Studies, vol. 152, Princeton University Press, Princeton, NJ, 2003. MR 1961194
- G. Cherlin and A. H. Lachlan, Stable finitely homogeneous structures, Trans. Amer. Math. Soc. 296 (1986), no. 2, 815–850. MR 846608, DOI 10.1090/S0002-9947-1986-0846608-8
- Marko Djordjević, The finite submodel property and $\omega$-categorical expansions of pregeometries, Ann. Pure Appl. Logic 139 (2006), no. 1-3, 201–229. MR 2206256, DOI 10.1016/j.apal.2005.05.013
- Tristram de Piro and Byunghan Kim, The geometry of 1-based minimal types, Trans. Amer. Math. Soc. 355 (2003), no. 10, 4241–4263. MR 1990585, DOI 10.1090/S0002-9947-03-03327-0
- Roland Fraïssé, Sur l’extension aux relations de quelques propriétés des ordres, Ann. Sci. Ecole Norm. Sup. (3) 71 (1954), 363–388 (French). MR 0069239
- A. Gardiner, Homogeneous graphs, J. Combinatorial Theory Ser. B 20 (1976), no. 1, 94–102. MR 419293, DOI 10.1016/0095-8956(76)90072-1
- Ja. Ju. Gol′fand and M. H. Klin, On $k$-homogeneous graphs, Algorithmic studies in combinatorics (Russian), “Nauka”, Moscow, 1978, pp. 76–85, 186 (errata insert) (Russian). MR 509886
- Bradd Hart, Byunghan Kim, and Anand Pillay, Coordinatisation and canonical bases in simple theories, J. Symbolic Logic 65 (2000), no. 1, 293–309. MR 1782121, DOI 10.2307/2586538
- P. Hell, J. Nešetřil, Colouring, constraint satisfaction, and complexity, Computer Science Review, Vol. 2 (2008) 143–163.
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- Tristan Jenkinson, J. K. Truss, and Daniel Seidel, Countable homogeneous multipartite graphs, European J. Combin. 33 (2012), no. 1, 82–109. MR 2854633, DOI 10.1016/j.ejc.2011.04.004
- 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
- Alexei S. Kolesnikov, $n$-simple theories, Ann. Pure Appl. Logic 131 (2005), no. 1-3, 227–261. MR 2097228, DOI 10.1016/j.apal.2004.06.001
- V. Koponen, Homogeneous 1-based structures and interpretability in random structures, submitted. Online: http://arxiv.org/abs/1403.3757
- A. H. Lachlan, Countable homogeneous tournaments, Trans. Amer. Math. Soc. 284 (1984), no. 2, 431–461. MR 743728, DOI 10.1090/S0002-9947-1984-0743728-1
- A. H. Lachlan, On countable stable structures which are homogeneous for a finite relational language, Israel J. Math. 49 (1984), no. 1-3, 69–153. MR 788266, DOI 10.1007/BF02760647
- Alistair H. Lachlan, Stable finitely homogeneous structures: a survey, Algebraic model theory (Toronto, ON, 1996) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 496, Kluwer Acad. Publ., Dordrecht, 1997, pp. 145–159. MR 1481442
- Alistair H. Lachlan and Allyson Tripp, Finite homogeneous $3$-graphs, Math. Logic Quart. 41 (1995), no. 3, 287–306. MR 1373115, DOI 10.1002/malq.19950410302
- Alistair H. Lachlan and Saharon Shelah, Stable structures homogeneous for a finite binary language, Israel J. Math. 49 (1984), no. 1-3, 155–180. MR 788267, DOI 10.1007/BF02760648
- A. H. Lachlan and Robert E. Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), no. 1, 51–94. MR 583847, DOI 10.1090/S0002-9947-1980-0583847-2
- Dugald Macpherson, Interpreting groups in $\omega$-categorical structures, J. Symbolic Logic 56 (1991), no. 4, 1317–1324. MR 1136459, DOI 10.2307/2275477
- Dugald Macpherson, A survey of homogeneous structures, Discrete Math. 311 (2011), no. 15, 1599–1634. MR 2800979, DOI 10.1016/j.disc.2011.01.024
- Jaroslav Ne et il, Ramsey classes and homogeneous structures, Combin. Probab. Comput. 14 (2005), no. 1-2, 171–189. MR 2128088, DOI 10.1017/S0963548304006716
- Daniel Palacín, On omega-categorical simple theories, Arch. Math. Logic 51 (2012), no. 7-8, 709–717. MR 2975425, DOI 10.1007/s00153-012-0294-7
- Anand Pillay, An introduction to stability theory, Oxford Logic Guides, vol. 8, The Clarendon Press, Oxford University Press, New York, 1983. MR 719195
- James H. Schmerl, Countable homogeneous partially ordered sets, Algebra Universalis 9 (1979), no. 3, 317–321. MR 544855, DOI 10.1007/BF02488043
- J. Sheehan, Smoothly embeddable subgraphs, J. London Math. Soc. (2) 9 (1974/75), 212–218. MR 363974, DOI 10.1112/jlms/s2-9.2.212
- S. Shelah, Classification theory and the number of nonisomorphic models, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam, 1990. MR 1083551
- 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
Additional Information
- Vera Koponen
- Affiliation: Department of Mathematics, Uppsala University, Box 480, 75106 Uppsala, Sweden
- MR Author ID: 679224
- Email: vera@math.uu.se
- Received by editor(s): June 30, 2014
- Received by editor(s) in revised form: March 6, 2015, and April 7, 2015
- Published electronically: August 12, 2015
- Communicated by: Mirna Džamonja
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 144 (2016), 1745-1759
- MSC (2010): Primary 03C10, 03C45, 03C50, 03C52, 03C68
- DOI: https://doi.org/10.1090/proc/12828
- MathSciNet review: 3451250