Testing Cayley graph densities
Goulnara N. Arzhantseva; Victor S. Guba; Martin Lustig; Jean-Philippe Préaux
Annales Mathématiques Blaise Pascal, Volume 15 (2008) no. 2, p. 233-286

We present a computer-assisted analysis of combinatorial properties of the Cayley graphs of certain finitely generated groups: given a group with a finite set of generators, we study the density of the corresponding Cayley graph, that is, the least upper bound for the average vertex degree (= number of adjacent edges) of any finite subgraph. It is known that an m-generated group is amenable if and only if the density of the corresponding Cayley graph equals to 2m. We test amenable and non-amenable groups, and also groups for which amenability is unknown. In the latter class we focus on Richard Thompson’s group F.

Nous présentons une analyse assistée par ordinateur de propriétés combinatoires des graphes de Cayley de certains groupes de type fini : donnés un groupe et un ensemble fini de générateurs, nous étudions la densité du graphe de Cayley correspondant, c’est à dire, la borne supérieure de la valence de sommet (= nombre d’arêtes adjacentes) moyenne de tous ses sous-graphes finis. Il est connu qu’un groupe ayant m générateurs est moyennable si et seulement si la densité du graphe de Cayley correspondant est 2m. Nous testons des groupes moyennables et non-moyennables, ainsi que d’autres dont la moyennabilité est inconnue. Dans cette dernière classe nous nous intéressons au groupe F de Thompson.

DOI : https://doi.org/10.5802/ambp.249
Classification:  20-04,  20F05
Keywords: Amenability, Thompson’s group F, computer-assisted analysis
@article{AMBP_2008__15_2_233_0,
     author = {Arzhantseva, Goulnara N. and Guba, Victor S. and Lustig, Martin and Pr\'eaux, Jean-Philippe},
     title = {Testing Cayley graph densities},
     journal = {Annales Math\'ematiques Blaise Pascal},
     publisher = {Annales math\'ematiques Blaise Pascal},
     volume = {15},
     number = {2},
     year = {2008},
     pages = {233-286},
     doi = {10.5802/ambp.249},
     mrnumber = {2473819},
     zbl = {1191.20025},
     language = {en},
     url = {https://ambp.centre-mersenne.org/item/AMBP_2008__15_2_233_0}
}
Arzhantseva, Goulnara N.; Guba, Victor S.; Lustig, Martin; Préaux, Jean-Philippe. Testing Cayley graph densities. Annales Mathématiques Blaise Pascal, Volume 15 (2008) no. 2, pp. 233-286. doi : 10.5802/ambp.249. https://ambp.centre-mersenne.org/item/AMBP_2008__15_2_233_0/

[1] J. M. Belk; K. S. Brown Forest diagrams for elements of Thompson’s group F, Internat. J. Algebra Comput., Tome 15 (5-6) (2005), pp. 815-850 | Article | Zbl pre05017961

[2] J. W. Cannon; W. J. Floyd; W. R. Parry Introductory notes on Richard Thompson’s groups, L’Enseignement Mathématique, Tome 42 (2) (1996), pp. 215-256 | Zbl 0880.20027

[3] T. Ceccherini-Silberstein; R. Grigorchuk; P. de la Harpe Amenability and paradoxal decompositions for pseudogroups and for discrete metric spaces, Proc. Steklov Inst. Math., Tome 224 (1) (1999), pp. 57-97 | MR 1721355 | Zbl 0968.43002

[4] V. S. Guba On the properties of the Cayley graph of Richard Thompson’s group F, Internat. J. Algebra Comput., Tome 14 (5-6) (2004), pp. 677-702 | Article | MR 1786869 | Zbl 0965.20025

[5] P. de la Harpe Topics in geometric group theory, University of Chicago Press, Chicago, IL (2000) | Zbl 1088.20021

[6] R.S. Lyndon; P.E. Schupp Combinatorial group theory, Springer-Verlag, Berlin (2001) (Reprint of the 1977 edition) | MR 1812024 | Zbl 0997.20037