Cayley graphs with few automorphisms: the case of infinite groups
Annales Henri Lebesgue, Volume 5 (2022), pp. 73-92.

Metadata

KeywordsGRR, 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 | Article | MR: 498225 | Zbl: 0392.05032

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

[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.) | Article | Zbl: 1289.05001

[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: 0205.00201

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

[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: 642043 | Zbl: 0476.05041

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

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

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

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

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

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

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

[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 | Article | MR: 3873496 | Zbl: 1398.05105

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

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

[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 | Article | MR: 319804 | Zbl: 0249.05123

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

[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 | Article | MR: 4072155 | Zbl: 1428.05131

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

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

[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: 363998 | Zbl: 0249.05124

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

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