The undecidability of joint embedding for 3-dimensional permutation classes

MaRDI QIDQ5074775zbMATH OpenFDO

Authors Samuel Braunfeld

Publication date 10 May 2022

Full work available at URL https://arxiv.org/abs/2002.11494, https://dmtcs.episciences.org/8461

zbMATH Keywords

atomic permutation avoidance classjoint embeddingpermutationsundecidable joint embedding property

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Permutations, words, matrices (05A05)

Abstract: As a step towards resolving a question of Ruv{s}kuc on the decidability of joint embedding for hereditary classes of permutations, which may be viewed as structures in a language of 2 linear orders, we show the corresponding problem is undecidable for hereditary classes of structures in a language of 3 linear orders.

Recommendations

• Simple permutations: Decidability and unavoidable substructures
• Homogeneous 3-dimensional permutation structures
• Hereditary undecidability of some theories of finite structures
• Composability of permutation classes
• An undecidable problem in finite combinatorics

Cites work

• An infinite antichain of permutations
• Forbidden substructures and combinatorial dichotomies: WQO and universality
• Ramsey-type and amalgamation-type properties of permutations
• The undecidability of the domino problem

Cited in

(2)

• Decidability of well quasi-order and atomicity for equivalence relations under embedding orderings
• Well quasi-order and atomicity for combinatorial structures under consecutive orders

This page was built for publication: The undecidability of joint embedding for 3-dimensional permutation classes

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