Testing Cayley graph densities
Annales Mathématiques Blaise Pascal, Volume 15 (2008) no. 2, pp. 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: 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 = {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},
     pages = {233--286},
     publisher = {Annales math\'ematiques Blaise Pascal},
     volume = {15},
     number = {2},
     year = {2008},
     doi = {10.5802/ambp.249},
     mrnumber = {2473819},
     zbl = {1191.20025},
     language = {en},
     url = {https://ambp.centre-mersenne.org/articles/10.5802/ambp.249/}
}
TY  - JOUR
TI  - Testing Cayley graph densities
JO  - Annales Mathématiques Blaise Pascal
PY  - 2008
DA  - 2008///
SP  - 233
EP  - 286
VL  - 15
IS  - 2
PB  - Annales mathématiques Blaise Pascal
UR  - https://ambp.centre-mersenne.org/articles/10.5802/ambp.249/
UR  - https://www.ams.org/mathscinet-getitem?mr=2473819
UR  - https://zbmath.org/?q=an%3A1191.20025
UR  - https://doi.org/10.5802/ambp.249
DO  - 10.5802/ambp.249
LA  - en
ID  - AMBP_2008__15_2_233_0
ER  - 
%0 Journal Article
%T Testing Cayley graph densities
%J Annales Mathématiques Blaise Pascal
%D 2008
%P 233-286
%V 15
%N 2
%I Annales mathématiques Blaise Pascal
%U https://doi.org/10.5802/ambp.249
%R 10.5802/ambp.249
%G en
%F AMBP_2008__15_2_233_0
Goulnara N. Arzhantseva; Victor S. Guba; Martin Lustig; Jean-Philippe Préaux. 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/articles/10.5802/ambp.249/

[1] J. M. Belk; K. S. Brown Forest diagrams for elements of Thompson’s group F, Internat. J. Algebra Comput., Volume 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, Volume 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., Volume 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., Volume 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

Cited by Sources: