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

Symmetry Breaking

Formale Metadaten

Titel
Symmetry Breaking
Serientitel
Anzahl der Teile
19
Autor
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.