{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T23:58:43Z","timestamp":1778543923554,"version":"3.51.4"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2013,9,16]],"date-time":"2013-09-16T00:00:00Z","timestamp":1379289600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>A colouring of a graph<jats:italic>G<\/jats:italic>is called distinguishing if its stabilizer in Aut<jats:italic>G<\/jats:italic>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<jats:italic>G<\/jats:italic>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.<\/jats:p>","DOI":"10.1017\/s0963548313000382","type":"journal-article","created":{"date-parts":[[2013,9,16]],"date-time":"2013-09-16T13:35:53Z","timestamp":1379338553000},"page":"885-909","source":"Crossref","is-referenced-by-count":7,"title":["Random Colourings and Automorphism Breaking in Locally Finite Graphs"],"prefix":"10.1017","volume":"22","author":[{"given":"FLORIAN","family":"LEHNER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,9,16]]},"reference":[{"key":"S0963548313000382_ref14","volume-title":"Real and Complex Analysis","author":"Rudin","year":"1987"},{"key":"S0963548313000382_ref7","doi-asserted-by":"crossref","first-page":"R36","DOI":"10.37236\/954","article-title":"Distinguishing infinite graphs","volume":"14","author":"Imrich","year":"2007","journal-title":"Electron. J. Combin."},{"key":"S0963548313000382_ref10","unstructured":"Lehner F. Distinguishing graphs with intermediate growth. Preprint."},{"key":"S0963548313000382_ref17","doi-asserted-by":"crossref","first-page":"#50","DOI":"10.37236\/537","article-title":"Distinguishing maps","volume":"18","author":"Tucker","year":"2011","journal-title":"Electron. J. Combin."},{"key":"S0963548313000382_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02992834"},{"key":"S0963548313000382_ref8","unstructured":"Imrich W. , Smith S. M. , Tucker T. and Watkins M. E. Infinite motion and 2-distinguishability of groups and graphs. Preprint."},{"key":"S0963548313000382_ref1","doi-asserted-by":"crossref","first-page":"R18","DOI":"10.37236\/1242","article-title":"Symmetry breaking in graphs","volume":"3","author":"Albertson","year":"1996","journal-title":"Electron. J. Combin."},{"key":"S0963548313000382_ref16","doi-asserted-by":"crossref","first-page":"R27","DOI":"10.37236\/2283","article-title":"Distinguishability of infinite groups and graphs","volume":"19","author":"Smith","year":"2012","journal-title":"Electron. J. Combin."},{"key":"S0963548313000382_ref12","unstructured":"M\u00f6ller R. G. (2010) Graphs, permutations and topological groups. arXiv.org\/pdf\/1008.3062v2.pdf"},{"key":"S0963548313000382_ref18","doi-asserted-by":"crossref","first-page":"R29","DOI":"10.37236\/947","article-title":"Distinguishability of locally finite trees","volume":"14","author":"Watkins","year":"2007","journal-title":"Electron. J. Combin."},{"key":"S0963548313000382_ref3","volume-title":"Graduate Texts in Mathematics","author":"Diestel","year":"2005"},{"key":"S0963548313000382_ref13","first-page":"128","article-title":"Problem 729","volume":"11","author":"Rubin","year":"1979","journal-title":"J. Recreational Math."},{"key":"S0963548313000382_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01194294"},{"key":"S0963548313000382_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01186596"},{"key":"S0963548313000382_ref6","doi-asserted-by":"crossref","DOI":"10.1201\/b10959","volume-title":"Handbook of Product Graphs","author":"Hammack","year":"2011"},{"key":"S0963548313000382_ref15","doi-asserted-by":"crossref","first-page":"R23","DOI":"10.37236\/1361","article-title":"A note on the asymptotics and computational complexity of graph distinguishability","volume":"5","author":"Russell","year":"1998","journal-title":"Electron. J. Combin."},{"key":"S0963548313000382_ref2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.26493\/1855-3974.334.fe4","article-title":"Distinguishing graphs with infinite motion and nonlinear growth.","volume":"7","author":"Cuno","year":"2014","journal-title":"Ars Math. Contemp."},{"key":"S0963548313000382_ref11","first-page":"400","article-title":"Les groupes de permutations infinies.","volume":"7","author":"Maurer","year":"1955","journal-title":"Gaz. Mat. Fiz. Ser. A"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000382","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,4]],"date-time":"2020-08-04T03:39:53Z","timestamp":1596512393000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000382\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,16]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["S0963548313000382"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000382","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,16]]}}}