Volume 5 (2022)
Leemann, Paul-Henry; de la Salle, Mikael
Cayley graphs with few automorphisms: the case of infinite groups
Annales Henri Lebesgue, Volume 5 (2022), pp. 73-92.

Metadata

DOI10.5802/ahl.118
Keywords GRR, DRR, ORR, Cayley graph, automorphisms of graphs, generalized dihedral group, generalized dicyclic group, regular automorphism group

Abstract

We characterize the finitely generated groups that admit a Cayley graph whose only automorphisms are the translations, confirming a conjecture by Watkins from 1976. The proof relies on random walk techniques. As a consequence, every finitely generated group admits a Cayley graph with countable automorphism group. We also treat the case of directed graphs.


References

[Bab78] Babai, László Infinite digraphs with given regular automorphism groups, J. Comb. Theory, Volume 25 (1978) no. 1, pp. 26-46 | DOI | MR | Zbl

[Bab80] Babai, László Finite digraphs with given regular automorphism groups, Period. Math. Hung., Volume 11 (1980) no. 4, pp. 257-270 | DOI | MR | Zbl

[Ben13] Benjamini, Itai Coarse geometry and randomness, Lecture Notes in Mathematics, 2100, Springer, 2013 (Lecture notes from the 41st Probability Summer School held in Saint-Flour, 2011. Chapter 5 is due to Nicolas Curien, Chapter 12 was written by Ariel Yadin, and Chapter 13 is joint work with Gady Kozma, École d’Été de Probabilités de Saint-Flour.) | DOI | Zbl

[ERS70] Erdős, Pál; Rényi, Alfréd; Sós, Vera Túran Combinatorial theory and its applications. I-III. Proceedings of a colloqium, Balatonfüred, 1969, Colloquia Mathematica Societatis János Bolyai, 4, North-Holland, 1970 | Zbl

[Geo17] Georgakopoulos, Agelos On covers of graphs by Cayley graphs, Eur. J. Comb., Volume 64 (2017), pp. 57-65 | DOI | MR | Zbl

[God81] Godsil, Christopher D. GRRs for nonsolvable groups, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) (Colloquia Mathematica Societatis János Bolyai), Volume 25, North-Holland, 1981, pp. 221-239 | MR | Zbl

[Het76] Hetzel, D. Über reguläre graphische Darstellung von auflösbaren Gruppen, Ph. D. Thesis, Technische Universität Berlin, Deutschland (1976)

[Imr69] Imrich, Wilfried Graphen mit transitiver Automorphismengruppe, Monatsh. Math., Volume 73 (1969), pp. 341-347 | DOI | MR | Zbl

[Imr75] Imrich, Wilfried On graphs with regular groups, J. Comb. Theory, Volume 19 (1975) no. 2, pp. 174-180 | DOI | MR | Zbl

[IW76] Imrich, Wilfried; Watkins, Mark E. On automorphism groups of Cayley graphs, Period. Math. Hung., Volume 7 (1976) no. 3-4, pp. 243-258 | DOI | MR | Zbl

[LS21] Leemann, Paul-Henry; de la Salle, Mikael Cayley graphs with few automorphisms, J. Algebr. Comb., Volume 53 (2021) no. 4, pp. 1117-1146 | DOI | MR | Zbl

[Man94] Mann, Avinoam Finite groups containing many involutions, Proc. Am. Math. Soc., Volume 122 (1994) no. 2, pp. 383-385 | DOI | MR | Zbl

[Man18] Mann, Avinoam Groups satisfying identities with high probability, Int. J. Algebra Comput., Volume 28 (2018) no. 8, pp. 1575-1584 | DOI | MR | Zbl

[MS18] Morris, Joy; Spiga, Pablo Classification of finite groups that admit an oriented regular representation, Bull. Lond. Math. Soc., Volume 50 (2018) no. 5, pp. 811-831 | DOI | MR | Zbl

[Neu54] Neumann, Bernhard H. Groups covered by permutable subsets, J. Lond. Math. Soc., Volume 29 (1954), pp. 236-248 | DOI | MR | Zbl

[Neu89] Neumann, Peter M. Two combinatorial problems in group theory, Bull. Lond. Math. Soc., Volume 21 (1989) no. 5, pp. 456-458 | DOI | MR | Zbl

[NW72] Nowitz, Lewis A.; Watkins, Mark E. Graphical regular representations of non-abelian groups. I, II, Can. J. Math., Volume 24 (1972), pp. 993-1018 | DOI | MR | Zbl

[Rob95] Robinson, Derek J. S. A course in the theory of groups, Graduate Texts in Mathematics, 80, Springer, 1995 | Zbl

[ST19] de la Salle, Mikael; Tessera, Romain Characterizing a vertex-transitive graph by a large ball, J. Topol., Volume 12 (2019) no. 3, pp. 705-743 | DOI | MR | Zbl

[Toi20] Tointon, Matthew C. H. Commuting probabilities of infinite groups, J. Lond. Math. Soc., Volume 101 (2020) no. 3, pp. 1280-1297 | DOI | MR | Zbl

[Wat71] Watkins, Mark E. On the action of non-Abelian groups on graphs, J. Comb. Theory, Volume 11 (1971), pp. 95-104 | DOI | MR | Zbl

[Wat72] Watkins, Mark E. On graphical regular representations of C n ×Q, Graph Theory Appl., Proc. Conf. Western Michigan Univ. 1972 (Lecture Notes in Mathematics), Volume 303, Springer, 1972, pp. 305-311 | MR | Zbl

[Wat74] Watkins, Mark E. Graphical regular representations of alternating, symmetric, and miscellaneous small groups, Aequationes Math., Volume 11 (1974), pp. 40-50 | DOI | MR | Zbl

[Wat76] Watkins, Mark E. Graphical regular representations of free products of groups, J. Comb. Theory, Volume 21 (1976) no. 1, pp. 47-56 | DOI | MR | Zbl