Suppose Gamma is a group acting on a set X. An r-labeling f : X -> {1, 2,...., r) of X is distinguishing (with respect to Gamma) if the only label preserving permutation of X in Gamma is the identity. The distinguishing number, D-Gamma(X), of the action of Gamma on X is the minimum r for which there is an r-labeling which is distinguishing. This paper investigates the relation between the cardinality of a set X and the distinguishing numbers of group actions on X. For a positive integer n, let D(n) be the set of distinguishing numbers of transitive group actions on a set X of cardinality n, i.e., D(n) = {D-Gamma(X) : vertical bar X vertical bar = n and Gamma acts transitively on X}. We prove that vertical bar D(n)vertical bar = O(root n). Then we consider the problem of an arbitrary fixed group Gamma acting on a large set. We prove that if for any action of Gamma on a set Y, for each proper normal subgroup H of Gamma, D-H (Y) <= 2, then there is an integer n such that for any set X with vertical bar X vertical bar >= n, for any action of Gamma on X with no fixed points, D-Gamma(X) <= 2. (C) 2008 Elsevier B.V. All rights reserved.
