Distinguishing Numbers for Graphs and Groups

Abstract

A graph $G$ is distinguished if its vertices are labelled by a map $\phi: V(G) \longrightarrow \{1,2,\ldots, k\}$ so that no non-trivial graph automorphism preserves $\phi$. The distinguishing number of $G$ is the minimum number $k$ necessary for $\phi$ to distinguish the graph. It measures the symmetry of the graph.

We extend these definitions to an arbitrary group action of $\Gamma$ on a set $X$. A labelling $\phi: X \longrightarrow \{1,2,\ldots,k\}$ is distinguishing if no element of $\Gamma$ preserves $\phi$ except those which fix each element of $X$. The distinguishing number of the group action on $X$ is the minimum $k$ needed for $\phi$ to distinguish the group action. We show that distinguishing group actions is a more general problem than distinguishing graphs.

We completely characterize actions of $S_n$ on a set with distinguishing number $n$, answering an open question of Albertson and Collins.