Portal de Periódicos da CAPES

The 42 reducts of the random ordered graph

2015; Wiley; Volume: 111; Issue: 3 Linguagem: Inglês

10.1112/plms/pdv037

1460-244X

Manuel Bodirsky, Michael Pinsker, András Pongrácz,

Graph theory and applications

Proceedings of the London Mathematical SocietyVolume 111, Issue 3 p. 591-632 Articles The 42 reducts of the random ordered graph Manuel Bodirsky, Manuel Bodirsky [email protected] http://www.math.tu-dresden.de/~bodirsky/ Institut für Algebra, TU Dresden, 01062 Dresden, GermanySearch for more papers by this authorMichael Pinsker, Corresponding Author Michael Pinsker [email protected] http://dmg.tuwien.ac.at/pinsker/ Institut für Computersprachen, Theory and Logic Group, Technische Universtät Wien, Favoritenstrasse 9/E1852, A-1040 Wien, Austria[email protected]Search for more papers by this authorAndrás Pongrácz, András Pongrácz [email protected] http://www.eis.mdx.ac.uk/staffpages/andraspongracz/ School of Science and Technology, Middlesex University, The Burroughs, London NW4 4BT, United KingdomSearch for more papers by this author Manuel Bodirsky, Manuel Bodirsky [email protected] http://www.math.tu-dresden.de/~bodirsky/ Institut für Algebra, TU Dresden, 01062 Dresden, GermanySearch for more papers by this authorMichael Pinsker, Corresponding Author Michael Pinsker [email protected] http://dmg.tuwien.ac.at/pinsker/ Institut für Computersprachen, Theory and Logic Group, Technische Universtät Wien, Favoritenstrasse 9/E1852, A-1040 Wien, Austria[email protected]Search for more papers by this authorAndrás Pongrácz, András Pongrácz [email protected] http://www.eis.mdx.ac.uk/staffpages/andraspongracz/ School of Science and Technology, Middlesex University, The Burroughs, London NW4 4BT, United KingdomSearch for more papers by this author First published: 31 July 2015 https://doi.org/10.1112/plms/pdv037Citations: 8 2010 Mathematics Subject Classification 20B27, 03C40 (primary), 05C55, 03C10 (secondary). The first and third authors have received funding from the European Research Council under the European Community's Seventh Framework Program (FP7/2007-2013 Grant Agreement no. 257039). The second author has been funded through project I836-N23 of the Austrian Science Fund (FWF) as well as through an APART fellowship of the Austrian Academy of Science. Read the full textAboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat Abstract The random ordered graph is the up to isomorphism unique countable homogeneous linearly ordered graph that embeds all finite linearly ordered graphs. We determine the reducts of the random ordered graph up to first-order interdefinability. References 1F. G. Abramson, L. Harrington, 'Models without indiscernibles', J. Symbolic Logic, 43 (1978) 572–600. 2D. Adams, A hitchhiker's guide to the galaxy (Pan Books, London, 1979). 3J. H. Bennett, 'The reducts of some infinite homogeneous graphs and tournaments', PhD Thesis, Rutgers University, Newark, 1997. 4M. Bodirsky, M. Pinsker, 'Reducts of Ramsey structures', Model theoretic methods in finite combinatorics, AMS Contemporary Mathematics 558 (2011) 489–519. 5M. Bodirsky, M. Pinsker, 'Minimal functions on the random graph', Israel J. Math., 200 (2014) 251–296. 6M. Bodirsky, M. Pinsker, 'Schaefer's theorem for graphs', A Conference Version Appeared in the Proceedings of STOC 2011, J. ACM., 62 (2015) 655–664. 7M. Bodirsky, M. Pinsker, T. Tsankov, 'Decidability of definability', J. Symbolic Logic, 78 (2013) 1036–1054. A Conference Version appeared in the Proceedings of LICS 2011, pp. 321–328. 8P. J. Cameron, 'Transitivity of permutation groups on unordered sets', Math. Z., 148 (1976) 127–139. 9P. J. Cameron, Oligomorphic permutation groups (Cambridge University Press, Cambridge, 1990). 10W. Hodges, A shorter model theory (Cambridge University Press, Cambridge, 1997). 11M. Junker, M. Ziegler, 'The 116 reducts of ( Q , , a ) ', J. Symbolic Logic, 74 (2008) 861–884. 12J. Linman, M. Pinsker, ' Permutations on the random permutation', Preprint, 2014, arXiv:1405. 4297. 13D. Macpherson, 'A survey of homogeneous structures', Discrete Math., 311 (2011) 1599–1634. 14J. Nešetřil, V. Rödl, 'Ramsey classes of set systems', J. Combin. Theory Ser. A, 34 (1983) 183–201. 15J. Nešetřil, V. Rödl, 'The partite construction and Ramsey set systems', Discrete Math., 75 (1989) 327–334. 16P. P. Pach, M. Pinsker, G. Pluhár, A. Pongrácz, C. Szabó, 'Reducts of the random partial order', Adv. Math., 267 (2014) 94–120. 17S. Thomas, 'Reducts of the random graph', J. Symbolic Logic, 56 (1991) 176–181. 18S. Thomas, 'Reducts of random hypergraphs', Ann. Pure Appl. Logic, 80 (1996) 165–193. 19T. Tsankov, ' Automorphism groups and their actions', Thèse présentée en vue de l'obtention de l'Habilitation à Diriger des Recherches, Université Paris Diderot, 2014, http://webusers.imj-prg.fr/~todor.tsankov/papers/hdr.pdf. Citing Literature Volume111, Issue3September 2015Pages 591-632 ReferencesRelatedInformation