[Tester les densités de graphes de Cayley.]
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 générateurs est moyennable si et seulement si la densité du graphe de Cayley correspondant est . 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 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 -generated group is amenable if and only if the density of the corresponding Cayley graph equals to . 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 .
Keywords: Amenability, Thompson’s group $F$, computer-assisted analysis
Mot 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},
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.5802/ambp.249/
[1] Forest diagrams for elements of Thompson’s group , Internat. J. Algebra Comput., Volume 15 (5-6) (2005), pp. 815-850 | DOI
[2] Introductory notes on Richard Thompson’s groups, L’Enseignement Mathématique, Volume 42 (2) (1996), pp. 215-256 | Zbl
[3] 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] On the properties of the Cayley graph of Richard Thompson’s group , Internat. J. Algebra Comput., Volume 14 (5-6) (2004), pp. 677-702 | DOI | MR | Zbl
[5] Topics in geometric group theory, University of Chicago Press, Chicago, IL, 2000 | Zbl
[6] Combinatorial group theory, Springer-Verlag, Berlin, 2001 (Reprint of the 1977 edition) | MR | Zbl
Cité par Sources :
