Asymptotic dimension, Isoperimetric Problem, and Traveling Salesman Problem in Groups

In many groups, the optimal diameter for the solutions of the isoperimetric problem is asymptotically equivalent to the lower bound coming from their cardinality; in this situation one says that the Følner function is lossless with respect to the isodiametric function. Answering a question of Nowak, we prove that for some   groups the Følner function is not lossless, and we compute the asymptotics of the isodiametric function in many examples.

We study the relationship between the isodiametric function, the control function for the asymptotic dimension of the group, and an invariant related to the Universal Traveling Salesman Problem. We prove that the isodiametric function is equivalent to the control function for the asymptotic dimension for a broad class of groups with a lossless Følner function. In particular, this applies to the diagonal products of Brieussel–Zheng associated with a sequence of expander graphs.

For our main examples, the Følner function is not lossless with respect to the isodiametric function; nevertheless, we show that in these examples the control function is lossless with respect to the isodiametric one. Such groups include wreath products, Hall’s nilpotent-by-abelian groups, and Lampshuffler groups. While many amenable groups of finite Assouad–Nagata dimension have a lossless control function, we also construct examples with a non-lossless control function.

We also discuss open problems concerning how the isoperimetric problem influences algebraic properties of groups. We show that every amenable group of finite Assouad–Nagata dimension has Shalom’s property HFD. In particular, such groups cannot be simple and cannot be purely torsion. The first conclusion contrasts with the simple groups of Burger and Mozes, some of which are quasi-isometric to a product of two trees and therefore have Assouad–Nagata dimension two.