Geodesic
Testing Cayley graph densities
[Tester les densités de graphes de Cayley.]
Arzhantseva, Goulnara N.1  ; Guba, Victor S.2  ; Lustig, Martin3 ; Préaux, Jean-Philippe4
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
Annales mathématiques Blaise Pascal, Tome 15 (2008) no. 2, pp. 233-286.

Voir la notice de l'article provenant de la source Numdam

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
Mots-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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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 | Zbl | MR

[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 | Zbl | MR

[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) | Zbl | MR

Cité par Sources :