Statistical mechanics of the travelling salesman on the Sierpinski gasket

Abstract
We study the statistical mechanics of the travelling salesman on a Sierpinski gasket in which the bond lengths { λi } are quenched random variables. The problem of finding the shortest closed path which visits all N sites is tractable if all the| λi - 1 | are less than (2 N + 1)-1. For a particular choice of the bond-length probability distribution and at low temperatures, the system behaves like a set of non-interacting Ising spins in a quenched random magnetic field. The relevance of one of our results to collapsed polymer chains in random media is also discussed.

Résumé
Nous étudions la mécanique statistique du problème du voyageur de commerce sur un tamis de Sierpinski dans lequel les longueurs des liaisons {λ i} sont des variables aléatoires et gelées. Le problème de trouver le plus court chemin fermé qui visite tous les N sites est traitable si tous les | λi - 1| sont inferieurs à (2 N + 1)-1. Pour un choix particulier d'une distribution de probabilité pour les longueurs des liaisons et aux basses températures, le système se comporte comme des spins d'Ising sans interactions dans un champ magnétique aléatoire. La pertinence d'un de nos résultats aux chaînes polymériques compactes en milieux aléatoires est aussi discutée.