×

Bounding the distinguishing number of infinite graphs and permutation groups. (English) Zbl 1301.05138

Summary: A group of permutations \(G\) of a set \(V\) is \(k\)-distinguishable if there exists a partition of \(V\) into \(k\) cells such that only the identity permutation in \(G\) fixes setwise all of the cells of the partition. The least cardinal number \(k\) such that \((G,V)\) is \(k\)-distinguishable is its distinguishing number \(D(G,V)\). In particular, a graph \(\Gamma\) is \(k\)-distinguishable if its automorphism group \(\mathrm{Aut}(\Gamma)\) satisfies \(D(\mathrm{Aut}(\Gamma),V\Gamma)\leqslant k\).
Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph \(\Gamma\) is not \(k\)-distinguishable (for a given cardinal \(k\)), then it contains a ball of finite radius whose distinguishing number is at least \(k\). Moreover, this lower bound cannot be sharpened, since for any integer \(k \geqslant 3\) there exists an infinite, locally finite, connected graph \(\Gamma\) that is not \(k\)-distinguishable but in which every ball of finite radius is \(k\)-distinguishable.
In the second half of this paper we show that a large distinguishing number for an imprimitive group \(G\) is traceable to a high distinguishing number either of a block of imprimitivity or of the induced action by \(G\) on the corresponding system of imprimitivity. An immediate application is to automorphism groups of infinite imprimitive graphs. These results are companion to the study of the distinguishing number of infinite primitive groups and graphs in a previous paper by S. M. Smith et al. [Electron. J. Comb. 19, No. 2, Research Paper P27, 10 p. (2012; Zbl 1243.05086)].

MSC:

05C15 Coloring of graphs and hypergraphs
05C63 Infinite graphs
20B27 Infinite automorphism groups
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

Citations:

Zbl 1243.05086
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] M. O. Albertson and K. L. Collins. Symmetry breaking in graphs. Electron. J. Combin., 3, 1996, #R18. · Zbl 0851.05088
[2] M. Bhattacharjee, D. Macpherson, R. G. M¨oller, and P. M. Neumann. Notes on infinite permutation groups, volume 1698 of Lecture Notes in Mathematics SpringerVerlag, 1998. · Zbl 0916.20002
[3] N. G. de Bruijn and P. Erd˝os. A color problem for infinite graphs and a problem in the theory of relations. Indagationes Math., 13:369-373, 1951. · Zbl 0044.38203
[4] M. Chan. The distinguishing number of the direct product and wreath product action. J Algebr. Comb., 24:331-345, 2006. · Zbl 1113.20002
[5] K. L. Collins and A. N. Trenk. The Distinguishing Chromatic Number. Electron. J. Combin., 13, 2006, #R16. · Zbl 1081.05033
[6] G. A. Dirac and S. Schuster. A theorem of Kuratowski. Indagationes Math., 16:343– 348, 1954. · Zbl 0055.17002
[7] W. Imrich, S. Klav˘zar, and V. Trofimov. Distinguishing infinite graphs. Electron. J. Combin., 14, 2007, #R36. · Zbl 1124.05044
[8] ´A. Seress. Primitive groups with no regular orbits on the set of subsets. Bull. London Math. Soc., 29(6):697-704, 1997. · Zbl 0892.20002
[9] S. M. Smith, T. W. Tucker, and M. E. Watkins. Distinguishability of infinite groups and graphs. Electron. J. Combin., 19, 2012, #P27. · Zbl 1243.05086
[10] M. E. Watkins and X. Zhou. Distinguishability of locally finite trees. Electron. J. Combin., 14, 2007, #R29. · Zbl 1112.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.