Skip to content
Texas A&M University
Mathematics

Groups and Dynamics Seminar

Date: January 20, 2021

Time: 12:00PM - 1:00PM

Location: online

Speaker: Ivan Mitrofanov, Ecole Normale Superieure, Paris

  

Title: Ordering Ratio function and Travelling Salesman Breakpoint for groups and metric spaces

Abstract: We study ordering ratio function -- an asymptotic invariant that describes how well a given metric space can be ordered. We say that an order is "good" if it can be effectively (with sub-linear competitive ratio) used as an universal order for solving traveling salesman problem. We describe connections of ordering ratio function with more traditional invariants, such as hyperbolicity, Assouad-Nagata dimension, number of ends and doubling. In particular, we characterize virtually free groups as those for which ordering ratio function satisfies $OR(3)<3$. We show that all $\delta$-hyberbolic uniformly discrete spaces can be ordered extremely effectively, with bounded ordering ratio function. We prove that all spaces of finite $AN$-dimension admit a logarithmic bound for this function, and under an additional hypothesis prove the converse, providing sufficient conditions when $OR(k)$ is linear. This talk is based on joint work with Anna Erschler.