Cayley graphs with few automorphisms: the case of infinite groups

Leemann, Paul-Henry; de la Salle, Mikael

Annales Henri Lebesgue, Tome 5 (2022), pp. 73-92.

Nous caractérisons les groupes de type fini qui admettent un graphe de Cayley dont les seuls automorphismes sont les translations. Cela confirme une conjecture de Watkins formulée en 1976. Les preuves reposent sur des méthodes de marches aléatoires. Une conséquence des résultats est que tout groupe de type fini admet un graphe de Cayley dont le groupe d’automorphismes est dénombrable. Nous obtenons des résultats similaires pour les graphes dirigés.

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.

Classification : 53C28, 53C26, 32Q45
Mots clés : GRR, DRR, ORR, Cayley graph, automorphisms of graphs, generalized dihedral group, generalized dicyclic group, regular automorphism group

[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\times 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