×

Motion and distinguishing number two. (English) Zbl 1236.05205

Summary: A group \(A\) acting faithfully on a finite set \(X\) is said to have distinguishing number two if there is a proper subset \(Y\) whose (setwise) stabilizer is trivial. The motion of \(A\) acting on \(X\) is defined as the largest integer \(k\) such that all non-trivial elements of \(A\) move at least \(k\) elements of \(X\). The Motion Lemma of Russell and Sundaram states that if the motion is at least \(2 \log_2 |A|\), then the action has distinguishing number two. When \(X\) is a vector space, group, or map, the Motion Lemma and elementary estimates of the motion together show that in all but finitely many cases, the action of Aut\((X)\) on \(X\) has distinguishing number two. A new lower bound for the motion of any transitive action gives similar results for transitive actions with restricted point-stabilizers. As an instance of what can happen with intransitive actions, it is shown that if \(X\) is a set of points on a closed surface of genus \(g\), and \(|X|\) is sufficiently large with respect to \(g\), then any action on \(X\) by a finite group of surface homeomorphisms has distinguishing number two.

MSC:

05E18 Group actions on combinatorial structures
05E15 Combinatorial aspects of groups and algebras (MSC2010)
05C10 Planar graphs; geometric and topological aspects of graph theory
20B05 General theory for finite permutation groups

Software:

Magma; GAP
PDFBibTeX XMLCite
Full Text: DOI