Infinite limits of finite-dimensional permutation structures, and their automorphism groups
Citation & Export
Hide
Simple citation
Braunfeld, Samuel Walker.
Infinite limits of finite-dimensional permutation structures, and their automorphism groups. Retrieved from
https://doi.org/doi:10.7282/T33R0X8C
Export
Description
TitleInfinite limits of finite-dimensional permutation structures, and their automorphism groups
Date Created2018
Other Date2018-05 (degree)
Extent1 online resource (x, 133 p. : ill.)
DescriptionIn the course of classifying the homogeneous permutations, Cameron introduced the viewpoint of permutations as structures in a language of two linear orders [7], 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 0-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šetril [16]. Finally, we turn to the interaction of model theory with more classical topics in the theory of permutation avoidance classes. 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. The results in the first 8 chapters of this thesis largely appeared in the previous articles [4], [5], and [6]. In many places the arguments and context have been expanded upon, and in the case of some arguments from [4], they have been simplified.
NotePh.D.
NoteIncludes bibliographical references
Noteby Samuel Walker Braunfeld
Genretheses, ETD doctoral
Languageeng
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.