Assouad-Nagata dimension and gap for ordered metric spaces

DOI10.4171/CMH/549arXiv2109.12181OpenAlexW3202538755MaRDI QIDQ6058052FDOQ6058052

Authors: Anna Erschler, Ivan Mitrofanov 

Publication date: 26 October 2023

Published in: Commentarii Mathematici Helvetici (Search for Journal in Brave)

Abstract: We prove that all spaces of finite Assouad-Nagata dimension admit a good order for Travelling Salesman Problem, and provide sufficient conditions under which the converse is true. We formulate a conjectural characterisation of spaces of finite $AN$-dimension, which would yield a gap statement for the efficiency of orders on metric spaces. Under assumption of doubling, we prove a stronger gap phenomenon about all orders on a given metric space.

Full work available at URL: https://arxiv.org/abs/2109.12181

Recommendations

• Assouad-Nagata dimension of locally finite groups and asymptotic cones
• Asymptotic cones and Assouad-Nagata dimension
• Assouad dimension, Nagata dimension, and uniformly close metric tangents
• Assouad-Nagata dimension via Lipschitz extensions

zbMATH Keywords

asymptotic dimensionnilpotent groupswreath productsdoubling propertyuniform embeddingsAssouad-Nagata dimensionquasi-isometric invariants

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Geometric group theory (20F65) Asymptotic properties of groups (20F69) Metric spaces, metrizability (54E35) Nilpotent groups (20F18) Dimension theory in general topology (54F45)

Cites Work

• Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions
• Expander graphs and their applications
• Ramanujan graphs
• A New Short Proof of Kneser's Conjecture
• Title not available (Why is that?)
• Special cube complexes
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Universal approximations for TSP, Steiner tree, and set cover
• Sorting in \(c \log n\) parallel steps
• A proof of Alon’s second eigenvalue conjecture and related problems
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Spacefilling curves and the planar travelling salesman problem
• The diameter of random regular graphs
• Assouad-Nagata dimension of wreath products of groups
• Title not available (Why is that?)
• Embeddings of hyperbolic groups into products of binary trees
• Embedding mapping class groups into a finite product of trees
• Mixing and relaxation time for random walk on wreath product graphs
• Every Coxeter group acts amenably on a compact space
• Note on dimension theory for metric spaces
• Mixing times for random walks on finite lamplighter groups
• An O(N log N) planar travelling salesman heuristic based on spacefilling curves
• How groups grow.
• A fixed point theorem in \(L^p\)-spaces
• Assouad-Nagata dimension of connected Lie groups
• Title not available (Why is that?)
• Assouad-Nagata dimension of locally finite groups and asymptotic cones
• On exactness and isoperimetric profiles of discrete groups
• Designing networks with good equilibria under uncertainty
• Small cancellation labellings of some infinite graphs and applications
• Improved lower bounds for the universal and a priori TSP
• Lamplighter groups, de Brujin graphs, spider-web graphs and their spectra
• Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
• Triangle inequalities in path metric spaces
• Poincaré profiles of groups and spaces
• An optimal lower bound for hierarchical universal solutions for TSP on the plane
• Assouad-Nagata dimension of finitely generated \(C^\prime(\frac{1}{6})\) groups
• Optimal lower bounds for universal and differentially private Steiner trees and TSPs
• An improved upper bound for the universal TSP on the grid
• Spaces that can be ordered effectively: virtually free groups and hyperbolicity

Cited In (1)

• The metric relaxation for 0 -extension admits an Ω(log ^2/3 k) gap

This page was built for publication: Assouad-Nagata dimension and gap for ordered metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6058052)