Conjugacy for homogeneous ordered graphs

DOI10.1007/S00153-018-0645-0MaRDI QIDQ1734273zbMATH OpenOpenAlexWikidataFDO

Authors Samuel Coskey, Paul Ellis

Publication date 27 March 2019

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.04609, https://scholarworks.boisestate.edu/math_facpubs/222

zbMATH Keywords

conjugacyhomogeneous structureBorel complexityordered graphs

Mathematics Subject Classification ID

Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Descriptive set theory (03E15) Graph theory (05C99) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Model theory of denumerable and separable structures (03C15)

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$.

Recommendations

• The conjugacy problem for automorphism groups of homogeneous digraphs
• Elements of finite order in automorphism groups of homogeneous structures.
• Homogeneous ordered graphs, metrically homogeneous graphs, and beyond. Volume 1. Ordered graphs and distanced graphs
• Ordered structures and large conjugacy classes

Cites work

• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 1522814 (Why is no real title available?)
• A survey of homogeneous structures
• Homogeneous ordered graphs, metrically homogeneous graphs, and beyond. Volume 1. Ordered graphs and distanced graphs
• Invariant descriptive set theory
• Katětov functors
• The conjugacy problem for automorphism groups of homogeneous digraphs
• The conjugacy problem for the automorphism group of the random graph

Cited in

(3)

• Homogeneously orderable graphs
• ON EXTENSIONS OF PARTIAL ISOMORPHISMS
• The conjugacy problem for automorphism groups of homogeneous digraphs

This page was built for publication: Conjugacy for homogeneous ordered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1734273)