BIRS Workshop Lecture Videos
Symmetry Breaking Tucker, Thomas
Given a group $A$ acting on a set $X$, the distinguishing number, or asymmetric coloring number, denoted $D(A,X)$ or $ACN(A,X)$, is the smallest $k$ such that $X$ has a $k$-coloring where the only elements of $A$ preserving the coloring fix all elements of $X$, thus "breaking" the symmetry of $X$ under $A$. Albertson and Collins  introduced and named $D(G)$ in the context of a graph $G$ with $A=Aut(G), X=V(G)$, but precedents include Babai's work  on regular trees, Cameron et al.\  and Seress  on regular orbits for a primitive permutation group acting on the set of subsets of $X$, and work of many authors on the graph isomorphism problem using colors to "individualize" vertices. This talk will survey various aspects of symmetry breaking: contexts other than graphs (such as maps), bounds relating $D(G)$ and the maximal degree of $G$, variations of $D(G)$ where the coloring is proper or where edges are colored instead of vertices. An underlying theme is the role of the elementary "Motion Lemma'' (Cameron et al.  and Russel and Sundaram ) that $D\leq 2$ when $m(A)>2\log_2(|A|)$, where $m(A)$ is the minimum number of elements of $X$ moved by any element of $A$ not acting as the identity on $X$.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International