Random colourings and automorphism breaking in locally finite graphs

Florian Lehner
Universit\"at Hamburg

PDF

Minisymposium: GENERAL SESSION TALKS

Content: A colouring of a graph G is called distinguishing if it is not preserved by any nontrivial automorphism of G. Equivalently, a colouring is distinguishing if its stabiliser in the automorphism group is trivial, i.e., only consists of the identity. Tucker conjectured that, if each automorphism of a graph moves infinitely many vertices, then there is a distinguishing 2-colouring of G. In this talk we investigate the stabiliser of a random 2-colouring of such a graph in order to make progress towards Tucker's conjecture. We show that these stabilisers are almost surely close to being trivial. More precisely, they are nowhere dense in the topology of pointwise convergence and have Haar measure 0 in the automorphism group.

Back to all abstracts