Some remarks on the orbit dimension of transitive groups and on the metric dimension of Johnson graphs

Abstract

The orbit dimension $\sigma (G)$ (also called the separation number or rigidity index) of a permutation group $G$ with domain $\Omega$ is the minimum cardinality of a subset $S\subseteq \Omega$ such that, for any two distinct elements $\omega ,{\omega }^{\prime }\in \Omega$, there exists $\alpha \in S$ for which $\omega$ and ${\omega }^{\prime }$ lie in distinct orbits of the stabilizer $G_{\alpha }$. In this paper, we first observe that if $G$ is transitive, then $\sigma (G)\le |\Omega |-r+1$, where $r$ is the rank of $G$, and we obtain strong structural information on the groups for which equality holds. Next, we investigate the orbit dimension in the case where $G$ is the symmetric group of degree $n$, acting on the set of $k$-subsets of $\{1,\dots ,n\}$. In this case, this invariant equals the metric dimension of Johnson graphs.

18 pages