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 .
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.
Keywords: Amenability, Thompson’s group $F$, computer-assisted analysis
Mots-clés : Moyennabilité, groupe $F$ de Thompson, analyse assistée par ordinateur
Goulnara N. Arzhantseva 1; Victor S. Guba 2; Martin Lustig 3; Jean-Philippe Préaux 4
@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 AU - Goulnara N. Arzhantseva AU - Victor S. Guba AU - Martin Lustig AU - Jean-Philippe Préaux 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 - https://ambp.centre-mersenne.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 Goulnara N. Arzhantseva %A Victor S. Guba %A Martin Lustig %A Jean-Philippe Préaux %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://ambp.centre-mersenne.org/articles/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] 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
Cited by Sources: