Has the following kind of problem been investigated previously and, where can I find information about it:
Given
the set $\mathbb{P}_{n_0}$ of all permutations of $n_0$ elements
a predicate $P: p\in\mathbb{P}_{n_0}\mapsto w\in\{true,false\}$
an equivalence relation $R:(p,q)\in\mathbb{P}_{n_0}\times\mathbb{P}_{n_0}\mapsto w\in\{true,false\}$
a maximal subset $\mathcal{P}\subseteq\mathbb{P}_{n_0}:\ p\in\mathcal{P}\iff P(p)=true,\ (p,q)\in\mathbb{P}_{n_0}\times\mathbb{P}_{n_0}\implies R(p,q)=false$
determine the set of maximal sub-permutations, that are found in every $p\in\mathcal{P}$?
$$ $$
Background:
this question is a generalisation of Calculating a Combinatorial Generalization of Planar Convex Hulls and was motivated by Joseph O'Rourke's request for an example of a $k$-hull in his comment.
The attempt to devise some brute force algorithm for hunting down such a specimen led to some very fruitful ideas and solutions and, also to the "discovery" of what the essence of the problem actually is.
I could find information about the statistics of random permutations (e.g here, but nothing that relates to invariant sub-permutations as specified above,
so any pointers to literature or online resources would be appeciated.
$$ $$
Examples of predicates may be (but are not limited to) certain degrees of optimality of tours in TSP instances.
Examples for equivalence of tours may be invariance of the length measure under cyclic permutation of vertex labels and/or invariance under inversion of their sequence, as found in the problems of finding directed or undirected optimal Hamilton paths or cycles.
