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 : 10.5802/ambp.249
Classification : 20-04, 20F05
Keywords: Amenability, Thompson’s group $F$, computer-assisted analysis
Mot clés : Moyennabilité, groupe $F$ de Thompson, analyse assistée par ordinateur
Arzhantseva, Goulnara N. 1 ; Guba, Victor S. 2 ; Lustig, Martin 3 ; Préaux, Jean-Philippe 4

1 Section de Mathématiques Université de Genève CP 64, 1211 Genève 4 SWITZERLAND
2 Department of Mathematics Vologda State University 6 S. Orlov St., Vologda 160600 RUSSIA
3 LATP, UMR CNRS 6632 Mathématiques Université d’Aix-Marseille III Avenue Escadrille Normandie-Niemen 13397 Marseille cédex 20 FRANCE
4 Centre de recherche de l’Armée de l’air Ecole de l’air 13661 Salon-air FRANCE LATP, UMR CNRS 6632 Université de Provence 39 rue Joliot-Curie 13453 Marseille cédex 13 FRANCE
@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},
     pages = {233--286},
     publisher = {Annales math\'ematiques Blaise Pascal},
     volume = {15},
     number = {2},
     year = {2008},
     doi = {10.5802/ambp.249},
     zbl = {1191.20025},
     mrnumber = {2473819},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/ambp.249/}
}
TY  - JOUR
AU  - Arzhantseva, Goulnara N.
AU  - Guba, Victor S.
AU  - Lustig, Martin
AU  - Préaux, Jean-Philippe
TI  - Testing Cayley graph densities
JO  - Annales mathématiques Blaise Pascal
PY  - 2008
SP  - 233
EP  - 286
VL  - 15
IS  - 2
PB  - Annales mathématiques Blaise Pascal
UR  - http://www.numdam.org/articles/10.5802/ambp.249/
DO  - 10.5802/ambp.249
LA  - en
ID  - AMBP_2008__15_2_233_0
ER  - 
%0 Journal Article
%A Arzhantseva, Goulnara N.
%A Guba, Victor S.
%A Lustig, Martin
%A Préaux, Jean-Philippe
%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 http://www.numdam.org/articles/10.5802/ambp.249/
%R 10.5802/ambp.249
%G en
%F 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. http://www.numdam.org/articles/10.5802/ambp.249/

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

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

[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., Volume 224 (1) (1999), pp. 57-97 | MR | Zbl

[4] Guba, V. S. 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 | DOI | MR | Zbl

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

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

Cité par Sources :