(Abstract taken from arXiv paper.) We study asymptotic invariants of metric spaces and infinite groups related to the universal Travelling Salesman Problem (TSP). We prove that spaces with doubling property (in particular virtually nilpotent groups) admit Gap for Ordering Ratio functions which holds for all orders on these spaces. We describe Travelling Salesman Breakpoint for finite graphs. We characterize groups with Travelling Salesman Breakpoint ≤ 3 as virtually free ones. We show that Ordering Ratio function is bounded (which is the best possible situation) for all uniformly discrete δ-hyperbolic spaces of bounded geometry, in particular for all hyperbolic groups. We prove that any metric space, containing weakly a sequence of arbitrarily large cubes, has infinite Travelling Salesman Breakpoint; this means that any order on such spaces satisfies OR(s)=s for all s. This is the worst possible case for Ordering Ratio functions. For a sequence of finite graphs, we provide a sufficient spectral condition for OR(s)=s. This condition is in particular satisfied for any sequence of expander graphs. Under this stronger assumption of being a family of expander graphs, we prove a stronger claim about snakes of bounded width. We show that any metric space of finite Assouad-Nagata dimension admits an order satisfying OR(s) ≤ Const ln s, and discuss general Gap Problems for Ordering Ratio functions.
Joint work with Ivan Mitrofanov. This talk raltes to this arXiv paper, and the link is to the latest version.
This video is part of the New York Group Theory Cooperative‘s Manhatten algebra day.
