An official website of the United States government
We generalize the notions of asymptotic dimension and coarse embeddings from metric spaces to quantum metric spaces in the sense of Kuperberg and Weaver [A von Neumann algebra approach to quantum metrics, Mem. Am. Math. Soc. 215(1010) (2012) 1–80]. We show that quantum asymptotic dimension behaves well with respect to metric quotients and direct sums, and is preserved under quantum coarse embeddings. Moreover, we prove that a quantum metric space that equi-coarsely contains a sequence of expanders must have infinite asymptotic dimension. This is done by proving a quantum version of a vertex-isoperimetric inequality for expanders, based upon a previously known edge-isoperimetric one from [K. Temme, M. J. Kastoryano, M. B. Ruskai, M. M. Wolf and F. Verstraete, The [Formula: see text]-divergence and mixing times of quantum Markov processes, J. Math. Phys. 51(12) (2010) 122201].
more »
« less
Assouad–Nagata dimension of minor‐closed metrics
Abstract Assouad–Nagata dimension addresses both large‐ and small‐scale behaviors of metric spaces and is a refinement of Gromov's asymptotic dimension. A metric space is a minor‐closed metric if there exists an (edge‐)weighted graph satisfying a fixed minor‐closed property such that the underlying space of is the vertex‐set of , and the metric of is the distance function in . Minor‐closed metrics naturally arise when removing redundant edges of the underlying graphs by using edge‐deletion and edge‐contraction. In this paper, we determine the Assouad–Nagata dimension of every minor‐closed metric. Our main theorem simultaneously generalizes known results about the asymptotic dimension of ‐minor free unweighted graphs and about the Assouad–Nagata dimension of complete Riemannian surfaces with finite Euler genus (Bonamy et al., Asymptotic dimension of minor‐closed families and Assouad–Nagata dimension of surfaces,JEMS(2024)).
more »
« less
- PAR ID:
- 10577015
- Publisher / Repository:
- Oxford University Press (OUP)
- Date Published:
- Journal Name:
- Proceedings of the London Mathematical Society
- Volume:
- 130
- Issue:
- 3
- ISSN:
- 0024-6115
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The metric dimension of a graph is the smallest number of nodes required to identify allother nodes uniquely based on shortest path distances. Applications of metric dimensioninclude discovering the source of a spread in a network, canonically labeling graphs, andembedding symbolic data in low-dimensional Euclidean spaces. This survey gives a self-contained introduction to metric dimension and an overview of the quintessential resultsand applications. We discuss methods for approximating the metric dimension of generalgraphs, and specific bounds and asymptotic behavior for deterministic and random familiesof graphs. We conclude with related concepts and directions for future work.more » « less
-
We prove that the class of reflexive asymptotic-$$c_{0}$$ Banach spaces is coarsely rigid, meaning that if a Banach space $$X$$ coarsely embeds into a reflexive asymptotic-$$c_{0}$$ space $$Y$$, then $$X$$ is also reflexive and asymptotic-$$c_{0}$$. In order to achieve this result, we provide a purely metric characterization of this class of Banach spaces. This metric characterization takes the form of a concentration inequality for Lipschitz maps on the Hamming graphs, which is rigid under coarse embeddings. Using an example of a quasi-reflexive asymptotic-$$c_{0}$$ space, we show that this concentration inequality is not equivalent to the non-equi-coarse embeddability of the Hamming graphs.more » « less
-
null (Ed.)In this paper, we study the asymptotic behavior of BV functions in complete metric measure spaces equipped with a doubling measure supporting a 1-Poincare inequality. We show that at almost every point x outside the Cantor and jump parts of a BV function, the asymptotic limit of the function is a Lipschitz continuous function of least gradient on a tangent space to the metric space based at x. We also show that, at co-dimension 1 Hausdorff measure almost every measure-theoretic boundary point of a set E of finite perimeter, there is an asymptotic limit set (E)∞ corresponding to the asymptotic expansion of E and that every such asymptotic limit (E)∞ is a quasiminimal set of finite perimeter. We also show that the perimeter measure of (E)∞ is Ahlfors co-dimension 1 regular.more » « less
-
null (Ed.)We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O (1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.more » « less
