Distinguishing numbers for graphs and groups (Q1883683)

Summary: A graph \(G\) is distinguished if its vertices are labelled by a map \(\varphi:V(G)\to\{1,2,\dots,k\}\) so that no non-trivial graph automorphism preserves \(\varphi\). The distinguishing number of \(G\) is the minimum number \(k\) necessary for \(\varphi\) 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 \(\varphi:X\to\{1,2,\dots,k\}\) is distinguishing if no element of \(\Gamma\) preserves \(\varphi\) except those which fix each element of \(X\). The distinguishing number of the group action on \(X\) is the minimum \(k\) needed for \(\varphi\) 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.