Conjugacy for homogeneous ordered graphs

&
Archive for Mathematical Logic 58 (3-4):457-467 (2019)
  Copy   BIBTEX

Abstract

We show that for any countable homogeneous ordered graph G, the conjugacy problem for automorphisms of G is Borel complete. In fact we establish that each such G satisfies a strong extension property called ABAP, which implies that the isomorphism relation on substructures of G is Borel reducible to the conjugacy relation on automorphisms of G.

Categories

Add categories

Keywords

Reprint years

DOI

10.1007/s00153-018-0645-0

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The conjugacy problem for automorphism groups of countable homogeneous structures.Samuel Coskey & Paul Ellis - 2016 - Mathematical Logic Quarterly 62 (6):580-589.
Uncountable Homogeneous Partial Orders.Manfred Droste, Dugald Macpherson & Alan Mekler - 2002 - Mathematical Logic Quarterly 48 (4):525-532.
Two cardinal properties of homogeneous graphs.Gregory Cherlin & Simon Thomas - 2002 - Journal of Symbolic Logic 67 (1):217-220.
Graphs realised by r.e. equivalence relations.Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan - 2014 - Annals of Pure and Applied Logic 165 (7-8):1263-1290.
The conjugacy problem for the automorphism group of the random graph.Samuel Coskey, Paul Ellis & Scott Schneider - 2011 - Archive for Mathematical Logic 50 (1-2):215-221.
Some results on ordered structures in toposes.Luís Sbardellini & Marcelo Coniglio - 2006 - Reports on Mathematical Logic:181-198.
Minimality conditions on circularly ordered structures.Beibut Sh Kulpeshov & H. Dugald Macpherson - 2005 - Mathematical Logic Quarterly 51 (4):377-399.
Finite Homogeneous 3‐Graphs.Alistair H. Lachlan & Allyson Tripp - 1995 - Mathematical Logic Quarterly 41 (3):287-306.
The complexity of random ordered structures.Joel Spencer & Katherine St John - 2008 - Annals of Pure and Applied Logic 152 (1-3):174-179.
The complexity of random ordered structures.Joel H. Spencer & Katherine St John - 2008 - Annals of Pure and Applied Logic 152 (1):174-179.
Graphs and order. The role of graphs in the theory of ordered sets and its applications, edited by rival Ivan, nato asi series c, vol. 147, D. reidel publishing company, dordrecht, boston, and Lancaster, 1985, XIX+ 796 pp. [REVIEW]R. Downey - 1992 - Journal of Symbolic Logic 57 (1):269-271.
Isomorphism of Homogeneous Structures.John D. Clemens - 2009 - Notre Dame Journal of Formal Logic 50 (1):1-22.
Emergence of geometry in a combinatorial universe.Paul Baird - 2013 - Journal of Geometry and Physics 74:185-195.
Non-genericity phenomena in ordered Fraïssé classes.Konstantin Slutsky - 2012 - Journal of Symbolic Logic 77 (3):987-1010.
Classes of Ulm type and coding rank-homogeneous trees in other structures.E. Fokina, J. F. Knight, A. Melnikov, S. M. Quinn & C. Safranski - 2011 - Journal of Symbolic Logic 76 (3):846 - 869.

Analytics

Added to PP
2018-09-09

Downloads
12 (#1,054,764)

6 months
1 (#1,533,009)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Model theory.Wilfrid Hodges - 2008 - Stanford Encyclopedia of Philosophy.

Add more references