Towards the undecidability of atomicity for permutation classes via the undecidability of joint embedding for hereditary graph classes

Samuel Braunfeld

Published 2019-03-28Version 1

We work towards answering a question of Ru\v{s}kuc on the decidability of atomicity for permutation classes, which is equivalent to the decidability of the joint embedding property when permutations are viewed as structures in a language of two linear orders. We begin by showing the corresponding question is undecidable for hereditary graph classes, via a reduction from the tiling problem. After an interlude also showing the undecidability of the joint homomorphism property for hereditary graph classes, we show the undecidability of the joint embedding property for 3-dimensional permutations, i.e. structures in a language of 3 linear orders. Both of these later proofs are obtained by adapting the first proof for hereditary graph classes.