The traveling salesman problem, conformal invariance, and dense polymers

Abstract

We propose that the statistics of the optimal tour in the planar random Euclidean traveling salesman problem is conformally invariant on large scales. This is exhibited in power-law behavior of the probabilities for the tour to zigzag repeatedly between two regions, and in subleading corrections to the length of the tour. The universality class should be the same as for dense polymers and minimal spanning trees. The conjectures for the length of the tour on a cylinder are tested numerically.

4 pages. v2: small revisions, improved argument about dimensions d>2. v3: Final version, with a correction to the form of the tour length in a domain, and a new reference

References in corpus (4)

• Dense loops, supersymmetry, and Goldstone phases in two dimensions
• Minimum spanning trees on random networks
• Scaling Limits for Minimal and Random Spanning Trees in Two Dimensions
• Disorder-Induced Topological Defects in a d=2 Elastic Medium at Zero Temperature

Cited by in corpus (8)

• Solvable Critical Dense Polymers
• A scale-free network hidden in the collapsing polymer
• Integrals of Motion for Critical Dense Polymers and Symplectic Fermions
• Minimum spanning trees and random resistor networks in d dimensions
• The Baxter Q Operator of Critical Dense Polymers
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Percolating paths through random points :