Analyst's traveling salesman theorem

Last updated

The analyst's traveling salesman problem is an analog of the traveling salesman problem in combinatorial optimization. In its simplest and original form, it asks which plane sets are subsets of rectifiable curves of finite length. Whereas the original traveling salesman problem asks for the shortest way to visit every vertex in a finite set with a discrete path, this analytical version may require the curve to visit infinitely many points.

Contents

β-numbers

A rectifiable curve has tangents at almost all of its points, where in this case "almost all" means all but a subset whose one-dimensional Hausdorff measure is zero. Accordingly, if a set is contained in a rectifiable curve, the set must look flat when zooming in on almost all of its points. This suggests that testing us whether a set could be contained in a rectifiable curve must somehow incorporate information about how flat it is when one zooms in on its points at different scales.

This discussion motivates the definition of the following quantity, for a plane set :

there is a line so that for every dist

Where is the set that is to be contained in a rectifiable curve, is any square, is the side length of , and dist measures the distance from to the line . Intuitively, is the width of the smallest rectangle containing the portion of inside , and hence gives a scale invariant notion of flatness.

Jones' traveling salesman theorem in R2

Let Δ denote the collection of dyadic squares, that is,

where denotes the set of integers. For a set , define

where diam E is the diameter of E. Then Peter Jones's [1] analyst's traveling salesman theorem may be stated as follows:

Generalizations and Menger curvature

Euclidean space and Hilbert space

The Traveling Salesman Theorem was shown to hold in general Euclidean spaces by Kate Okikiolu, [2] that is, the same theorem above holds for sets , d > 1, where Δ is now the collection of dyadic cubes in defined in a similar way as dyadic squares. In her proof, the constant C grows exponentially with the dimension d.

With some slight modifications to the definition of β(E), Raanan Schul [3] showed Traveling Salesman Theorem also holds for sets E that lie in any Hilbert Space, and in particular, implies the theorems of Jones and Okikiolu, where now the constant C is independent of dimension. (In particular, this involves using β-numbers of balls instead of cubes).

Menger curvature and metric spaces

