Infinite Limits of Finite-Dimensional Permutation Structures, and their Automorphism Groups: Between Model Theory and Combinatorics

arXiv1805.04219MaRDI QIDQ6301448FDOQ6301448

Authors: Samuel Braunfeld 

Publication date: 10 May 2018

Abstract: In the course of classifying the homogeneous permutations, Cameron introduced the viewpoint of permutations as structures in a language of two linear orders, and this structural viewpoint is taken up here. The majority of this thesis is concerned with Cameron's problem of classifying the homogeneous structures in a language of finitely many linear orders, which we call finite-dimensional permutation structures. Towards this problem, we present a construction that we conjecture produces all such structures. Some evidence for this conjecture is given, including the classification of the homogeneous 3-dimensional permutation structures. We next consider the topological dynamics, in the style of Kechris, Pestov, and Todorv{c}evi'c, of the automorphism groups of the homogeneous finite-dimensional permutation structures we have constructed, which requires proving a structural Ramsey theorem for all the associated amalgamation classes. Because the $emptyset$-definable equivalence relations in these homogeneous finite-dimensional permutation structures may form arbitrary finite distributive lattices, the model-theoretic algebraic closure operation may become quite complex, and so we require the framework recently introduced by Hubiv{c}ka and Nev{s}etril. Finally, we consider the decision problem for whether a finitely-constrained permutation avoidance class is atomic, or equivalently, has the joint embedding property. As a first approximation to this problem, we prove the undecidability of the corresponding decision problem in the category of graphs. Modifying this proof also gives the undecidability, in the category of graphs, of the corresponding decision problem for the joint homomorphism property, which is of interest in infinite-domain constraint satisfaction problems.

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Models with special properties (saturated, rigid, etc.) (03C50) Dynamical systems involving transformations and group actions with special properties (minimality, distality, proximality, expansivity, etc.) (37B05) Ramsey theory (05D10) Model theory of denumerable and separable structures (03C15)

This page was built for publication: Infinite Limits of Finite-Dimensional Permutation Structures, and their Automorphism Groups: Between Model Theory and Combinatorics

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