×

Infinite motion and 2-distinguishability of graphs and groups. (English) Zbl 1307.05231

Summary: A group \(A\) acting faithfully on a set \(X\) is \(2\)-distinguishable if there is a \(2\)-coloring of \(X\) that is not preserved by any nonidentity element of \(A\), equivalently, if there is a proper subset of \(X\) with trivial setwise stabilizer. The motion of an element \(a \in A\) is the number of points of \(X\) that are moved by \(a\), and the motion of the group \(A\) is the minimal motion of its nonidentity elements. When \(A\) is finite, the Motion Lemma says that if the motion of \(A\) is large enough (specifically at least \(2\log _2 |A|\)), then the action is 2-distinguishable. For many situations where \(X\) has a combinatorial or algebraic structure, the Motion Lemma implies that the action of \(\mathrm{Aut}(X)\) on \(X\) is 2-distinguishable in all but finitely many instances. We prove an infinitary version of the Motion Lemma for countably infinite permutation groups, which states that infinite motion is large enough to guarantee 2-distinguishability. From this, we deduce a number of results, including the fact that every locally finite, connected graph whose automorphism group is countably infinite is 2-distinguishable. One cannot extend the Motion Lemma to uncountable permutation groups, but nonetheless we prove that (under the permutation topology) every closed permutation group with infinite motion has a dense subgroup which is 2-distinguishable. We conjecture an extension of the Motion Lemma which we expect holds for a restricted class of uncountable permutation groups, and we conclude with a list of open questions. The consequences of our results are drawn for orbit equivalence of infinite permutation groups.

MSC:

05E18 Group actions on combinatorial structures
05C63 Infinite graphs
05A05 Permutations, words, matrices
20B27 Infinite automorphism groups
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albertson, M.O.: Distinguishing Cartesian powers of graphs. Electron. J. Comb. 12, N17 (2005) · Zbl 1082.05047
[2] Albertson, M.O., Collins, K.L.: Symmetry breaking in graphs. Electron. J. Comb. 3, R18 (1996)
[3] Bailey, R.F., Cameron, P.J.: Base size, metric dimension and other invariants of groups and graphs. Bull. Lond. Math. Soc. 43, 209-242 (2011) · Zbl 1220.05030
[4] Cameron, P.J., Neumann, P.M., Saxl, J.: On groups with no regular orbits on the set of subsets. Arch. Math. (Basel) 43, 295-296 (1984) · Zbl 0575.20002
[5] Cameron, P.J.: Aspects of infinite permutation groups. In: Campbell, C.M. et al. (eds.) Groups St Andrews 2005, vol. 1, London Math. Soc. Lecture Note Ser. 399, pp. 1-35. CUP, Cambridge (2007) · Zbl 1119.20002
[6] Chan, M.: The maximum distinguishing number of a group. Electron. J. Comb. 13, R70 (2006) · Zbl 1096.05053
[7] Conder, M., Tucker, T.: Motion and distinguishing number two. Ars Math. Contemp. 4, 63-72 (2011) · Zbl 1236.05205
[8] Cuno, J., Imrich, W., Lehner, F.: Distinguishing graphs with infinite motion and nonlinear growth. Ars Math. Contemp. 7, 201-213 (2014) · Zbl 1301.05369
[9] Evans, D.M.: A note on automorphism groups of countably infinite structures. Arch. Math. 49, 479-483 (1987) · Zbl 0635.20001
[10] Graver, J.E., Watkins, M.E.: Locally Finite, Planar, Edge-Transitive Graphs. Memoirs of the Am. Math. Soc. 126 (1997) · Zbl 0901.05087
[11] Halin, R.: Automorphisms and endomorphisms of infinite locally finite graphs. Abh. Math. Sem. Univ. Hamburg 39, 251-283 (1973) · Zbl 0265.05118
[12] Imrich, W., Jerebic, J., Klavžar, S.: The distinguishing number of Cartesian products of complete graphs. Eur. J. Comb. 29, 922-929 (2008) · Zbl 1205.05198
[13] Imrich, W., Klavžar, S., Trofimov, V.: Distinguishing infinite graphs. Electron. J. Comb. 14, R36 (2007) · Zbl 1124.05044
[14] Klavžar, S., Wong, T.-L., Zhu, X.: Distinguishing labelings of group action on vector spaces and graphs. J. Algebra 303, 626-641 (2006) · Zbl 1105.05031
[15] Klavžar, S., Zhu, X.: Cartesian powers of graphs can be distinguished by two labels. Eur. J. Comb. 28, 303-310 (2007) · Zbl 1105.05032
[16] Kueker, D.W.: Definability, automorphisms, and infinitary languages, In: Barwise, J. (Ed.) The Syntax and Semantics of Infinitary Languages. LNM 72, Berlin-Heidelberg-New York (1968) · Zbl 0235.02018
[17] LaFlamme, C., Nguyen Van Thé, L., Sauer, N.: Distinguishing number of countable homogeneous relational structures. Electron. J. Comb. 17, R20 (2010) · Zbl 1215.05198
[18] Lehner, F.: Random colourings and automorphism breaking in locally finite graphs. Comb. Probab. Comput. 22, 885-909 (2013) · Zbl 1282.05043
[19] Lehner, F.: Distinguishing graphs with intermediate growth. Combinatorica (to appear) · Zbl 1389.05070
[20] Lockett, D.C., Macpherson, H.D.: Orbit-equivalent infinite permutation groups. J. Algebraic Comb. 38, 973-988 (2013) · Zbl 1291.20001
[21] Reyes, G.E.: Local definability theory. Ann. Math. Logic 1, 95-138 (1970) · Zbl 0217.30501
[22] Russell, A., Sundaram, R.: A note on the asymptotics and computational complexity of graph distinguishability. Electron. J. Comb. 5, R23 (1998)
[23] Seress, Á.: Primitive groups with no regular orbits on the set of subsets. Bull. Lond. Math. Soc. 29, 697-704 (1997) · Zbl 0892.20002
[24] Smith, S.M., Tucker, T.W., Watkins, M.E.: Distinguishability of infinite groups and graphs. Electron. J. Comb. 19, P27 (2012) · Zbl 1243.05086
[25] Tucker, T.: Distinguishing maps. Electron. J. Comb. 18, R50 (2011)
[26] Watkins, M.E., Zhou, X.: Distinguishability of locally finite trees. Electron. J. Comb. 14, R29 (2007) · 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.