Predavatelj: Wilfried Imrich (Montanuniversitaet, Leoben, Avstrija)
A coloring of the vertices of a graph G is called distinguishing if the stabilizer
of the coloring in the automorphism group of G is trivial. Tom Tucker
conjectured that, if every automorphim of a connected, locally finite graph moves
infinitely many vertices, then there exists a distinguishing 2-coloring, that is, a coloring
using only two colors. This is known as the infinite Motion Conjecture.
Despite many
intriguing partial results, it is still open in general.
of the coloring in the automorphism group of G is trivial. Tom Tucker
conjectured that, if every automorphim of a connected, locally finite graph moves
infinitely many vertices, then there exists a distinguishing 2-coloring, that is, a coloring
using only two colors. This is known as the infinite Motion Conjecture.
Despite many
intriguing partial results, it is still open in general.
This conjecture, its generalizations to uncountable graphs, to groups
acting on structures, and to endomorphims of countable and uncountable graphs and structures,
has become an inspiring topic and spawned numerous papers.
In this talk I will present generalizations of the Infinite Motion
Conjecture, to
random colorings on countable graphs, and other generalizations to
uncountable graphs. I will also shortly describe some of the methods used to obtain solutions
for various classes of graphs, this includes the permutation toplogy on countable sets and related topological spaces, in particular Polish spaces.
