Testing Cayley graph densities
[Tester les densités de graphes de Cayley.]
Arzhantseva, Goulnara N. ; Guba, Victor S. ; Lustig, Martin ; Préaux, Jean-Philippe
Annales mathématiques Blaise Pascal, Tome 15 (2008), p. 233-286 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2008-01-01
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 = {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},
     volume = {15},
     year = {2008},
     pages = {233-286},
     doi = {10.5802/ambp.249},
     zbl = {1191.20025},
     mrnumber = {2473819},
     language = {en},
     url = {http://dml.mathdoc.fr/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) pp. 233-286. doi : 10.5802/ambp.249. http://gdmltest.u-ga.fr/item/AMBP_2008__15_2_233_0/

[1] Belk, J. M.; Brown, K. S. 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] Cannon, J. W.; Floyd, W. J.; Parry, W. R. Introductory notes on Richard Thompson’s groups, L’Enseignement Mathématique, Tome 42 (2) (1996), pp. 215-256 | Zbl 0880.20027

[3] Ceccherini-Silberstein, T.; Grigorchuk, R.; De La Harpe, P. 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] Guba, V. S. 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] De La Harpe, P. Topics in geometric group theory, University of Chicago Press, Chicago, IL (2000) | Zbl 1088.20021

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