On distinguishing labelling of sets under the wreath product action (Q6114162)

A distinguishing labeling of a graph \(G\) is a vertex-labeling of the graph such that no non-trivial automorphism of the graph \(G\) preserves the vertex labels. The distinguishing number of \(G\) is the minimum number of labels \(D(G)\) necessary to distinguish the graph \(G\). For instance, if \(C_n\) is the cyclic graph of order \(n\geq3\), then \(D(C_n)=3\) for \(n=3,4,5\) and \(D(C_n)=2\) for \(n\geq6\). The concept of distinguishing labeling and the distinguishing number of a graph was introduced in [\textit{M. Albertson} and \textit{K. Collins}, Electron. J. Comb. 3, No. 1, Research paper R18, 17 p. (1996); printed version J. Comb. 3, No. 1, 259--275 (1996; Zbl 0851.05088)]. \textit{J. Tymoczko} [Electron. J. Comb. 11, No. 1, Research paper R63, 13 p. (2004; Zbl 1058.05038)] extended the concept of distinguishing labeling and distinguishing number of a graph to an arbitrary group action of a group on a set, as follows. Let a group \(G\) acting faithfully on a set \(X\). An \(r\)-labeling \(f:X\to\{1,2,\ldots,r\}\) of \(X\) is distinguishing with respect to the action \(G\) if the only label-preserving permutation of \(X\) in \(G\) is the identity. The distinguishing number of the action of \(G\) on \(X\) is the minimum \(r\) for which there is an \(r\)-labeling which is distinguishing. It is easy to see, for example, that the distinguishing number for the action of the symmetric group \(S_n\) on the set \(\{1,2,\ldots,n\}\) is \(n\). In the paper under review, the authors prove that the distinguishing number of the group \(\overrightarrow{S_n}\) on the set \(\{1,2,\ldots,2n\}\) is one more than the \(n\)-th term of the sequence\phantom{ } ``\(1, 2, 2, 3, 3, 3, 4, \ldots\) (\(n\) appears \(n\) times)''. Note that here the group \(\overrightarrow{S_n}\) is isomorphic to the wreath product of the groups \(\mathbb{Z}_2\) by \(S_n\) and \(\overrightarrow{S_n}\) can be identified as the following subgroup of the symmetric group \(S_{2n}\): \[ \overrightarrow{S_n}=\{\theta\in S_{2n}\mid\theta(i)+\theta(2n-i+1)=2n+1\}. \] For convenience, \(S_{2n}\) is treated as the group of permutations of \(\{1,\ldots,n,-n,\ldots,-1\}\) then \[ \overrightarrow{S_n}=\{\theta\in S_{2n}\mid\theta(i)+\theta(-i)=0\}, \] see [\textit{C. Musili}, Representations of finite groups. New Delhi: Hindustan Book Agency (1993; Zbl 1043.20500)].