Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-02-06T23:40:46.412Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Colourings and Automorphism Breaking in Locally Finite Graphs

Published online by Cambridge University Press:  16 September 2013

FLORIAN LEHNER
FLORIAN LEHNER*
Affiliation:
Institute of Geometry, TU Graz, Kopernikusgasse 24, A 8010 Graz, Austria (e-mail: f.lehner@tugraz.at)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A colouring of a graph G is called distinguishing if its stabilizer in Aut G is trivial. It has been conjectured that, if every automorphism of a locally finite graph moves infinitely many vertices, then there is a distinguishing 2-colouring. We study properties of random 2-colourings of locally finite graphs and show that the stabilizer of such a colouring is almost surely nowhere dense in Aut G and a null set with respect to the Haar measure on the automorphism group. We also investigate random 2-colourings in several classes of locally finite graphs where the existence of a distinguishing 2-colouring has already been established. It turns out that in all of these cases a random 2-colouring is almost surely distinguishing.

Keywords

Primary 05E18Secondary 20B2705C63
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 6 , November 2013 , pp. 885 - 909
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Albertson, M. O. and Collins, K. L. (1996) Symmetry breaking in graphs. Electron. J. Combin. 3 R18.CrossRefGoogle Scholar
[2]Cuno, J., Imrich, W. and Lehner, F. (2014) Distinguishing graphs with infinite motion and nonlinear growth. Ars Math. Contemp. 7 201–213.CrossRefGoogle Scholar
[3]Diestel, R. (2005) Graph Theory, third edition, Vol. 173 of Graduate Texts in Mathematics, Springer.Google Scholar
[4]Evans, D. M. (1987) A note on automorphism groups of countably infinite structures. Arch. Math. 49 479–483.Google Scholar
[5]Halin, R. (1973) Automorphisms and endomorphisms of infinite locally finite graphs. Abh. Math. Sem. Univ. Hamburg 39 251–283.Google Scholar
[6]Hammack, R., Imrich, W. and Klavžar, S. (2011) Handbook of Product Graphs, second edition, CPC Press.Google Scholar
[7]Imrich, W., Klavžar, S. and Trofimov, V. (2007) Distinguishing infinite graphs. Electron. J. Combin. 14 R36.Google Scholar
[8]Imrich, W., Smith, S. M., Tucker, T. and Watkins, M. E. Infinite motion and 2-distinguishability of groups and graphs. Preprint.Google Scholar
[9]Karrass, A. and Solitar, D. (1956) Some remarks on the infinite symmetric groups. Math. Z. 66 64–69.Google Scholar
[10]Lehner, F. Distinguishing graphs with intermediate growth. Preprint.Google Scholar
[11]Maurer, I. (1955) Les groupes de permutations infinies. Gaz. Mat. Fiz. Ser. A 7 400–408.Google Scholar
[12]Möller, R. G. (2010) Graphs, permutations and topological groups. arXiv.org/pdf/1008.3062v2.pdfGoogle Scholar
[13]Rubin, F. (1979) Problem 729. J. Recreational Math. 11 128. Solution in 12 (1980).Google Scholar
[14]Rudin, W. (1987) Real and Complex Analysis, third edition, McGraw-Hill.Google Scholar
[15]Russell, A. and Sundaram, R. (1998) A note on the asymptotics and computational complexity of graph distinguishability. Electron. J. Combin. 5 R23.Google Scholar
[16]Smith, S. M., Tucker, T. W. and Watkins, M. E. (2012) Distinguishability of infinite groups and graphs. Electron. J. Combin. 19 R27.Google Scholar
[17]Tucker, T. W. (2011) Distinguishing maps. Electron. J. Combin. 18 #50.Google Scholar
[18]Watkins, M. E. and Zhou, X. (2007) Distinguishability of locally finite trees. Electron. J. Combin. 14 R29.CrossRefGoogle Scholar