Some Remarks on the Orbit Dimension of Transitive Groups and on the Metric Dimension of Johnson Graphs

Source abstract

Abstract The orbit dimension $$\sigma (G)$$ σ ( 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$$ S ⊆ Ω such that, for any two distinct elements $$\omega ,\omega '\in \Omega$$ ω , ω ′ ∈ Ω , there exists $$\alpha \in S$$ α ∈ S for which $$\omega$$ ω and $$\omega '$$ ω ′ lie in distinct orbits of the stabilizer $$G_\alpha$$ G α . In this paper, we first consider transitive permutation groups. If G has rank r , then we show that $$\sigma (G)\le |\Omega |-r+1$$ σ ( G ) ≤ | Ω | - r + 1 , and we obtain structural information on the groups for which equality holds. We then investigate the orbit dimension of the symmetric group $$\textrm{Sym}(m)$$ Sym ( m ) in its action on the k -subsets of $$\{1,\ldots ,m\}$$ { 1 , … , m } . In this action, the orbit dimension coincides with the metric dimension of the Johnson graph J ( m , k ). We obtain new upper and lower bounds for $$\sigma (m,k)$$ σ ( m , k ) , improving previously known estimates, and we refine these bounds further in the case $$k=3.$$ k = 3 .