James Cannon, Brigham Young University

Abstract:

Our intent is to provide a theoretical background for algorithmically exploring the amenability and nonamenability of discrete groups. The work is much in the spirit of [Goulnara N. Arzhantseva, Victor S. Guba, Martin Lustig, and Jean-Philippe Prèeaux, Testing Cayley graph densities, Annales Mathèematiques Blaise Paxcal 15, 233-386 (2008)], though we have not as yet collected the same beautiful set of experimental data.

Erling Folner proved that the amenability or nonamenability of a group depends on the complexity of its finite subsets S ⊂ G. Complexity has three measures: the maximum Folner ratio, the optimal cooling function, and the minimum cooling norm. We show that these measures are, for a fixed finite subset, precisely dual to one another and that they can be found by minimizing a certain simple convex function on a high dimensional simplex, with the optimum occurring at the barycenter of a face of the simplex. The optimization problem, though having a completely discrete interpretation, can thus be reduced to a standard linear programming problem.

We also give combinatorial conditions for passing into a smaller face of the simplex, with a guarantee that the desired barycenter lies in a face of that smaller face.

The combinatorial results suggest a very interesting constrained isoperimetric problem valid in any space in which it is possible to give a reasonable measure of both set-size and boundary-size. The combinatorial arguments applied to the metric balls of Z² allow us to give a precise solution to this constrained isoperimetric problem in any metric L₁-ball in the Euclidean plane, with standard set-area and with boundary-lengths measured in the taxi-cab (L₁) metric.