Hahlomaa [4] further adjusted the definition of β(E) to get a condition for when a set E of an arbitrary metric space may be contained in the Lipschitz-image of a subset of positive measure. For this, he had to redefine the definition of the β-numbers using menger curvature (since in a metric space there isn't necessarily a notion of a cube or a straight line).

Menger curvature, as in the previous example, can be used to give numerical estimates that determine whether a set contains a rectifiable subset, and the proofs of these results frequently depend on β-numbers.

Denjoy–Riesz theorem

The Denjoy–Riesz theorem gives general conditions under which a point set can be covered by the homeomorphic image of a curve. This is true, in particular, for every compact totally disconnected subset of the Euclidean plane. However, it may be necessary for such an arc to have infinite length, failing to meet the conditions of the analyst's traveling salesman theorem.

Related Research Articles

In mathematics, a continuous function is a function such that a continuous variation of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value, known as discontinuities. More precisely, a function is continuous if arbitrarily small changes in its value can be assured by restricting to sufficiently small changes of its argument. A discontinuous function is a function that is not continuous. Up until the 19th century, mathematicians largely relied on intuitive notions of continuity, and considered only continuous functions. The epsilon–delta definition of a limit was introduced to formalize the definition of continuity.

In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of n-dimensional Euclidean space. For n = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called n-dimensional volume, n-volume, or simply volume. It is used throughout real analysis, in particular to define Lebesgue integration. Sets that can be assigned a Lebesgue measure are called Lebesgue-measurable; the measure of the Lebesgue-measurable set A is here denoted by λ(A).

Pauli matrices Matrices important in quantum mechanics and the study of spin

In mathematical physics and mathematics, the Pauli matrices are a set of three 2 × 2 complex matrices which are Hermitian, involutory and unitary. Usually indicated by the Greek letter sigma, they are occasionally denoted by tau when used in connection with isospin symmetries.

Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative.

In differential geometry, a Riemannian manifold or Riemannian space(M, g), so called after the German mathematician Bernhard Riemann, is a real, smooth manifold M equipped with a positive-definite inner product gp on the tangent space TpM at each point p.

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. It was first used by Paul Cohen in 1963, to prove the independence of the axiom of choice and the continuum hypothesis from Zermelo–Fraenkel set theory.

In vector calculus, Green's theorem relates a line integral around a simple closed curve C to a double integral over the plane region D bounded by C. It is the two-dimensional special case of Stokes' theorem.

In mathematics, the adele ring of a global field is a central object of class field theory, a branch of algebraic number theory. It is the restricted product of all the completions of the global field, and is an example of a self-dual topological ring.

In the mathematical field of measure theory, an outer measure or exterior measure is a function defined on all subsets of a given set with values in the extended real numbers satisfying some additional technical conditions. The theory of outer measures was first introduced by Constantin Carathéodory to provide an abstract basis for the theory of measurable sets and countably additive measures. Carathéodory's work on outer measures found many applications in measure-theoretic set theory, and was used in an essential way by Hausdorff to define a dimension-like metric invariant now called Hausdorff dimension. Outer measures are commonly used in the field of geometric measure theory.

In mathematics, Hausdorff measure is a generalization of the traditional notions of area and volume to non-integer dimensions, specifically fractals and their Hausdorff dimensions. It is a type of outer measure, named for Felix Hausdorff, that assigns a number in [0,∞] to each set in or, more generally, in any metric space.

In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

Chebotarev's density theorem in algebraic number theory describes statistically the splitting of primes in a given Galois extension K of the field of rational numbers. Generally speaking, a prime integer will factor into several ideal primes in the ring of algebraic integers of K. There are only finitely many patterns of splitting that may occur. Although the full description of the splitting of every prime p in a general Galois extension is a major unsolved problem, the Chebotarev density theorem says that the frequency of the occurrence of a given pattern, for all primes p less than a large integer N, tends to a certain limit as N goes to infinity. It was proved by Nikolai Chebotaryov in his thesis in 1922, published in.

In mathematics, in particular in algebraic geometry and differential geometry, Dolbeault cohomology is an analog of de Rham cohomology for complex manifolds. Let M be a complex manifold. Then the Dolbeault cohomology groups depend on a pair of integers p and q and are realized as a subquotient of the space of complex differential forms of degree (p,q).

Locally connected space

In topology and other branches of mathematics, a topological space X is locally connected if every point admits a neighbourhood basis consisting entirely of open, connected sets.

In mathematics, a metric outer measure is an outer measure μ defined on the subsets of a given metric space (Xd) such that

In mathematics, the Menger curvature of a triple of points in n-dimensional Euclidean space Rn is the reciprocal of the radius of the circle that passes through the three points. It is named after the Austrian-American mathematician Karl Menger.

In mathematics, the dyadic cubes are a collection of cubes in Rn of different sizes or scales such that the set of cubes of each scale partition Rn and each cube in one scale may be written as a union of cubes of a smaller scale. These are frequently used in mathematics as a way of discretizing objects in order to make computations or analysis easier. For example, to study an arbitrary subset of A of Euclidean space, one may instead replace it by a union of dyadic cubes of a particular size that cover the set. One can consider this set as a pixelized version of the original set, and as smaller cubes are used one gets a clearer image of the set A. Most notable appearances of dyadic cubes include the Whitney extension theorem and the Calderón–Zygmund lemma.

In mathematics, a polyadic space is a topological space that is the image under a continuous function of a topological power of an Alexandroff one-point compactification of a discrete space.

In mathematics, a dual system, dual pair, or duality over a field is a triple consisting of two vector spaces and over and a non-degenerate bilinear map . Duality theory, the study of dual systems, is part of functional analysis.

In the mathematical discipline of functional analysis, a differentiable vector-valued function from Euclidean space is a differentiable function valued in a topological vector space (TVS) whose domains is a subset of some finite-dimensional Euclidean space. It is possible to generalize the notion of derivative to functions whose domain and codomain are subsets of arbitrary topological vector spaces (TVSs) in multiple ways. But when the domain of a TVS-valued function is a subset of a finite-dimensional Euclidean space then many of these notions become logically equivalent resulting in a much more limited number of generalizations of the derivative and additionally, differentiability is also more well-behaved compared to the general case. This article presents the theory of -times continuously differentiable functions on an open subset of Euclidean space , which is an important special case of differentiation between arbitrary TVSs. This importance stems partially from the fact that every finite-dimensional vector subspace of a Hausdorff topological vector space is TVS isomorphic to Euclidean space so that, for example, this special case can be applied to any function whose domain is an arbitrary Hausdorff TVS by restricting it to finite-dimensional vector subspaces.

References

  1. Jones, Peter (1990). "Rectifiable sets and the Traveling Salesman Problem". Inventiones Mathematicae. 102: 1–15. Bibcode:1990InMat.102....1J. doi:10.1007/BF01233418. S2CID   123337823.
  2. Okikiolu, Kate (1992). "Characterization of subsets of rectifiable curves in Rn". Journal of the London Mathematical Society . 46 (2): 336–348. doi:10.1112/jlms/s2-46.2.336.
  3. Schul, Raanan (2007). "Subsets of Rectifiable curves in Hilbert Space—The Analyst's TSP". Journal d'Analyse Mathématique. 103: 331–375. arXiv: math/0602675 . doi:10.1007/s11854-008-0011-y. S2CID   17223641.
  4. Hahlomaa, Immo (2005). "Menger curvature and Lipschitz parametrizations in metric spaces". Fund. Math. 185 (2): 143–169. doi: 10.4064/fm185-2-3 .