Finite Homomorphism-Homogeneous Permutations via Edge Colourings of Chains

  • Igor Dolinka
  • Éva Jungábel
Keywords: Homomorphism-homogeneous, Finite permutation, Linear order

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.
Published
2012-11-01
Article Number
P17