Mathematics colloquium, September 9:th: Florian Lehner

[Aron Lagerberg]

Speaker: Florian Lehner, (Graz University of Technology)

Date and time: Monday, September 9:th, 15.00

Place: VRII, room 157

Title: Symmetry breaking in graphs

Abstract: Let $G =(V,E)$ be a graph and let $c \colon V \to C$ be a colouring of the vertices of $G$. Then $c$ is said to be distinguishing if it is not preserved by any non-trivial automorphism of $G$. The distinguishing number of a graph is the least number of colours needed for a distinguishing colouring.

Assume that there is a finite constant $m$ such that the automorphism group of $G$ contains at most $2^{\frac{m}{2}}$ elements and each non-trivial automorphism of $G$ moves at least $m$ vertices. Then it is known that there is a distinguishing $2$-colouring of $G$. The same has been conjectured to be true for locally finite graphs and $m = \aleph_0$.
We give several classes of graphs where this conjecture is known to be true and show that random $2$-colourings have a good chance of being distinguishing.