Testing Cayley graph densities

Abstract

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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>m</mml:mi> </mml:math> -generated group is amenable if and only if the density of the corresponding Cayley graph equals to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> . 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> .