An official website of the United States government
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
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
-
-
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
-
Abstract Alinear forestis a disjoint union of path graphs. Thelinear arboricity of a graph, denoted by , is the least number of linear forests into which the graph can be partitioned. Clearly, for any graph of maximum degree . For the upper bound, the long‐standingLinear Arboricity Conjecture(LAC) due to Akiyama, Exoo, and Harary from 1981 asserts that . A graph is apseudoforestif each of its components contains at most one cycle. In this paper, we prove thatthe union of any two pseudoforests of maximum degree up to 3 can be decomposed into three linear forests. Combining it with a recent result of Wdowinski on the minimum number of pseudoforests into which a graph can be decomposed, we prove that the LAC holds for the following simple graph classes: ‐degenerate graphs with maximum degree , all graphs on nonnegative Euler characteristic surfaces provided the maximum degree , and graphs on negative Euler characteristic surfaces provided the maximum degree , as well as graphs with no ‐minor satisfying some conditions on maximum degrees.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
-
A<sc>bstract</sc> By quantifying the distance between two collider events, one can triangulate a metric space and reframe collider data analysis as computational geometry. One popular geometric approach is to first represent events as an energy flow on an idealized celestial sphere and then define the metric in terms of optimal transport in two dimensions. In this paper, we advocate for representing events in terms of a spectral function that encodes pairwise particle angles and products of particle energies, which enables a metric distance defined in terms of one-dimensional optimal transport. This approach has the advantage of automatically incorporating obvious isometries of the data, like rotations about the colliding beam axis. It also facilitates first-principles calculations, since there are simple closed-form expressions for optimal transport in one dimension. Up to isometries and event sets of measure zero, the spectral representation is unique, so the metric on the space of spectral functions is a metric on the space of events. At lowest order in perturbation theory in electron-positron collisions, our metric is simply the summed squared invariant masses of the two event hemispheres. Going to higher orders, we present predictions for the distribution of metric distances between jets in fixed-order and resummed perturbation theory as well as in parton-shower generators. Finally, we speculate on whether the spectral approach could furnish a useful metric on the space of quantum field theories.more » « less
