We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Symmetry Breaking

Formal Metadata

Title
Symmetry Breaking
Title of Series
Number of Parts
19
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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≤2 when m(A)>2log2(|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.