What non-abelian groups have a minimal permutation representation that acts transitively $\{1,2,\ldots, k\}$? This question asks if a minimal permutation representation $\overline{G}$ of a group $G$ (that is, a subgroup $\overline{G} \le S_k$ is isomorphic to $G$ and $k$ is minimal with respect to this condition) must act transitively on $\\{1,2,\ldots,k\\}$. The answer is no: indeed, I showed in my answer that the only abelian groups which have a minimal permutation representation acting transitively on $\\{1,2,\ldots,k\\}$ are $G \cong \mathbb{Z}/p^n\mathbb{Z}$. However, all of the answer to the question seem to leverage the commutativity of $G$ to force $\overline{G}$ to be generated by disjoint cycles. Is there anything that can be said for nonabelian $G$?

An example of a nonabelian group that is not a direct product in which the smallest degree faithful permutaion representation is intransitive is the group $\langle x,y \mid x^3=y^4=1, y^{-1}xy=x^{-1} \rangle$ of order $12$.

It embeds into $S_7$ with $x \mapsto (1,2,3)$, $y \mapsto (2,3)(4,5,6,7)$. The smallest degree transitive representation is the regular representation of degree $12$.

In general it seems to be a difficult problem to determine the smallest $k$ for a general finite group $G$, and I don't think that there is ay known efficient algorithm for doing this. Even if you can find all subgroups of the group, there are a lot of different possibilities for intransitive representations.