Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1430

Preprint Number 1430

Previous Next Preprint server

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

Submission date: 11 May 2018


The author's thesis. Much of the first 8 chapters appeared in the previous articles “The Lattice of Definable Equivalence Relations in Homogeneous n-Dimensional Permutation Structures”, “Ramsey expansions of Λ-ultrametric spaces”, and “Homogeneous 3-dimensional permutation structures”

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 Todorčević, 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 ∅-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 Hubička and Nešetřil.
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: 03C13, 03C15, 03C50, 05D10, 37B05

Keywords and phrases:

Full text arXiv 1805.04219: pdf, ps.

Last updated: March 23 2021 10:20 Please send your corrections to: