Distinguishing actions of symmetric groups and related graphs

Abstract

The distinguishing number $D(G,X)$ of an action of a group $G$ on a set $X$ is the least size of a partition of $X$ such that no element of $G$ acting nontrivially on $X$ preserves this partition. In this paper we describe the distinguishing numbers for all actions of the symmetric group $S_n$, for any $n\ge 3$. This allows us to describe the distinguishing numbers for all graphs whose automorphism group is isomorphic with a symmetric group. Our description solves a few open problems posed by various authors in earlier papers on this topic.