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.
Accepté le :
Publié le :
Mots clés : GRR, DRR, ORR, Cayley graph, automorphisms of graphs, generalized dihedral group, generalized dicyclic group, regular automorphism group
@article{AHL_2022__5__73_0, author = {Leemann, Paul-Henry and de la Salle, Mikael}, title = {Cayley graphs with few automorphisms: the case of infinite groups}, journal = {Annales Henri Lebesgue}, pages = {73--92}, publisher = {\'ENS Rennes}, volume = {5}, year = {2022}, doi = {10.5802/ahl.118}, language = {en}, url = {http://www.numdam.org/articles/10.5802/ahl.118/} }
TY - JOUR AU - Leemann, Paul-Henry AU - de la Salle, Mikael TI - Cayley graphs with few automorphisms: the case of infinite groups JO - Annales Henri Lebesgue PY - 2022 SP - 73 EP - 92 VL - 5 PB - ÉNS Rennes UR - http://www.numdam.org/articles/10.5802/ahl.118/ DO - 10.5802/ahl.118 LA - en ID - AHL_2022__5__73_0 ER -
Leemann, Paul-Henry; de la Salle, Mikael. Cayley graphs with few automorphisms: the case of infinite groups. Annales Henri Lebesgue, Tome 5 (2022), pp. 73-92. doi : 10.5802/ahl.118. http://www.numdam.org/articles/10.5802/ahl.118/
[Bab78] Infinite digraphs with given regular automorphism groups, J. Comb. Theory, Volume 25 (1978) no. 1, pp. 26-46 | DOI | MR | Zbl
[Bab80] Finite digraphs with given regular automorphism groups, Period. Math. Hung., Volume 11 (1980) no. 4, pp. 257-270 | DOI | MR | Zbl
[Ben13] 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] 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] On covers of graphs by Cayley graphs, Eur. J. Comb., Volume 64 (2017), pp. 57-65 | DOI | MR | Zbl
[God81] 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] Über reguläre graphische Darstellung von auflösbaren Gruppen, Ph. D. Thesis, Technische Universität Berlin, Deutschland (1976)
[Imr69] Graphen mit transitiver Automorphismengruppe, Monatsh. Math., Volume 73 (1969), pp. 341-347 | DOI | MR | Zbl
[Imr75] On graphs with regular groups, J. Comb. Theory, Volume 19 (1975) no. 2, pp. 174-180 | DOI | MR | Zbl
[IW76] On automorphism groups of Cayley graphs, Period. Math. Hung., Volume 7 (1976) no. 3-4, pp. 243-258 | DOI | MR | Zbl
[LS21] Cayley graphs with few automorphisms, J. Algebr. Comb., Volume 53 (2021) no. 4, pp. 1117-1146 | DOI | MR | Zbl
[Man94] Finite groups containing many involutions, Proc. Am. Math. Soc., Volume 122 (1994) no. 2, pp. 383-385 | DOI | MR | Zbl
[Man18] Groups satisfying identities with high probability, Int. J. Algebra Comput., Volume 28 (2018) no. 8, pp. 1575-1584 | DOI | MR | Zbl
[MS18] 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] Groups covered by permutable subsets, J. Lond. Math. Soc., Volume 29 (1954), pp. 236-248 | DOI | MR | Zbl
[Neu89] Two combinatorial problems in group theory, Bull. Lond. Math. Soc., Volume 21 (1989) no. 5, pp. 456-458 | DOI | MR | Zbl
[NW72] Graphical regular representations of non-abelian groups. I, II, Can. J. Math., Volume 24 (1972), pp. 993-1018 | DOI | MR | Zbl
[Rob95] A course in the theory of groups, Graduate Texts in Mathematics, 80, Springer, 1995 | Zbl
[ST19] Characterizing a vertex-transitive graph by a large ball, J. Topol., Volume 12 (2019) no. 3, pp. 705-743 | DOI | MR | Zbl
[Toi20] Commuting probabilities of infinite groups, J. Lond. Math. Soc., Volume 101 (2020) no. 3, pp. 1280-1297 | DOI | MR | Zbl
[Wat71] On the action of non-Abelian groups on graphs, J. Comb. Theory, Volume 11 (1971), pp. 95-104 | DOI | MR | Zbl
[Wat72] On graphical regular representations of , Graph Theory Appl., Proc. Conf. Western Michigan Univ. 1972 (Lecture Notes in Mathematics), Volume 303, Springer, 1972, pp. 305-311 | MR | Zbl
[Wat74] Graphical regular representations of alternating, symmetric, and miscellaneous small groups, Aequationes Math., Volume 11 (1974), pp. 40-50 | DOI | MR | Zbl
[Wat76] Graphical regular representations of free products of groups, J. Comb. Theory, Volume 21 (1976) no. 1, pp. 47-56 | DOI | MR | Zbl
Cité par Sources :