Traveling salesman problem, conformal invariance, and dense polymers.

Area of Science:

• Computational geometry
• Statistical physics
• Probability theory

Background:

• The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem.
• Understanding the statistical properties of optimal tours in random instances is crucial for theoretical insights.
• Conformal invariance is a key concept in statistical mechanics, describing scale-invariant systems.

Purpose of the Study:

• To propose and investigate the hypothesis of large-scale conformal invariance for optimal tours in the planar random Euclidean TSP.
• To identify the universality class of this problem by comparing it to other systems.
• To numerically test theoretical conjectures regarding tour length on a cylinder.

Main Methods:

• Analysis of the statistical properties of optimal tours in random Euclidean point sets.
• Investigation of power-law behaviors in tour probabilities and subleading corrections to tour length.
• Numerical simulations to test conjectures on cylindrical geometries.

Main Results:

• The study proposes that optimal tours in the planar random Euclidean TSP are conformally invariant at large scales.
• Evidence for this invariance is found in power-law probabilities of tour zigzagging and subleading corrections to tour length.
• The universality class is conjectured to align with that of dense polymers and minimal spanning trees.

Conclusions:

• The findings suggest a deep connection between the Euclidean TSP and other systems in statistical physics.
• Numerical tests support the theoretical conjectures about tour length on a cylinder.
• The research opens avenues for further exploration of geometric probability and critical phenomena.