Infinite permutations of lowest maximal pattern complexity

An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we define maximal pattern complexity for infinite permutations and show that this complexity function is ultimately constant if and only if the permutation is ultimately periodic; otherwise its maximal pattern complexity is at least n, and the value is reached exactly on a family of permutations constructed by Sturmian words.