On WQO Property for Different Quasi Orderings of the Set of Permutations

The property of certain sets being well quasi ordered (WQO) has several useful applications in computer science – it can be used to prove the existence of efficient algorithms and also in certain cases to prove that a specific algorithm terminates.

One of such sets of interest is the set of permutations. The fact that the set of permutations is not WQO has been rediscovered several times and a number of different permutation antichains have been published. However these results apply to a specific ordering relation of permutations

$\preccurlyeq$

, which is not the only ’natural’ option and an alternative ordering relation of permutations

$\trianglelefteq$

(more related to ’graph’ instead of ’sorting’ properties of permutations) is often of larger practical interest. It turns out that the known examples of antichains for the ordering

$\preccurlyeq$

can’t be used directly to establish that

$\trianglelefteq$

is not WQO.

In this paper we study this alternative ordering relation of permutations

$\trianglelefteq$

and give an example of an antichain with respect to this ordering, thus showing that

$\trianglelefteq$

is not WQO. In general antichains for

$\trianglelefteq$

cannot be directly constructed from antichains for

$\preccurlyeq$

, however the opposite is the case – any antichain for

$\trianglelefteq$

allows to construct an antichain for

$\preccurlyeq$

.