Finite Homomorphism-Homogeneous Permutations via Edge Colourings of Chains

Abstract

A relational structure is homomorphism-homogeneous if any homomorphism between its finite substructures extends to an endomorphism of the structure in question. In this note, we characterise all permutations on a finite set enjoying this property. To accomplish this, we switch from the more traditional view of a permutation as a set endowed with two linear orders to a different representation by a single linear order (considered as a directed graph with loops) whose non-loop edges are coloured in two colours, thereby `splitting' the linear order into two posets.