Testing Cayley graph densities
[Tester les densités de graphes de Cayley.]
Annales Mathématiques Blaise Pascal, Tome 15 (2008) no. 2, pp. 233-286.

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.

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.

DOI : https://doi.org/10.5802/ambp.249
Classification : 20-04,  20F05
Mots clés: Moyennabilité, groupe F de Thompson, analyse assistée par ordinateur
@article{AMBP_2008__15_2_233_0,
     author = {Goulnara N. Arzhantseva and Victor S. Guba and Martin Lustig and Jean-Philippe Pr\'eaux},
     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 = {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, Tome 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