Symmetry breaking in graphs

2015-10-26
11:00-12:00
Famnit-VP
Wilfried Imrich (Department Mathematics and Information Technology, Montanuniversität Leoben, Austria)
Symmetry breaking in graphs

In a graph, a set of vertices that is stabilized setwise by only the trivial automorphism is called a distinguishing set. Tom Tucker conjectured that every connected, infinite locally finite graph G has such a set if each nontrivial automorphism of G moves infinitely many vertices. The conjecture is know as the Infinite Motion Conjecture, which is still open despite the fact that numerous large classes of graphs have been shown to satisfy it. 

In finite graphs distinguishing sets, if they exist, can be very small in comparison to the size of the graph, and in infinite graphs such sets can be finite. If they are not finite, their density can be zero. 

This talk introduces to  the subject and presents new results about the density of distinguishing sets and the  Infinite Motion Conjecture.