Open Collections

Symmetry Breaking

Banff International Research Station for Mathematical Innovation and Discovery

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 [1996] 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 [1977] on regular trees, Cameron et al.\ [1984] and Seress [1997] 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. [1984] and Russel and Sundaram [1997]) 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$.

Mathematics; Combinatorics; Group theory and generalizations; Discrete mathematics

video/mp4

Author affiliation: Colgate University

2019-03-17

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/68822

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/