Distinguishing labeling of group actions

Suppose ΓΓ is a group acting on a set XX. An rr-labeling f:X→{1,2,…,r}f:X→{1,2,…,r} of XX is distinguishing (with respect to ΓΓ) if the only label preserving permutation of XX in ΓΓ is the identity. The distinguishing number, DΓ(X)DΓ(X), of the action of ΓΓ on XX is the minimum rr for which there is an rr-labeling which is distinguishing. This paper investigates the relation between the cardinality of a set XX and the distinguishing numbers of group actions on XX. For a positive integer nn, let D(n)D(n) be the set of distinguishing numbers of transitive group actions on a set XX of cardinality nn, i.e., D(n)={DΓ(X):|X|=n and Γ acts transitively on X}D(n)={DΓ(X):|X|=n and Γ acts transitively on X}. We prove that |D(n)|=O(n). Then we consider the problem of an arbitrary fixed group ΓΓ acting on a large set. We prove that if for any action of ΓΓ on a set YY, for each proper normal subgroup HH of ΓΓ, DH(Y)≤2DH(Y)≤2, then there is an integer nn such that for any set XX with |X|≥n|X|≥n, for any action of ΓΓ on XX with no fixed points, DΓ(X)≤2DΓ(X)≤2.